Привет, дорогие читатели хабра. В этой статье поговорим
- Про адреса и хранилища данных с нечеткой схемой
- Про обработку геоданных на java, а именно про Java Topology Suite
- Про стоимость «простоты» для разработчика
- Про pure Java nosql документную бд / движок полнотекстового поиска — Elasticsearch.
Для читателей хаба Java, незнакомых с OSM
OSM — это открытая геопространственная база данных с мировым весьма подробным покрытием.
Для пользователя — это просто карта, которую можно посмотреть on-line, загрузить на навигатор, телефон, отредактировать, распечатать и вообще использовать любым другим мыслимым образом, в том числе получая от этого коммерческую выгоду.
С точки зрения разработчика — эта весьма своеобразная база данных.
- В OSM нет четкой схемы данных, нет привычного для ГИС деления на слои. Тип объекта, его свойства, а в некотором смысле и геометрия, задаются через теги — текстовые пары ключ-значение.
- Геометрия хранится лишь для точек. Линия — это массив id'шников точек. Полигон — набор ссылок на линии с указанием, в какую из границ входит линия — внутреннюю или внешнюю.
- Это позволяет сообществу лепить новые типы данных на лету. Хотите отмечать тротуары — договаривайтесь о сочетании тегов и вперед. Все это без драм (ну почти) с выпиливанием каким-то непонятным модератором милых вашему сердцу данных с комментарием «вы захламляете карту, ваш труд никому не нужен».
Естественно, для разработчиков такая вольница запросто превращается в кошмар.
Адреса
Большинство из нас проживает жизнь сменив 1-2 города, и мы просто не успеваем обратить внимание на разнообразие схем почтовой адресации.
Начинается с малого — с записи адреса: от большего к меньшему или от меньшего к большему.
Потом выясняется, что в некоторых городах не используют в адресе улицу:
дом 521, Котор, Черногория или РФ, поселок Энергетик дом 15.
Что у одного дома может быть несколько адресов:
Лучший город земли, улица Прямая, 22 и у него же Лучший город земли, улица Перпендикулярная, 12
Что двойная адресация может быть не только у угловых домов и что 2 адреса — это далеко не предел.
Таллин Каштановая улица 13, 15, 17
Таллин Вишневая улица 1, 3
*Пример вполне себе из жизни, просто я забыл оригинальные названия улиц.
Что адресоваться могут не только сами дома, но и подъезды, а то и внешне никак не проявляющие себя секции дома. (Это как раз из примера с Таллином — адреса по одной улице внутри одного здания — это внутренние секции, принадлежавшие когда-то разным владельцам).
Ну и наконец, всякая экзотика как
Набережные Челны, 11/1
Это 11 жилой комплекс, дом 1. На самом деле, дома в НЧ имеют также привычные нам адреса вида Улица Дом, но местные жители ими не пользуются.
Теперь умножаем это на:
4 принципиально разных способа указания Населенного пункта в OSM
3-4 способа указания множественной адресации
3 способа указания улицы для адреса
Причем, если вы вносите данные, вам достаточно просто пользоваться парой схем из этого зоопарка. Если вы хотите написать приличный геокодер, вам мало просто помнить о существовании этого зоопарка, вам необходимо его «посчитать».
К примеру, давайте посмотрим, что надо сделать чтобы сопоставить дому — город.
Начнем с родины проекта — Великобритании.
Вот к примеру дом в Вестминстере. www.openstreetmap.org/way/46138969
addr:housenumber 1
addr:street Derby Gate
building yes
Сам Вестминстер отмечен вот так:
name Westminster
name:ru Вестминстер
place town
Что еще важно помнить, дак это то, что это практически самый центр Лондона. Лондон по сути состоит из нескольких десятков городков поменьше. К какому городу отнести дом? К Лондону или к Вестминстеру?
На самом деле — однозначно ответить на этот вопрос нельзя, для здания не указано к какому городу он формально относится. Но, для меня, например, очевидно что хороший геокодер должен найти этот дом как по запросу «London, Derby Gate, 1» так и по запросу «Westminster, Derby Gate, 1» так и «London, Westminster, Derby Gate, 1»
Как мне видится реализация: я сопоставляю каждому дому (адресной точке) все полигональные границы в которые она попадает (сюда попадут границы города если они указаны) и массив окрестных населенных пунктов, сюда попадут London как nearest city, и Westminster, как nearest town ну и еще их соседи.
Вот как это выглядит в схеме json данных для elasticsearch
//Сюда попадут окрестные населенные пункты
"nearby_places": {
"properties": {
"id": {
"type": "string"
},
"place": {
"type": "string"
},
"name": {
"type": "string"
},
"alt_names": {
"type": "string"
}
}
},
//Сюда попадут населенные пункты для которых будет найдено точное совпадение, либо по имени, либо по полигональной границе
"locality_name": {
"type": "string"
}
Соответственно, при поиске, можно будет найти дом по запросу с любым из городов, разница будет лишь в релевантности точно сопоставленного города и соседних городов. Каждое «нужно» это 1 или 2 пространственных join'а.
Геокодер
Как высказался один известный осмер Zverik
«В последнее время, все только тем и заняты что делают очередной геокодер».
Я не стану исключением: все пишут геокодер, чем я хуже? Я тоже хочу велосипед геокодер.
Чего вообще люди хотят от OSM касательно адресов?
- Выгрузите мне адреса в csv или sqlite
- Геокодируйте мне, пожалуйста, список из 100500 адресов
- Онлайн сервис геокодирования (онлайн геокодеры в OSM есть, поэтому этот пункт не на первом месте)
- Я внес адрес для домика или организации, почему я не могу найти его через онлайн геокодер?
- Я хочу свой локальный поисковик с данными OSM, что посоветуете.
Ответ обычно начинается так:
- Вам понадобится postgres, postgis (эту часть квеста обычно проходят 90%)
- Вам понадобится загрузить данные OSM в эту бд, используя osmosis или osm2pgsql, если вдруг вы решили провернуть такой фокус в масштабах планеты, то запаситесь оперативкой (16-32гига) и терпением (несколько суток, если у вас много оперативы, и несколько недель, если оперативки мало). По странам тоже не очень быстро и не очень лояльно к железу.
- Обработайте данные скриптами на постгрешке. (В зависимости от желаемого результата, тут остается 10% — 20%, желающих связываться с обработкой данных OSM-стоиков.)
- Добавьте поиск по бд с адресами или выгрузите нужное вам в csv/json
Целиком весь квест проходят единицы. Добавление каждой новой фишки к геокодеру оборачивается часами, а то и сутками на обработку геопространственных join'ов постгрешкой, и гигабайтами оперативки, необходимой для загрузки новых, требующихся вам данных в постгрешку.
И когда вы понимаете, что в РФ принято считать город для дома по попаданию в полигон города, а в UK — по близости точек населенных пунктов, соответсвенно, вам нужны и границы городов, принятые в РФ, и полигоны Вороного + соседи для Великобритании, и все это вперемешку. Глаза наливаются кровью, а очередная схема адресации, основанная на куче отношений, вызывает шквал эмоций.
Геокодирование можно рассматривать как две практически независимые задачи:
- Для всех объектов (адресов, улиц, городов, точек интереса) получить данные: границы городов, соседние точки городов, окрестные улицы.
- Организовать по этим данным поиск. В простейшем случае — это просто полнотекстовый поиск.
Я сконцентрировался на решении задачи 1 — получить данные, в пригодном для поисковой индексации виде. В принципе, отдав эти данные для индексации google или yandex вторую часть геокодера можно зааутсорсить.
Попытка №1
Первая моя попытка здесь. github.com/kiselev-dv/osm-addresses-pgsql
Я загружаю упрощенные данные в постгрес, после чего, прибегая к различным ухищрениям, чтобы уложиться в разумное время, обрабатываю их.
В процессе разработки оказалось, что быстрее и гибче обработать геометрию на java и загружать в постгрес уже готовую геометрию.
Вычислительная сложность в вычислительной геометрии
Середину статьи обычно никто не читает, надеюсь, явная тавтология взбодрит заскучавшего читателя.
Почему на загрузку 2 Гигабайт данных, запакованных в зипованый xml, требуется 6+ Гигабайт оперативки?
Данные OSM не содержат полной геометрии, единственным объектом OSM, который имеет географическую привязку, является точка. (Просто торжество нормализации данных) Соответсвенно, чтобы получить геометрию, вам необходио загрузить точки по спискам id'шников из линий. Собственно основной объем памяти съедает индекс точек. Чтобы не лазить лишний раз на диск, для них обычно сохраняют и теги. Сейчас дамп планеты содержит порядка 3х миллиардов точек, добавьте сюда накладные расходы на хранение точек в индексе, и для обычного домашнего компьютера замаячит JavaHeapSpace.
Допустим, нам удалось исхитриться и загрузить все это в бд, собрать геометрические индексы. Как ускорить выполнение запросов?
Основная часть работы — это Point Location Problem. То есть на примере РФ нам нужно посчитать вхождение полутора миллионов точек в полмиллиона полигонов границ. Важно также понимать, что, к примеру, граница РФ содержит 40 000 сегментов. Весь миллион точек надо проверить на вхождение в границу. Несмотря на существование индекса, сложность O(N * M). Постгис быстро, воспользовавшись индексом, определит, что точка n из миллиона адресных точек возможно попадает в границы РФ, после чего, определяя точно ли точка внутри полигона, будет рассчитывать M скалярных произведений, где M — это количество сегментов полигона границы.
К моменту осознания этого факта я уже делал практически всю подготовительную работу: парсил полигоны административных границ, получал и упрощал геометрию улиц, получал геометрию для домиков с адресами на java, используя Java Topology Suite. www.vividsolutions.com/jts/jtshome.htm Тоесть постгис я по сути использовал для расчета пространственных join'ов ну и как общий io фреймворк.
Еще одно узкое место работы с postgis — сложность распараллелить выполнение запроса. В данном случае у меня не сотни запросов в секунду, а 1 толстый запрос на несколько часов.
Самый лучший велосипед, попытка №2
На самом деле, расписывая сложности обработки данных, я немного кривлю душой. К примеру, сообщество OSM вполне себе справляется с конвертацией карт в форматы различных навигационных програм. Делает это в ежедневном режиме, используя как выделенные сервера, так и обычные домашние компьютеры участников.
При этом, сообщество РФ обрабатывет данные OSM с учетом местной специфики, сообщество Германии — с учетом своей.
Во второй попытке, я решил пойти схожим путем. Я решил написать приложение которое было бы под силу использовать большинству OSM'еров на домашних пк.
Что для этого требуется:
- Самое главное — простота установки. Никто не станет настраивать для вас окружение, устанавливать дополнительные бибилиотеки, или движок БД. (Прощай postgres)
- Возможность настройки. Если вы хотите, чтобы сообщество вам помогало, дайте сообществу возможность учесть и реализовать местные традиции и практики.
- Разнообразие применений. Опять же, дайте возможность местному комьюнити решать при помощи вашего инструмена широкий круг задач. Дайте возможность делать выгрузки адресного реестра в том виде в котором он нужен местному сообществу.
Т.к. некоторый опыт после попытки №1 у меня уже был, мне оставалось частично повторить процесс реализованый для postgis используя только java. По сути, мне нужны лишь пространственные индексы RTree и QuadTree, которые реализованы в JTS. И пара утилитарных методов для работы с геометрией, как то разделение геометрии и точка на линии.
Итак, я обрабатываю данные OSM в 2 стадии.
1 Получаю геометрию из файла OSM, режу ее на куски — полосы шириной 0.1 градус. Это позволяет естественным образом разбить задачу на части и попутно упрощает геометрию границ. То есть вместо 1 границы РФ с 40 000 сегментов я получаю 1500 кусочков, в каждом из которых пара десятков сегментов. Количество полигонов границ на каждую полосу также выходит в районе нескольких десятков.
2 На второй стадии я рассчитываю попадание точек в полигоны границ, ищу ближайшие улицы, ближайшие города. Каждая «полоса» обрабатывается отдельно, соответсвенно, этот этап распараллелен между потоками / нодами.
В результате я получаю json описание для точек интереса, улиц, городов, границ и домов.
{
"id": "poipnt-3372930671-n600379459",
"ftype": "poipnt",
"timestamp": "2014-05-14T15:22:11.785Z",
"poiTypes": ["police"],
"boundaries": {
"index_name": "Саров, Нижегородская область, Российская Федерация",
"text": "Российская Федерация, Нижегородская область, Саров",
"langs": [],
"longText": "Российская Федерация, Нижегородская область, ЗАТО Саров, Саров",
"boundariesHash": -410546539,
"parts": [{
"lvl": "boundary:2",
"names": {
//Здесь был список названий РФ на всех мыслимых языках
"int_name": "Russia",
"official_name": "Российская федерация",
"name": "Россия"
},
"lnk": "admbnd-2864649470-r60189",
"name": "Российская Федерация",
"lvl-size": 130
}, {
"lvl": "boundary:4",
"names": {
"name:en": "Nizhny Novgorod Oblast",
"name:ru": "Нижегородская область",
"name": "Нижегородская область",
"name:de": "Oblast Nischni Nowgorod"
},
"lnk": "admbnd-3018389977-r72195",
"name": "Нижегородская область",
"lvl-size": 110
}, {
"lvl": "boundary:6",
"names": {
"name:ru": "ЗАТО Саров",
"name": "ЗАТО Саров",
"official_name": "ЗАТО Город Сарод"
},
"lnk": "admbnd-3704710510-r2031968",
"name": "ЗАТО Саров",
"lvl-size": 90
}, {
"lvl": "place:town",
"names": {
"name:hu": "Szarov",
"name:en": "Sarov",
"name:ru": "Саров",
"name:pl": "Sarow",
"name": "Саров",
"name:de": "Sarow"
},
"lnk": "plcbnd-3118671325-r1428992",
"name": "Саров",
"lvl-size": 70
}]
},
"properties": {
"name": "УВД",
"amenity": "police"
},
"type": "Feature",
"metainfo": {
"id": 600379459,
"type": "node"
},
"geometry": {
"type": "Point",
"coordinates": [43.323823, 54.935209]
}
}
{
"id": "adrpnt-0642964090-w129096772",
"ftype": "adrpnt",
"timestamp": "2014-05-14T15:31:38.778Z",
"nearbyStreets": [{
"id": "hghway-3750745956-w128994466",
"properties": {
"highway": "unclassified",
"name": "Полярная улица"
}
}, {
"id": "hghway-1683350308-w129293134",
"properties": {
"kladr:user": "87005000001000100",
"surface": "concrete",
"highway": "tertiary",
"name": "улица Набережная Дежнёва",
"oneway": "no"
}
}, {
"id": "hghway-0059099168-w129293131",
"properties": {
"highway": "unclassified",
"name": "Полярная улица"
}
}, {
"id": "hghway-0069632087-w129293121",
"properties": {
"kladr:user": "87005000001000100",
"surface": "concrete",
"highway": "tertiary",
"name": "улица Набережная Дежнёва",
"oneway": "no"
}
}, {
"id": "hghway-4111943004-w128995822",
"properties": {
"highway": "residential",
"name": "Чукотская улица"
}
}],
"properties": {
"building": "yes",
"building:levels": "2",
"sport": "swimming",
"amenity": "swimming_pool",
"addr:street": "улица Набережная Дежнёва",
"addr:housenumber": "14"
},
"nearestCity": {
"id": "plcdln-2842041450-n1575069719",
"properties": {
"name:fr": "Providenia",
"addr:postcode": "689251",
"name:ru": "Провидения",
"name:en": "Provideniya",
"name:nl": "Providenia",
"name:pl": "Prowidienija",
"name:it": "Providenija",
"name:es": "Providéniya",
"addr:country": "RU",
"name": "Провидения",
"name:de": "Prowidenija",
"addr:region": "Чукотский автономный округ",
"place": "town"
}
},
"type": "Feature",
"addresses": [{
"index_name": "дом 14, улица Набережная Дежнёва, Провидения, Провиденский район, Чукотский автономный округ, Российская Федерация",
"text": "Российская Федерация, Чукотский автономный округ, Провиденский район, Провидения, улица Набережная Дежнёва, дом 14",
"langs": [],
"longText": "Российская Федерация, Дальневосточный федеральный округ, Чукотский автономный округ, Провиденский район, Провидения, улица Набережная Дежнёва, дом 14",
"parts": [{
"lvl": "postcode",
"name": "",
"lvl-size": 55
}, {
"lvl": "boundary:2",
"names": {
//куча названий России
},
"lnk": "admbnd-2864649470-r60189",
"name": "Российская Федерация",
"lvl-size": 130
}, {
"lvl": "boundary:3",
"names": {
"name:sv": "Fjärran österns federala distrikt",
"name:en": "Far Eastern Federal District",
"name:ru": "Дальневосточный федеральный округ",
"name:ja": "極東連邦管区",
"name:es": "Distrito federal del Lejano Oriente",
"name:de": "Föderationskreis Ferner Osten",
"short_name": "ДФО",
"name:vi": "Vùng liên bang Viễn Đông",
"name:pt": "Distrito Federal Oriental",
"name:fr": "District fédéral extrême-oriental",
"name:uk": "Далекосхідний федеральний округ",
"name:nl": "Federaal District Verre Oosten",
"name:zh": "遠東聯邦管區",
"name:it": "Distretto Federale dell'Estremo Oriente",
"name:pl": "Dalekowschodni Okręg Federalny",
"name": "Дальневосточный федеральный округ"
},
"lnk": "admbnd-2969582277-r1221185",
"name": "Дальневосточный федеральный округ",
"lvl-size": 120
}, {
"lvl": "boundary:4",
"names": {
"name:sv": "Tjuktjien",
"name:en": "Chukotka Autonomous Okrug",
"name:ru": "Чукотский автономный округ",
"name:ja": "チュクチ自治管区",
"name:es": "Chukotka",
"name:de": "Autonomer Kreis der Tschuktschen",
"short_name": "Чукотка",
"name:vi": "Khu tự trị Chukotka",
"name:fr": "Tchoukotka",
"name:uk": "Чукотський автономний округ",
"name:nl": "Tsjoekotka",
"name:zh": "楚科奇自治区",
"name:it": "Circondario autonomo della Čukotka",
"name:pl": "Czukocki Okręg Autonomiczny",
"int_name": "Chukotka Autonomous Okrug",
"name": "Чукотский автономный округ"
},
"lnk": "admbnd-4289483775-r151231",
"name": "Чукотский автономный округ",
"lvl-size": 110
}, {
"lvl": "boundary:6",
"names": {
"name:ru": "Провиденский район",
"name": "Провиденский район"
},
"lnk": "admbnd-2373015928-r1949882",
"name": "Провиденский район",
"lvl-size": 90
}, {
"lvl": "place:town",
"names": {
"name": "Провидения"
},
"lnk": "plcbnd-3753535756-w129289823",
"name": "Провидения",
"lvl-size": 70
}, {
"lvl": "street",
"strtUID": -30263303,
"lnk": "hghway-1683350308-w129293134",
"names": {
"name": "улица Набережная Дежнёва"
},
"name": "улица Набережная Дежнёва",
"lvl-size": 20
}, {
"lvl": "hn",
"names": {},
"lnk": "adrpnt-0642964090-w129096772",
"name": "дом 14",
"lvl-size": 10
}],
"addr-scheme": "regular"
}],
"metainfo": {
"id": 129096772,
"type": "way",
"fullGeometry": {
"type": "Polygon",
"coordinates": [
[
[-173.2301084, 64.4217729],
[-173.229167, 64.4220204],
[-173.2293185, 64.4221278],
[-173.2298729, 64.421982],
[-173.2299223, 64.4220171],
[-173.2302113, 64.4219379],
[-173.2300846, 64.4218517],
[-173.2301819, 64.421825],
[-173.2301084, 64.4217729]
]
]
}
},
"geometry": {
"type": "Point",
"coordinates": [-173.22972832, 64.42195376]
}
}
Промежуточный формат хранения данных — json (запакованный gzip). Это, во-первых, сильно упрощает дебаг. Я могу смотреть промежуточные результаты при помощи простых (z)cat, (z)grep. Во вторых, упрощает жизнь сторонним разработчикам, если таковые найдуться.
На выходе я генерирую csv для связки postgis + sphynx (возможно, постгис тут лишний, но на нем в этой связке удобно делать обратный геокодер) и json для elasticsearch (обратный геокодинг можно выполнить средствами самого elasticsearch).
На обработку РФ уходит примерно 2 часа, при 6 Гб оперативки и примерно 5Гб дискового пространства. Можно ужаться в меньший объем ram пожертвовав временем. Известные мне аналоги тратят двое суток.
Многие участки можно кастомизировать (количество расширений я планирую увеличить) используя свои реализации классов, предавая их из расширений на groovy.
Приложение для обработки данных представляет собой 1 исполняемый jar и не требует от вас установки дополнительных зависимостей.
На данный момент у меня довольно мудреный синтаксис для запуска, с множеством параметров командной строки, в дальнейшем я планирую добиться запуска в 1 строку java -jar gazetteer.jar russia.config а еще лучше в качестве рабочей ноды кластера.
Ссылка на велосипед github.com/kiselev-dv/gazetteer
Я не силен в поисковых технологиях, поэтому сам поиск по загруженным в elasticsearch пока хромает. Если на хабре есть те, кому интересно поработать с такого рода данными и поэкспериметировать с настройками поисковика по геоданным — добро пожаловать.
Проект состоит из двух частей.
Gazetteer — обработка данных.
GazetteerWeb — апи поверх elasticsearch (пока на tomcat — в дальнейшем планирую использовать netty)
Автор: kiselev_dv
