Інженерний журнал
Як 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. Деякі невідповідності були очевидними, тоді як інші призводили до правдоподібних, але невірних результатів.
В одній з перших таблиць перетворення провінція Квебек була помилково пов'язана з географічними даними провінції Нью-Брансуїк. Іншим функціям не вистачало коду, вони містили код із сусідньої системи або представляли адміністративну одиницю інакше, ніж у довіднику. Візуальний огляд карти світу не завжди дозволяв надійно виявити всі ці помилки.
Нова модель обробки даних розглядає міста як оракул. Для кожного потенційного багатокутника вона запитує, які міста з відповідного регіону довідника фактично знаходяться всередині нього. Існуючі коди 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, тому що майже кожна просунута функція зрештою повинна відповідати на одне й те саме просте питання: що це за місце?
Щоб отримати правильну відповідь, необхідно розуміти, що географія – це не просто одна база даних або складний запит. Це ретельне узгодження між назвами, точками, лініями, правилами продукту та очікуваним користувачем записом про подорож.