Как работает приложение Maps.me

Как работает приложение Maps.me

Разговор с создателем технологии

Это выпуск подкаста «Запуск завтра», который (как и мы) выходит при поддержке «Яндекс Практикума». Отвлекитесь от забот и послушайте, как с помощью математики и продвинутых алгоритмов можно ужать терабайты данных и сделать из них полезный продукт.

О герое

Герой выпуска — разработчик Юрий Мельничек. Десять лет назад он придумал приложение для смартфонов MAPS.ME и продал его холдингу Mail.ru Group. Затем создал компанию, которая занималась нейронными сетями, и продал её Google Research. Вырученные деньги Юрий инвестирует в стартапы в сфере Machine Learning.

Как появилась идея первого стартапа

Я бы не сказал, что на 100% придумал MAPS.ME. Просто уловил актуальные мысли и тенденции на заре, когда только появился iPhone. 

Я тогда работал в Google, и у меня было несколько проблем с использованием Google Maps. Одна из них заключалась в том, что Беларусь была представлена только двумя дорогами и государственной границей. А я сам из Беларуси, и мне хотелось, чтобы у страны была красивая карта. 

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

Мы взяли маленький кусочек Минска, где есть железнодорожный вокзал, дорога, здания — то есть разнообразные объекты. И сделали небольшой прототип, начали его рисовать. Это было даже не приложение. История называлась OMIM — one month in Minsk. Мы собрались тогда на один месяц в Минске, чтобы поработать над проектом, не предполагая, что этот своеобразный хакатон выльется в полноценное приложение и годы разработки.

В чём технический прорыв стартапа

В те годы и «Яндекс», и Google хранили данные для интернет-карт на своих серверах и обрабатывали их там, а на телефон присылали готовые отрисованные картинки. Как это работает: когда мы просматриваем карту на телефоне и что-то ищем — мы делаем запрос, который отправляется на сервер и возвращается назад в виде картинки.

Сделав прототип MAPS.ME, мы поняли, что можно хранить и отрисовывать карту прямо на телефоне. Эта идея казалась безумной, поскольку никто не знал, как обрабатывать множество данных на медленном телефоне. Мы придумали как. 

Откуда в интернет-картах берутся данные

У Google и «Яндекса» — из своих источников данных, у MAPS.ME — из сервиса Open Street Map. Обычно данные хранятся у поставщиков карт, которые их покупают у нескольких провайдеров, а затем объединяют, склеивают и сшивают вместе. 

На момент появления MAPS.ME мало кто считал, что карта города должна быть в общем доступе и любой человек может пользоваться этими данными. Сейчас интернет-карты сами собирают данные. Это можно делать из машин, которые снимают съёмку street view — панорамные карты улиц, откуда через распознавание можно вытащить названия магазинов. Есть концепция, как у 2GIS. У них огромная армия людей, которые ходят по улицам, сверяются, вручную редактируют карту, заодно разговаривают с владельцами бизнеса и продают услуги 2GIS.

Что такое Open Street Map

Это такая «Википедия», но в мире карт. Open Street Map — это мировое сообщество, где люди все вместе рисуют карту. В основе общества лежит важная с точки зрения цивилизации идея: знание о том, как устроен наш мир, не должно принадлежать кому-то одному — человеку или компании. Оно должно быть доступным для всех.

У Open Street Map есть совет из ограниченного числа людей, которые принимают решения. И есть множество волонтёров. Они добавляют данные на карту, исправляют ошибки и оставляют пометки о том, что нужно исправить. Взять данные для MAPS.ME из Open Street Map для меня было очевидным решением, потому что у них Беларусь была детально нарисована.

Как появляются дома на интернет-карте

Если говорить про прямоугольники зданий, то большая часть из них появилась благодаря провайдерам спутниковых снимков. Microsoft, Yahoo и другие сказали: «Ребята, мы верим в концепцию Open Street Map, поэтому берите наши спутниковые снимки и по ним рисуйте карты». 

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

Как Open Street Map помогает в случае природной катастрофы

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

Затем подключается Open Street Map Humanitarian Team — команды, специально созданные для таких ситуаций. Они быстро строят интернет-карту, и через сутки у спасателей есть детальная актуальная информация по всем разрушениям и завалам.

О навигации

Сначала в MAPS.ME мы сделали вертолётную навигацию. Это проще всего — вертолёт летит от точки в точку. Хотя там всё равно много работы над пользовательским интерфейсом и тем, как показать маршрут на карте. Потом мы запустили пешеходную навигацию, поскольку пешеходные маршруты проще, чем автомобильные — они на меньшее расстояние. Я вряд ли пойду пешком из Москвы в Берлин.

Автомобильная навигация работает так. Берётся граф дороги, то есть все связи между всеми точками на дороге; дальше выделяются разные маршруты: быстрые дорогие, супербыстрые дороги, автострады. Маршрут строится сначала по автострадам, потом по условно городским дорогам, потом по маленьким улочкам. Это метафорическое описание формального алгоритма, который использует не официальную классификацию дорог, а в ходе обработки данных сам их подразделяет в зависимости от скоростных режимов и взаимного расположения.

При построении маршрута алгоритм добавляет на карту виртуальные дороги, которые представляют для определённых точек самый оптимальный путь. Мы это всё не программировали, а взяли готовый алгоритм, который это строит. Оказалось, что нужны сотни гигабайт оперативной памяти для построения кратчайших автомобильных маршрутов. На телефоне их точно нет. Тогда мы просто сжали эту информацию в сотни раз и сделали так, чтобы она была расположена на флешке телефона.

Как работает сжатие данных в MAPS.ME

В основе MAPS.ME лежит сжатие данных. Нам нужно было решить три задачи одновременно. Во-первых, очень сильно сжать данные. Это, в принципе, нормальная задача. Вторая проблема сложнее. Когда я пакую файлы с помощью архиватора ZIP или RAR, мне ради одного файла нужно распаковать весь архив. Некоторые архиваторы дают опцию распаковывать файлы независимо. Но когда мне нужен даже не один файл, а его маленький кусочек, всё равно нужно распаковать весь архив. Нам же было важно, чтобы при сжатии оставался доступ к любому байту без распаковки. Третья проблема ещё сложнее: всё должно работать внутри мобильного телефона.

Для решения этих задач мы воспользовались областью математики и информатики, которая по-английски называется Succinct Data Structures. Условно, это структуры данных, которые изначально сжаты, и они чуть больше теоретического минимума, необходимого для представления сжатой информации. Это доказывается через алгебру операций. Succinct Data Structures — абсолютно новая на тот момент область, ей не было и десяти лет. 

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

Этот гигантский XML-файл можно использовать только как поток реки, в котором ты вылавливаешь то, что тебе надо. Если ты захочешь всю эту воду собрать, то случится наводнение — резервуара твоего жёсткого диска не хватит. 

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

Слушайте полную версию подкаста

В конспект не вошёл разговор о проекциях Земли на плоскость и трансформации координат из плоскости в «ленту». Будет интересно тем, кто хочет глубже понять, как математика может пригодиться в программировании.

Редактор покаста:

Юля Яковлева

Младший редактор подкаста:

Ирина Хант

Продюсер подкаста:

Павел Боровков

Звукорежиссёр:

Нина Мамотина

Дизайнер обложки подкастов:

Пётр Сутупов

Текст конспекта:

Максим Ильяхов, сервис «Чистовик»

Корректор:

Ира Михеева

Обложка конспекта:

Алексей Сухов

Вёрстка конспекта:

Кирилл Климентьев

Соцсети «Кода»:

Алина Грызлова, Ася Пушкина

Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
Облачный гейминг: что это и как работает
Облачный гейминг: что это и как работает

Как запустить новую игру на слабом железе (и кайфануть)

easy
Симметричное шифрование
Симметричное шифрование

Простое, но очень стойкое.

medium
Всё на костылях, но мы видим, что это работает

Разговор с Ильёй Красильщиком о первых запусках «Лавки».

medium
Разбор: непобедимый алгоритм для игры «4 в ряд»
Разбор: непобедимый алгоритм для игры «4 в ряд»

Разбор видео Code Bullet про трюки в оптимизации алгоритмов

medium
Нужно ли вам учить Swift?

Что особенного в этом языке и чем он выгоден.

easy
Как парень из Томска руководит бэкенд-разработкой в Практикуме
Как парень из Томска руководит бэкенд-разработкой в Практикуме

О CTF-турнирах и пути в Яндекс.

easy
Хранение данных в дереве. Это как вообще?
Хранение данных в дереве. Это как вообще?

Знакомство с Trie: это дерево, которое помогает работать со словарями.

medium
Как работает доставка товаров в России
Как работает доставка товаров в России

Подкаст о «Сберлогистике»

easy
Большой разбор: как ИИ играет в змейку

Современные технологии против игры прошлого века.

medium
Myspace потеряла архивы за 12 лет. Как не потерять свои
Myspace потеряла архивы за 12 лет. Как не потерять свои

Почему так сложно сберечь важные данные и как с этим быть вообще.

easy
easy