Инженерный журнал
Как Mapsake создает свою офлайн-географическую базу данных для путешествий.
Преобразование координат фотографии в страну, регион, город и аэропорт требует больше, чем просто поиск ближайшего места. Вот как Mapsake объединяет открытые данные о местах, геометрию границ, детерминированные правила и локальную индексацию.
Координаты еще не являются местом.
Фотография может содержать широту и долготу с впечатляющей точностью. Однако эти два числа не говорят о том, находилась ли камера в Японии, префектуре Киото, Киото или в международном аэропорту Кансай по дороге домой. Mapsake нуждается в этой иерархии, прежде чем точку можно будет считать полезной записью о путешествии.
Компонент, отвечающий на эти вопросы, – это географический справочник: структурированный каталог географических названий. Mapsake включает свой географический справочник в приложение, наряду с границами, используемыми для отображения и тестирования стран и регионов первого уровня. Поиск, ручная отметка, импорт фотографий, истории о местах, статистика паспортов, достижения и даже несколько представлений друзей зависят от него.
Было бы проще отправлять все координаты в веб-геокодер. Однако это замедлило бы импорт больших фотографий, сделало бы его более зависимым от сети, сложнее в воспроизведении и менее приватным. Создание оффлайн-маршрута потребовало больше инженерных усилий на начальном этапе, но это дало Mapsake стабильный географический словарь, который работает одинаково в самолете, дома и спустя годы после изменения исходного набора данных.
Это история о том, как был создан этот слой, где точки и линии не совпадают, и почему «ближайший город» – это только начало правильного ответа.
Четыре открытых набора данных, четыре разные задачи
Ни один источник не содержит всю необходимую информацию для Mapsake, поэтому процесс сборки объединяет четыре вида открытых данных:
- GeoNames. предоставляет страны, административные регионы первого уровня, населенные пункты, стабильные идентификаторы, альтернативные названия, координаты и население.
- OurAirports предоставляет аэропорты, коды IATA и ICAO, названия, муниципалитеты и координаты.
- Natural Earth предоставляет геометрию границ стран и единиц admin-1, а также полезные точки для подписей на карте.
- Небольшой слой, принадлежащий Mapsake, содержит записи о решениях, принятых в отношении продукта, такие как поддерживаемые режимы подсчета стран, псевдонимы и исправления, которые нельзя безопасно вывести из общего источника.
Каждый источник хорош в своей области. GeoNames знает, что город принадлежит к региону и стране, но координаты города – это точка, а не граница. Natural Earth знает, где нарисован полигон, но его идентификаторы не всегда четко соответствуют идентификаторам GeoNames. OurAirports знает, что KLAX и LAX относятся к одному и тому же аэропорту, но это не иерархия всех мест вокруг аэропорта.
Скрипт сборки загружает и кэширует исходные файлы, нормализует их, проверяет связи и создает два готовых артефакта: базу данных SQLite только для чтения и упрощенную геометрию GeoJSON. Приложение распространяет эти результаты. Приложение не загружает глобальную базу данных при первом запуске и не зависит от доступности исходных сайтов во время поездки.
Создание сгенерированных артефактов также обеспечивает воспроизводимость сборки. Скомпилированная версия имеет известную географическую модель мира. Обновление исходного кода – это намеренное изменение кода, которое можно протестировать и проверить, а не невидимое изменение на стороне сервера, которое может изменить карту пользователя в одночасье.
Преднамеренно простая база данных SQLite.
В первом справочнике содержалось 252 стран, 3,861 регионов, 33,744 городов и 4,564 аэропортов объемом около 14 МБ. Он использовал библиотеку SQLite, уже предоставляемую операционной системой, и небольшой локальный обертку, а не более сложную базу данных.
Схема намеренно проста. Континенты содержат страны. Страны содержат регионы. Регионы содержат города. Аэропорты содержат коды стран и координаты. Стабильные идентификаторы источников становятся идентификаторами, хранящимися с отметкой Mapsake: ISO alpha-2 для страны, код административного деления GeoNames для региона, идентификатор GeoNames для города и код IATA для аэропорта.
Mapsake также денормализует читаемое имя и происхождение в каждую сохраненную метку. Эта дубликация полезна. Личная запись о путешествии должна оставаться читаемой, если более поздний справочник переименует место, удалит запись или не будет доступен во время экспорта. Идентификатор используется для сопоставления; снимок сохраняет данные пользователя в автономном режиме.
SQLite хорошо подходит для этой задачи, поскольку база данных создается один раз и многократно запрашивается. Она поддерживает индексы, транзакции во время сборки и полнотекстовый поиск без использования отдельного сервиса. Приложение открывает встроенный файл только для чтения, поэтому нет риска миграции данных и нет возможности повреждения данных из-за прерванной записи.
Поиск – это не просто проверка наличия текста.
Ручная разметка начинается с одного поля поиска, охватывающего континенты, страны, регионы, города и аэропорты. Поиск «san» должен находить значимые города, а не малоизвестные записи; «LAX» должен находить аэропорт; а имя, набранное без диакритических знаков, также должно работать.
Эта сборка создает таблицу FTS5 с отображаемыми именами, выбранными альтернативными именами, кодами, родословной, координатами, типом и значением важности. Токенизатор Unicode удаляет диакритические знаки для сопоставления. Во время запроса Mapsake игнорирует регистр и диакритические знаки, удаляет символы, которые могут стать синтаксисом полнотекстового поиска, добавляет префиксное сопоставление к каждому токену и ранжирует точные имена выше префиксов и общих совпадений.
Важность определяет порядок оставшихся элементов. Континенты и страны должны отображаться выше, чем деревни с похожими названиями. Население города придает значимым местам правильный вес. Большие аэропорты имеют более высокий рейтинг, чем маленькие, если текстовое соответствие в противном случае сопоставимо.
Альтернативные названия намеренно ограничены. GeoNames может предоставить очень длинный многоязычный список для популярного места. Копирование каждого варианта написания в индекс устройства добавит шум и увеличит размер. Система сохраняет ограниченный набор полезных вариантов и отдельно сохраняет исходное отображаемое имя, отделяя его от формы поиска.
Результаты поиска соответствуют модели GazetteerPlace, используемой для иерархической навигации. Пользователь может искать напрямую или просматривать континент, страну, регион и город, не создавая две разные географические системы, которые могут не совпадать.
Линии отвечают на другой вопрос, чем точки.
Первая функция определения местоположения фотографии выбирала ближайший город и наследует страну и регион этого города. В густонаселенных районах это часто выглядит идеально. Вблизи границы это может быть неверно, и это трудно заметить.
Представьте фотографию, сделанную прямо у границы штата Монтана, при этом ближайший населенный пункт в базе данных находится за границей, в штате Северная Дакота. Расчет ближайшего города работает правильно, но результат не соответствует административному региону, где была сделана фотография. Аналогичная проблема возникает на международных границах, в анклавах и вдоль береговой линии, где отсутствие близлежащих населенных пунктов приводит к неточным результатам.
Геометрия границ определяет, находится ли объект внутри границы, а не его близость. Mapsake декодирует страны и полигоны admin-1 Natural Earth, проверяет, какие полигоны содержат координату, и использует этот результат для защиты назначения страны и региона. Затем он может искать ближайший город, ограниченный страной или регионом полигона.
Это создает полезное разделение труда:
- Содержащая полигон область определяет административную территорию.
- Иерархия справочника предоставляет стабильные идентификаторы и названия.
- Ограниченный поиск ближайшего города предоставляет полезную информацию о местоположении, не выходя за установленные границы.
- Проверка ближайшего аэропорта добавляет аэропорт только в пределах строго заданного расстояния.
Данные о маршрутах и справочник местностей не являются достаточными по отдельности. Вместе они преобразуют координаты в надежную цепочку.
Аудит admin-1 выявил систематические несоответствия.
Полигоны стран и регионов взяты из разных слоев Natural Earth, и идентификаторы слоя регионов не всегда совпадали с GeoNames. Некоторые несоответствия были очевидными, в то время как другие приводили к правдоподобным, но неверным результатам.
В одной из ранних таблиц преобразований провинции Квебек была ошибочно связана с географическими данными провинции Нью-Брансуик. Другим функциям не хватало кода, они содержали код из соседней системы или представляли административную единицу иначе, чем в справочнике. Визуальный осмотр карты мира не всегда позволял надежно обнаружить все эти ошибки.
Новая модель состояния рассматривает города как оракул. Для каждого кандидата в полигон она запрашивает, какие города из региона Gazetteer фактически находятся внутри него. Существующие коды Natural Earth проверяются, а не используются слепо. Функции, которые не проходят проверку, могут быть пространственно переназначены, разделены или исключены. Сгенерированный вывод затем использует точные идентификаторы регионов, которые уже присутствуют в SQLite.
Это практическая форма кросс-датасетного тестирования. Полигон, который заявляет, что является регионом, должен содержать убедительный набор городов, которые также заявляют, что находятся в этом регионе. Когда два источника не согласны, сборка предоставляет доказательства, а не тихо выбирает значение, которое было загружено первым.
В ходе одного из аудитов были выявлены особые случаи, такие как зависимые территории, включенные в географию родительской страны. Mapsake исправляет небольшое количество таких случаев, чтобы фотография могла быть сопоставлена с той же страной, которую понимают справочник и настройки подсчета стран.
Более четкие линии без передачи исходного размера мира.
Первая версия Atlas использовала слой данных о границах стран Natural Earth в 1:110 миллионах. Она была компактной и быстрой, но при добавлении Mapsake более подробных карт, историй о местах и региональной информации, береговые линии стали заметно менее четкими.
Карта была перемещена на слой 1:10 миллионов. Этот источник содержит гораздо больше деталей, поэтому его объединение и рендеринг без изменений увеличило бы объем хранилища, время декодирования, построение наложений и перерисовку. Скрипт сборки упрощает каждое кольцо с помощью алгоритма Douglas-Peucker с погрешностью примерно 0.004 градуса, а затем округляет координаты до стабильной точности.
Полученный файл страны имеет размер около 6.5 МБ. Он сохраняет полезные детали береговой линии на уровнях масштабирования, которые Mapsake отображает, при этом удаляются вершины, которые попадают на пиксели, которые кажутся одинаковыми. Геометрия Admin-1 проходит аналогичный путь проверки и упрощения.
Упрощение имеет ограничение по корректности: меньший полигон должен принимать те же решения для реальных координат фотографий. Впоследствии, тестовые примеры намеренно размещают точки вокруг границ и сравнивают оптимизированное определение пересечений с зафиксированным эталонным значением. Более быстрые линии полезны только в том случае, если они все еще правильно определяют, находится ли объект внутри полигона.
Расширение от городов 34,000 до 234,000.
В первой базе данных использовались города GeoNames с населением более 15,000. Это сделало пакет компактным, но это привело к тому, что поездки в сельскую местность, на небольшие острова, в небольшие городки и многие домашние локации имели слишком далекую метку.
Mapsake позже начала использовать данные GeoNames. Города500, охватывает населенные пункты с населением примерно 500 человек и административные центры. Таблица городов увеличилась примерно в семь раз, до примерно 234,000 записей, а размер встроенной базы данных увеличился примерно с 14 МБ до примерно 69 МБ.
Эта сделка была совершена после удаления App Clip. Ограничение на загрузку Clip было самой сильной причиной ограничения размера базы данных. После того, как основным потребителем стало основное приложение, более широкое покрытие было более ценным, чем сохранение искусственного ограничения на небольшой город.
Индекс полного текста выборочно относится к альтернативным названиям незначительных мест, а просмотр по регионам ограничивает количество отображаемых элементов. Данные могут быть обширными, не требуя отображения всей таблицы на каждом экране.
Покрытие наиболее важно в тех местах, где геокодер не будет достаточно надежным. Маленький городок в отдаленной местности не должен быть обозначен как город, расположенный в нескольких часах езды, просто потому, что компактный набор данных его не включил.
Поиск ближайшего города стал проблемой производительности.
Изначальный запрос ближайшего города расширял область координат, запрашивал у SQLite расчет взвешенного расстояния для каждого кандидата, создавал временную сортировку и возвращал ближайшую строку. Это было легко понять и достаточно точно, но библиотека 82,000 фотографий превратила небольшую стоимость запроса в секунды повторяющейся работы при импорте, создании воспоминаний, генерации карты и создании Constellations.
Первое улучшение добавило узкий зонд 0.4 градуса перед более широкими альтернативными вариантами. В густонаселенных районах город обычно находился из гораздо меньшего набора кандидатов. Механизм кэширования и постоянный кэш географических ячеек также предотвращали повторение одинаковой работы для фотографий поблизости.
Наибольшее улучшение заключается в загрузке числовых координат городов 234,000 в индекс в памяти, отсортированный по широте. Двоичный поиск находит срез внутри текущего диапазона широты, ограниченный цикл проверяет долготу и взвешенное расстояние, и извлекается только выигрышная строка из SQLite. Небольшой кэш записей обеспечивает быструю повторную обработку выигрышных записей.
Поведение расширения не изменилось. Оптимизированная функция по-прежнему выбирает ближайший город в первом непустом окне поиска, включая детерминированное разрешение конфликтов. Копия старого пути SQL, предназначенная только для тестирования, проверяет сотни координат, расположенных на границах, на точное соответствие идентификаторам.
В симуляторе время получения ближайшего города в средней партии сократилось с 2.11 секунды до 5.2 миллисекунд. Время выполнения на физическом iPhone сократилось с 3.06 секунды до 6.35 миллисекунд. Эти улучшения затронули несколько функций, поскольку глоссарий является общей инфраструктурой, а не частной реализацией экрана импорта.
Обнаружена ошибка, связанная с перекрывающимися полигонами.
Механизм проверки эквивалентности производительности выявил ошибку, которая существовала до оптимизации. Некоторые полигоны admin-1 намеренно перекрываются, особенно регионы столиц внутри окружающего региона. Берлин и Бранденбург, Сеул и провинция Кёнгидо, а также Киев и его область – примеры.
Старый метод проверки соответствия принимал первый найденный совпадающий полигон из словаря Swift. Порядок итерации по словарю меняется между процессами, поэтому одна и та же координата может получить другую область после перезапуска приложения.
Mapsake теперь сортирует перекрывающиеся варианты по площади полигона и позволяет победить наименьшему и наиболее точному объекту. Реализация соответствует этому правилу. Фиксированный тест с фотографией 82,000 должен давать нулевые различия между холодным и горячим путем получения данных, прежде чем будет принята оптимизация геометрии.
Этот баг – хорошее напоминание о том, что «внутри полигона» не всегда означает «да» или «нет». Географические данные содержат анклавы, вложенные столицы, антимеридианы, многоугольники, отверстия, спорные границы и соглашения об источниках. Детерминированная политика так же важна, как и алгоритм определения принадлежности точки к многоугольнику.
Оффлайн-режим – это функция конфиденциальности и функция продукта.
Функция импорта фотографий в Mapsake позволяет обрабатывать большую библиотеку фотографий без отправки их координат в сторонний сервис геолокации. Это защищает конфиденциальные данные о местоположении, исключает плату за каждый запрос, предотвращает ограничения скорости и делает процесс предсказуемым.
Он также делает редактирование более согласованным. Ручной поиск, импорт фотографий, карты Passport, достижения, снимки друзей, сопоставление штампов и истории мест говорят на одном языке, потому что они используют одни и те же стабильные идентификаторы мест. Аэропорт, импортированный из журнала рейсов, может быть дедублирован с тем же аэропортом, обнаруженным рядом с фотографией. Город, найденный с помощью поиска, может соответствовать городу, используемому в Then & Now.
Сборка не рассматривается как идеальная или постоянная. Информация об источниках отображается в приложении. Скрипты сборки хранятся рядом с кодом. Известные исправления явно указаны. Тестовые данные для бенчмаркинга защищают поведение в сложных координатах. Обновление географической базы данных – это событие, связанное с выпуском, которое имеет проверяемые последствия.
Что бы я сохранил, если бы пересобрал это?
Наиболее надежные решения были не отдельными алгоритмами. Это были границы ответственности:
- Используйте точки для названий, стабильных идентификаторов, поиска и иерархии.
- Используйте линии и многоугольники для ограничения.
- Создайте артефакт продукта только для чтения вместо разбора четырех форматов на устройстве.
- Сохраняйте читаемый снимок с данными пользователя, сохраняя при этом идентификатор источника для сопоставления.
- Сделайте общий путь для работы в автономном режиме детерминированным, прежде чем делать его быстрым.
- Поддерживайте медленную демонстрационную версию достаточно долго, чтобы доказать, что оптимизированный вывод эквивалентен.
Справочник (gazetteer) начинался как функция поиска. Он стал одной из ключевых систем Mapsake, потому что почти каждая продвинутая функция в конечном итоге должна отвечать на один и тот же простой вопрос: что это за место?
Чтобы получить правильный ответ, необходимо понимать, что география – это не просто одна база данных или один сложный запрос. Это тщательное согласование между названиями, точками, линиями, правилами продукта и ожидаемой пользователем записью о путешествии.