Это выпуск подкаста «Запуск завтра», который (как и мы) выходит при поддержке «Яндекс Практикума». Отвлекитесь от забот и послушайте, как с помощью математики и продвинутых алгоритмов можно ужать терабайты данных и сделать из них полезный продукт.
О герое
Герой выпуска — разработчик Юрий Мельничек. Десять лет назад он придумал приложение для смартфонов 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-файл можно использовать только как поток реки, в котором ты вылавливаешь то, что тебе надо. Если ты захочешь всю эту воду собрать, то случится наводнение — резервуара твоего жёсткого диска не хватит.
Файл обрабатывается, из него вытаскивается нужная информация, строятся индексы, потом на этих индексах строятся ещё индексы. Запускаются алгоритмы для поисков и маршрутов. На выходе получаются сильно сжатые файлы с картой, которые предназначены только для чтения.
Слушайте полную версию подкаста
В конспект не вошёл разговор о проекциях Земли на плоскость и трансформации координат из плоскости в «ленту». Будет интересно тем, кто хочет глубже понять, как математика может пригодиться в программировании.
