OpenStreetMap (OSM) — глобальный проект, образованный вокруг геоинформационной базы данных, наполняемой всеми желающими — как энтузиастами, так и заинтересованными компаниями. Любой может внести свой вклад, однако открытость имеет и оборотную сторону, которая приводит к тому, что в базу часто попадают некорректные правки. Поэтому в экосистеме OSM написано множество валидаторов, которые позволяют поддерживать качество данных на приемлемом уровне.

С 2016 года в open source существует препроцессор метро, который валидирует (генерирует отчёты об ошибках) маршруты скоростного городского транспорта в OSM на предмет полноты и логических/топологических ошибок и преобразует их в форматы, пригодные для сервисов роутинга и рендеринга, в том числе в GTFS. Кроме данных OSM он принимает на вход список сетей общественного транспорта (ОТ), содержащий контрольную информацию о числе линий, станций и прочего в некоторой транспортной сети. Препроцессор успешно себя зарекомендовал в подготовке данных об ОТ для таких приложений, как Maps.me и Organic Maps.

В этой статье я хотел бы поделиться подходом к детектированию одного из видов ошибок, которые довольно часто случаются в данных OSM и автоматический отлов которых представляет собой некоторый вызов — это случайное выпадение станции из маршрута. Все исходные коды валидатора и описываемого алгоритма находятся в открытом доступе. Но сначала определимся с понятиями, используемыми для представления данных об ОТ в OpenStreetMap.

Основные понятия

При первом прочтении можно обойтись обывательским представлением о станции (остановке), хотя в OSM ей могут соответствовать минимум четыре различных вида объектов:

• railway=halt (пример — остановочный пункт Elsholz),

• railway=station (пример — станция метро Грин‑Парк),

• public_transport=stop_position (пример точки остановки на станции Грин‑Парк),

• public_transport=stop_area (пример места остановки на станции Грин‑Парк).

Замечание. Ссылки на OSM‑объекты со временем могут устареть. Альтернативный способ их получить — выполнить приблизительно такой запрос в Overpass Turbo, спозиционировав карту в область некоторой станции:

(
nwr[railway=station]({{bbox}});
  rel[public_transport=stop_area]({{bbox}});
);
(._;>>;);
out;

Схематически эти понятия иллюстрирует изображение (создано для OSM Wiki под лицензией CC SA-4.0):

Если захотите углубиться в программный код алгоритма на GitHub, то роль станции в нём играет класс StopArea, основанный на OSM-отношении public_transport=stop_area, объединяющем ж/д станцию, платформы и входы на станцию в определённом месте остановки ОТ.

Замечание. Мы будем говорить о скоростном железнодорожном транспорте, хотя алгоритмы и выводы можно распространить и на наземный транспорт: автобусы, трамваи, троллейбусы.

Пересадка или пересадочный узел — две или более станции, между которыми можно осуществить пеший переход за относительно короткое время. В OSM они обозначаются специальным объектом — отношением public_transport=stop_area_group. Пример - пересадка на станции Green Park между линиями Piccadilly Line, Jubilee Line и Victoria Line. Иногда то, что для пассажира выглядит как одна станция, в OSM может представляться как несколько станций, объединённых пересадкой.

Маршрут — это последовательность остановок, обычно имеющая свой идентификатор, по которой периодически следуют транспортные средства ОТ. Пример реального маршрута в OSM: Piccadilly line: Uxbridge → Cockfosters.

Рассмотрим гипотетический маршрут «R1: Reading → Maryland». Из определения следует, что «R2: Maryland → Reading» — это другой маршрут, так же как и укороченный вариант «R4: Reading → Slough» или экспресс‑маршрут «R3: Maryland — Slough — Reading», делающий всего одну промежуточную остановку.

Мастер-маршрут — это все варианты маршрутов в пределах общего направления, в том числе маршруты «туда» и «обратно», укороченные, ускоренные за счёт пропуска некоторых станций, а также варианты с другими отличиями. В нашем примере все перечисленные маршруты, которые мы обозначим как R1-R5, могут быть объединены в один мастер‑маршрут. Пример реального мастер‑маршрута: Линия Пикадилли.

Замечание. Здесь и далее станции и маршруты на картинках служат только для иллюстраций и могут не соответствовать реальности.

Подробнее о решаемой проблеме

Когда валидатор обрабатывает данные OSM, он сравнивает количество найденных на маршруте станций с числом, заранее занесённым в файл контрольных значений. И если хранить и поддерживать количество станций во всех сетях скоростного городского транспорта в мире на мастер-маршрутах ещё возможно, то для всех вариантов маршрутов — уже не вариант. Поэтому если случайно из данных OSM удалят станцию в одном из направлений, количество станций в мастер-маршруте не изменится и валидатор не заметит, например, такую ошибку, где в обратном направлении пропущена станция Langley:

Алгоритм

Поиск маршрутов-близнецов

Обратимся к множеству маршрутов R1-R5 ещё раз:

Назовём два маршрута в мастер-маршруте потенциальными близнецами, если начало первого маршрута является концом другого, и наоборот. Таковыми для маршрута R1 являются R2 и R3. Среди потенциальных близнецов выберем наиболее близкого — по числу общих станций. Таким образом в нашем случае мы найдём две пары маршрутов-близнецов: (R1, R2) и (R4, R5). Для каждой пары запустим алгоритм поиска отличий, ведь весьма вероятно, что отличия в близнецах — следствие ошибок в данных.

Поиск отличий в маршрутах

Определить, содержит ли один маршрут все станции из другого маршрута, не является сложной задачей. Однако здесь много нюансов: станция может быть пропущена как в первом маршруте, так и во втором, или пропущено сразу несколько станций, причём идущих подряд или нет. А ещё станция в одном маршруте может не соответствовать этой же станции в другом, то есть может быть по ошибке подменена дублем или совершенно другой станцией. Всё это очень напоминает… редакционное расстояние Левенштейна!

Посмотрим на маршруты T1 и T2 ещё раз:

Представим маршрут как слово, где буквы — это станции (в общем случае — пересадочные узлы). По первым буквам станций маршруту T1 соответствует слово RTBSLHM, а обратному маршруту T2 — слово MHSBTR. Сравним слово для T1 с перевёрнутым словом для T2:

RTBSLHM
RTBSHM

У идеальных близнецов слова должны совпадать, однако у нас в T2 имеется «опечатка» — пропущена буква L. Таким образом, поиск несоответствия станций на паре маршрутов сводится к поиску редакционного расстояния между парой слов.

Замечание. Первые буквы здесь используются только для иллюстрации. Настоящие «буквы» — это объекты станций/пересадочных узлов!

Алгоритм Вагнера‑Фишера позволяет методом динамического программирования найти кратчайшую последовательность шагов по преобразованию одного слова в другое путём добавления, удаления или замены одной буквы за один шаг. Результатом будет редакционное предписание — в каких местах необходимы добавления/удаления/замены. 

Таким образом, адаптированный под маршруты ОТ алгоритм Вагнера‑Фишера выдаст все отличия в станциях у пары маршрутов‑близнецов. Проиллюстрируем это ещё на одном примере с бóльшим количеством «опечаток» на маршрутах, где помимо выпадения станций в исходных данных оказались две разные станции там, где должна быть одна общая станция.

Адаптированный алгоритм Вагнера-Фишера, будучи запущен на паре маршрутов (S1, S2), выдаст следующие предупреждения:

• В маршруте S1 отсутствует станция Taplow;

• В маршруте S2 отсутствует станция Langley;

• Разные станции Slough в маршрутах S1 и S2.

Ложные срабатывания

В реальности каждый случай обнаруженной ошибки может являться ложным срабатыванием и потребует отдельного разбирательства, однако в описанном виде алгоритм выдаст слишком много ложных срабатываний в случаях, когда прямой и обратный маршруты действительно расходятся на каком-то промежутке пути, например:

Алгоритм скажет, что станции Woodstock и Esplanade, Salt River и Mutual не соответствуют друг другу, а Ndabeni пропущена в маршруте U1. Для борьбы с этим стоить заметить, что в маршрутах-близнецах рельсы обычно проходят достаточно близко и в пределах станции точки посадки не удалены друг от друга более чем на пару десятков метров. Но даже с учётом крупных вокзалов с множеством путей и платформ эта цифра не должна превышать 100 м. Можно без опасений завысить эту цифру, ведь лучше получить ложное срабатывание, чем пропустить ошибку. Тем более если пути железнодорожных маршрутов действительно расходятся, то обычно намного больше, чем на 100 м.

Таким образом, для детектирования расхождения маршрутов мы сформируем такой критерий: если расстояние от станции, определённой алгоритмом как пропущенная или несоответствующая, до рельсов обратного маршрута превышает некоторый порог (~100 м), то мы считаем, что рельсы разошлись, — и не будем формировать сообщения об ошибках.

Практическое применение

Упомянутый валидатор метро в OSM работает много лет и содержит разносторонние проверки, а выдаваемые им ошибки регулярно исправляют несколько человек. При этом это не единственный валидатор ОТ. Тем не менее, когда вышеописанный алгоритм был прогнан на 300+ сетях метро и другого скоростного ж/д транспорта, он выдал 144 пропущенные/несовпадающие станции, всего 17 из которых оказались ложными срабатываниями.

Вот так сработал этот красивый пример всепроникающей сущности теории алгоритмов, где методы обработки текста нашли применение и в области общественного транспорта — вотчины теории графов.

Рекомендуется к внедрению в такие широко используемые валидаторы как:

• OSM Inspector: проект, issue 

• Osmose: проект, issue