В прошлой статье я рассмотрел обратное геокодирование средствами Spark. Теперь представим, что перед нами встала задача прямого геокодирования почтовых адресов. То есть, получения для записанного текстом адреса неких географических координат.

Адреса для определенности российские, и главное — зачастую написаны криво, то есть с ошибками, неоднозначностями и прочими прелест��ми. И находятся эти адреса в базе данных Hive, на кластере Hadoop.


Ну казалось бы — берем Google Maps Geocoding API (или, если вы сторонник импортозамещения, то Yandex Maps API), и работаем. Но тут нас, как впрочем и c обратным геокодированием, ждет небольшая засада.

Или большая, это как посмотреть. Дело в том, что на этот раз нам нужно обработать примерно 5 миллионов адресов. А может быть и 50 — это сразу было не ясно. Как известно, Google забанит ваш IP примерно через 10 тысяч адресов, Яндекс поступит с вами аналогично, хотя возможно и несколько позже (25 тыс запросов в день вроде). И кроме того, оба API это REST, а значит это сравнительно медленно. И даже если купить платную подписку, скорость от этого не увеличится ни на грош.

И еще — у нас кончились патроны (с) анекдот.

Самое главное забыл — наш кластер Hadoop расположен в интранете, и Google Maps, за компанию с Yandex Maps, и всеми остальными, нам вообще с кластера недоступны. То есть, нам было нужно автономное решение.

Скажу сразу — готового решения вы тут не найдете. Я лишь опишу тот подход, который мы планируем применить, и чуть более подробно — один из шагов на длинном пути к решению.

У нас в запасе конечно кое-что было. Был внутренний сервер ArcGIS, о котором я уже упоминал. Нам не давали им порулить, но разрешали пользоваться его REST сервисами.

Первое, что мы сделали — это прикрутили его к задаче. Он нас не банил, а просто иногда выключался на обслуживание. И что приятно — у него был пакетный режим геокодирования, когда вы подаете на вход пачку адресов (у нас после настройки сервера размер пачки был 1000 штук, по умолчанию там кажется что-то на порядок-другой меньше). Это все тоже было непросто, и мы, и поддержка ArcGIS долго занимались с сервером борьбой сумо, но это уже отдельная история.

После всех ухищрений и перипетий мы смогли примерно за сутки обработать свои пять миллионов. Нужно было двигаться дальше, и пытаться ускориться еще.

Заодно стало понятно, что любой геокодер с REST нам скорее всего не подойдет. Кроме того, мы смотрели и на Nominatim, и на Pelias, и на Photon, и на gisgraphy, и в общем не остались довольны ни одним. Качество и быстродействие (или и то и другое) было далеко от идеала.

Например, никто не умеет геокодировать пакетами (а это сильно ускоряло работу с ArcGIS).

Или качество — зайдите на демо-сервер gisgraphy.com, и попробуйте найти Москву. Вы получите пару десятков ответов, среди которых будут: Москва (город в РФ), Канзас-Сити (город в США), Химки, Калуга, Выхино-Жулебино, и многие другие объекты, которые я бы совсем не хотел видеть в ответе геокодера при поиске Москвы.

Ну и последняя (но не по важности для нас) проблема — далеко не у всех геокодеров API такой же продуманный, как скажем у Google Maps. Скажем, API ArcGIS уже значительно неудобнее, а остальные по большей части еще хуже. Если вы геокодируете адреса для UI, то как правило выбором лучшего варианта занимается человек. И у него это получается лучше, чем у программы. А в случае массового геокодирования, как у нас, оценка качества результата для конкретного адреса — один из важных компонентов успеха.

В итоге варианты вида «Развернуть собственный Nominatim», например, отпали тоже.

Что же делать?


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

Первым и главным кандидатом на базу существующих адресов является ФИАС. Погодите, скажете вы, но ведь в ФИАС же всего несколько миллионов адресов — а у вас же целых 50 миллионов? Да, там действительно лишь несколько миллионов домов. А наши 50 — это 50 миллионов адресов наших пользователей, то есть это — адреса людей, и у них в адресе внезапно есть квартира. Пять миллионов домов по 1-100 квартир, в каждой квартире живет несколько людей… ну вы все поняли. И второй вариант — это адреса офисов, где тоже на один офисный центр приходится до сотни помещений, которые иногда сдаются в аренду.

При этом нам очевидно не нужен адрес с номером квартиры (или офиса) — во-первых, это персональные данные, со всеми вытекающими, а во-вторых, нам все равно не интересно, как расположены квартиры в конкретном доме, и какие у них координаты. Нужен только дом. Для офисов это не совсем верно, но расположение офисов в здании по этажам все равно определяется не координатами.

В конечном итоге, имея базу ска��ем из 5 миллионов (условно) существующих домов, мы сможем решить задачу геокодирования 50 или 100 миллионов адресов, просто выбросив из адреса квартиру или офис, и сопоставив его с базой.

А где взять координаты домов? Очевидный открытый источник только один — OpenStreetMap, там есть дома, с геометриями, и разного рода прочими атрибутами типа этажности или даже цвета крыши.

После всех обсуждений у нас был наполеоновский план. Вот такой:

  • загружаем в Hadoop данные карт из OSM
  • загружаем данные ФИАС с адресами
  • строим список уникальных полных адресов с номерами домов
  • геокодируем его, путем поиска адресов в OSM, а что не нашли — через ArcGIS


Получаем базу домов с широтой и долготой. Наслаждаемся. Пожинаем плоды. Пропиваем премии (шутка).

В этой статье я расскажу, как мы воплощали в жизнь первый пункт этого плана.

Что такое OpenStreetMap


Если смотреть на OSM с позиции данных, то карты можно себе представить в виде трех таблиц:

  • точки (nodes)
  • линии (ways)
  • отношения (relations)


Реальные схемы этих данных будут приведены чуть ниже.

Только точки имеют координаты (широту и долготу, в градусах). Линии — это упорядоченная последовательность точек. Отношения — это набор из точек и линий, у каждой из которых есть роль.

Все остальное — это так называемые тэги (tags). То есть, например банкомат, или магазин, или вход в метро — это может быть точка, снабженная тэгом amenity=atm, или shop=чем-торгует, или еще каким-то. Есть справочник официально рекомендованных тэгов (для каждого прим��няемого языка и страны они могут быть частично свои), и практика придумывания нестандартных.

Кроме тэгов у каждого элемента карты есть уникальный числовой id, а также некоторые атрибуты, имеющие отношения к истории — кто редактировал, когда, номер правки и т.п.

База данных с картой поставляется в нескольких форматах:
— pbf — это Google Protobuf, переносимый формат сериализации данных.
— xml — это очевидно XML. Намного больше по объему.

Надо понимать, что база обновляется ежедневно. Поэтому выгрузки бывают полные и инкрементальные.

Мы выбрали PBF как более компактный.

Чтобы прочитать его в Hadoop, есть Java API, специально сделанный под OSM, называется этот проект osmosis. В принципе, работа с ним несложная — вы загружаете файл, и выполняете цикл по элементам карты. Точки складываете в одно место, линии в другое, отношения в третье. В принципе, osmosis и например Spark уже достаточно, чтобы загрузить все данные.

К счастью, в процессе реализации своего велосипеда, мне как-то пришло в голову поискать в интернете средства конвертации OSM в принятые в Hadoop форматы — Parquet (паркет) и Avro. В каком-то смысле оба — аналоги PBF, так что шанс найти конвертор существовал. И он нашелся, да не один.

Встречайте, OSM Parquetizer


Смотрите, что я нашел!

Для лентяев — прямо в readme проекта в первой же строке написано: Telenav еженедельно публикует выгрузки планеты по адресу.

Для совсем лентяев: готовьтесь грузить порядка 700 гигабайт ;) Ну, если вам конечно нужна планета. Обычно можно обойтись скажем Европой.

Если грузить вы не хотите, то процесс выглядит так: загружаете карту в формате PBF, например с геофабрики. Это 2.5 гигабайта, если вам нужна Россия, и 19 если Европа. Тоже не мало, но можно найти и более мелко порезанные выборки. Дальше кладем файл на диск, и запускаем программу:

java -jar ./osm-parquetizer.jar russia-latest.osm.pbf

Через несколько минут или даже секунд, в зависимости от производительности вашей машины, получаете три файла в формате паркет. Вот как это выглядит у автора (он из Румынии):

-rw-r--r--  1 adrianbona  adrianbona   145M Apr  3 19:57 romania-latest.osm.pbf
-rw-r--r--  1 adrianbona  adrianbona   372M Apr  3 19:58 romania-latest.osm.pbf.node.parquet
-rw-r--r--  1 adrianbona  adrianbona   1.1M Apr  3 19:58 romania-latest.osm.pbf.relation.parquet
-rw-r--r--  1 adrianbona  adrianbona   123M Apr  3 19:58 romania-latest.osm.pbf.way.parquet

Схемы получаемых файлов .parquet:

node
|-- id: long
|-- version: integer
|-- timestamp: long
|-- changeset: long
|-- uid: integer
|-- user_sid: string
|-- tags: array
| |-- element: struct
| | |-- key: string
| | |-- value: string
|-- latitude: double
|-- longitude: double

way
|-- id: long
|-- version: integer
|-- timestamp: long
|-- changeset: long
|-- uid: integer
|-- user_sid: string
|-- tags: array
| |-- element: struct
| | |-- key: string
| | |-- value: string
|-- nodes: array
| |-- element: struct
| | |-- index: integer
| | |-- nodeId: long

relation
|-- id: long
|-- version: integer
|-- timestamp: long
|-- changeset: long
|-- uid: integer
|-- user_sid: string
|-- tags: array
| |-- element: struct
| | |-- key: string
| | |-- value: string
|-- members: array
| |-- element: struct
| | |-- id: long
| | |-- role: string
| | |-- type: string


Как видите, тут все несложно. Дальше мы делаем следующее:

  • кладем файлы на кластер Hadoop командой hdfs dfs -put
  • заходим скажем в Hue и создаем схему/базу, и три таблицы к ней, на основе указанных выше данных
  • выполняем select * from osm.nodes, и наслаждаемся результатом.

Маленький нюанс: в нашей версии Hive (а возможно что и в вашей) не умеет создавать таблицы на основе схемы из Parquet. Нужно показанное выше либо преобразовать в CREATE TABLE (что в общем-то, не сложно, и я оставлю это в качестве домашнего упражнения читателям), либо поступить чуть хитрее: Spark умеет читать схему и данные из паркета, и создавать на их основе временные таблицы. Таким образом, мы можем прочитать данные в Spark Shell примерно так:

val nodeDF = sqlContext.read.parquet("file:/tmp/osm/romania-latest.osm.pbf.node.parquet")
nodeDF.createOrReplaceTempView("nodes")

После чего вы можете уже создать таблицы в Hive, используя LIKE nodes.

Еще замечание для лентяев: у автора есть вот такой замечательный пример, из которого в общем все становится ясным (ну, если вы владеете Spark). Это конечно не Spark Shell, а Databricks Notebook, но на перевод одного в другое у меня ушло примерно минут 15 стучания по клавиатуре. И за 30-40 минут удалось это все конвертировать в запросы для Hive с применением некоторых аналогов, которые чуточку отличаются от спарка.

Пример реального запроса


Что мы можем получить из этой базы в ее существующем виде? В общем-то, достаточно много. При наличии Hive или Spark, Spatial Framework, Geometry API, либо одной из альтернатив, которыми являются GeoSpark либо например GeoMesa, вы сможете решать на этой базе множе��тво самых разнообразных задач.

Посмотрим пример. Проще всего работать с точками. Например, запрос для получения списка банкоматов с их координатами выглядит так:

select * from nodes where tags['amenity']='atm'

Как построить такой запрос, вы можете догадаться, прочитав страницу в вики. Там же вы найдете, какие еще тэги бывают, и часть из них можно включить в свой запрос вместо *, в форме tags['operator'], например, чтобы показать название банка.

Из этой же страницы следует, что возможна разметка банкомата в виде тэгов amenity=bank и atm=yes. Увы, но такие неоднозначности в OSM везде.

Если вы новичок, и только знакомитесь с OSM, очень рекомендую освоить (по хорошим примерам в вики) overpass-turbo. Это инструмент, который позволяет выполнять разного рода поиск по данным карты, как геометрическими условиями, так и с условиями на тэги.

А где же тут адреса?


Хороший вопрос. Адреса в OSM — это элементы карты, снабженные тэгами addr:*, т.е. начинающимися с addr. Описание вы найдете тут. В принципе, зная все, что я изложил выше, вы уже можете написать кое-какой работающий запрос:

select * from nodes where tags['addr:housenumber']!=null

Какие нас тут ждут проблемы? Во-первых, адреса расставляются как на точки (например входы зданий), так и на полигоны, т.е. на ways. Так что запрос нам придется как минимум продублировать. А во-вторых, на упомянутой выше странице вики написано прямым текстом, что не рекомендуется ставить тэги, указывающие город, район, регион и страну, а это нужно вычислять геометрически. Как это сделать? В общем-то, это практически задача обратного геокодирования, с легкими модификациями, и она была описана в прошлом посте.

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

В целом эта задача не слишком уж простая, но вполне решаемая, причем решается она не при геокодировании, а при загрузке обновлений OSM в нашу базу, в спокойной обстановке.

Что полезно сделать дальше


В принципе, можно уже работать с теми таблицами nodes, ways и relations, которые у нас получились, но лучше немного поменять схему, сделав ее более подходящей для Hive и Spark. Дело в том, что схема OSM полностью нормализованная, ways и relations не содержат координат вообще. Чтобы построить полигон для way, нужно выполнить join с nodes. Вот эту операцию я бы рекомендовал проделать сразу, сохранив полигоны либо в виде массива структур (Hive умеет работать с составными типами array, map и struct), либо сразу в виде сериализованного представления скажем класса Geometry. Как это проделать, есть в примере у автора parquetizer.

Можно повторить подобную операцию на уровне relations, если хочется, но вряд ли стоит. Во-первых, вам далеко не всегда нужны будут все элементы отношения, а во-вторых, самих relations в OSM намного меньше.

Конвертор в Avro


Вот тут имеется еще один конвертор, на этот раз в формат Avro. А тут описано, где взять готовые файлы. Размеры я не измерял, но думаю, что примерно 15-20 файлов на планету должны быть сопоставимы с PBF. То есть это гигабайты, и много.

Некоторые выводы


А где же геокодирование, спросите вы? Да, загрузка карт и извлечение адресов — это лишь часть общей задачи. Я надеюсь до этого еще дойдет.