СКБ Контур — федеральный разработчик программного обеспечения с 1988 года. Возможно, вы слышали о Контуре как о компании, разрабатывающей продукты для малого и среднего бизнеса. Но наше подразделение занимается совершенно другим. Или, если сказать точнее, подходит к этому с другой стороны. Мы называемся “Контур Лабс” и занимаемся научными и исследовательскими проектами.
Что вы делаете, если у вас есть несколько десятков гигабайт данных? Мы в первую очередь стараемся эти данные каким-то образом нарисовать — кажется, в визуальном отображении могут проявиться связи, которые не были видны непосредственно.
Именно так мы поступили с данными о более чем 20 миллионах юридических лиц, официально зарегистрированных в России. ЕГРЮЛ (единый государственный реестр юридических лиц) предоставляет такую информацию всем желающим (а Контур на её основе даже сделал свой сервис Контур.Фокус). Для каждой фирмы и индивидуального предпринимателя мы знаем целую гору информации: дату регистрации, учредителей (в том числе и иностранных), их доли при составлении начального капитала, несколько видов названий (полное, сокращенное, английское), адреса, телефоны…
Самое интересное, что мы обнаружили в этой куче малоструктурированных данных — это различного вида связи между фирмами. Для начала мы любовались связями, показывающими, кто кого организовал. Этого нам показалось мало, и мы связали фирмы, имеющие одного и того же человека в директорах. Мы серьезно подсели на это дело, и через неделю у нас уже были связи между фирмами, имеющими одинаковый юридический адрес или одинаковый телефон.
Сразу же появился вопрос, как лучше всего изучать фирмы и их связи с другими. Как найти фирмы, которые имеют одинаковый адрес с теми, кого учредил Газпром (а “детей” у него больше сотни)? Конечно нарисовать! Так как фирмы со связями, проложенными между ними, образуют некоторый граф, мы в первую очередь обратили внимание на визуализаторы графов.
Если вы когда-нибудь занимались визуализацией графов, то знаете ограничения соответствующих алгоритмов и инструментов. Речь идёт в лучшем случае о десятках тысяч вершин, максимум о сотне, и то это уже, скорее всего, будет совсем не в реальном времени. А в нашем распоряжении были десятки миллионов вершин, ещё больше рёбер, да ещё и мета-информация о типах связей! Надо было что-то делать, и мы решили реализовать возможность смотреть наш граф маленькими кусками, ведь в каждый момент нас интересует только окрестность какой-то конкретной фирмы.
Мы взяли Gephi (это программа для отрисовки графов и не только, подробности можно найти на их сайте) и написали для него плагин, позволяющий рассматривать определенные части нашего большого графа “под лупой”. По пути ещё и сделали пул-реквест с исправлением баги в плагине для Gephi, который не позволял нам передавать по сети русские названия фирм. В каждый момент времени мы смотрели только на маленький кусочек, при этом имели возможность добавить к рассмотрению какую-нибудь фирму или даже всех, с кем она соединена связями.
Поиграв с плагином, мы поняли, что этого мало — решать задачи исследования фирм и их окрестностей, используя его, было неудобно. Тогда мы тщательно посовещались и решили, что удобнее всего будет работать с таким графом на тач-устройствах. Только представьте — элегантный тап по экрану, и вы уже изучаете фирмы, связанные с выбранной. Увеличение и уменьшение масштаба с помощью стандартных жестов. Динамическое добавление новых фирм и связей на экран в режиме реального времени. И всё это на планшете, чтобы обнаруженные интересности можно было показывать в дороге или на совещании.
Итак, мы решили разработать приложение для Айпада, которое будет подхватывать с сервера информацию об окрестности фирм, размещать ее на экране планшета и предоставлять пользователю удобный интерфейс для работы с этими данными.
Сразу же возникло множество интересных задач. Расскажем обо всех по порядку.
Задача 1. Сервер
Серверная часть нашего приложения проста и сложна одновременно. Проста, потому что ей не нужно почти ничего делать, только хранить и отдавать информацию о фирмах, смежных с заданной, а также отдавать различную мета-информацию о компаниях и связях, такую, как учредители фирмы, дата создания, адреса, телефоны и прочее-прочее-прочее. Сложна, потому что эту простую задачу необходимо делать быстро и эффективно, ведь хочется обрабатывать множество клиентов в режиме реального времени, и делать это ценой не очень большого количества ресурсов.
Мы решили отказаться от использования больших и монструозных баз данных, а написать что-нибудь свое — маленькое и быстрое. Взяли C++, добавили немного Python’а, и вот у нас есть то, что нам было нужно — быстрый и легко масштабируемый сервер для хранения фирм и отношений между ними. Все данные реально хранятся на диске, в оперативную память для быстрого доступа загружаются только индексы, что делает возможным при необходимости запустить сервер на обычной машине любого разработчика или пользователя.
Так как в наших головах все время существовала мысль о многообразии клиентов под разные платформы, то в качестве транспорта мы выбрали HTTP, а в качестве формата передаваемых данных — JSON. Это несколько замедляет скорость передачи и обработки данных, однако делает намного более удобной работу с сервисом на разных клиентах.
Задача 2. Удобный интерфейс
Мало кто решается сделать приложение, показывающее на экране только лишь граф. Из найденных нами подобных приложения для планшетов самыми похожими оказались Wikiweb и Solyaris. Но ни одно из них не решало задач, подобных тем, что стояли перед нами. Как показывать гору текстовой информации о конкретной фирме по желанию пользователя? Что делать с окружением, если в нём более пятисот фирм? А если больше тысячи?
Мы перепробовали несколько разных вариантов интерфейсных решений. Некоторые мы отбрасывали сразу, некоторыми давали попользоваться обычным людям. Ключевой характеристикой, которую мы выделили для себя на этих этапах — это минимизация текстовой информации на главном экране, который содержит непосредственно граф с фирмами. Ненужная в большинстве случаев подробная информация должна быть спрятана по умолчанию, а все управления нужно сделать визуальными и наглядными.
С проблемой большого количества фирм-соседей решили поступить следующим образом: в случае попытки показать непомерно большую окрестность мы отобразим пользователю удобный поиск, в котором все фирмы-соседи разделены на группы по некоторой “важности” фирмы. “Важностью” в данном случае выступил размер фирм, количество известных с ней связей.
После рисований разных вариантов интерфейсов получилось что-то такое:
Задача 3. Клиентское приложение
К приложению, которое будет рисовать картинку со связями между фирмами, было несколько требований. Но одно из них было принципиальным — приложение должно летать. Во всех смыслах этого слова — оно должно работать быстро, а все изменения в отображаемой структуре должны происходить плавно. Поэтому при разработке приложения под Айпад мы использовали только нативный код, написанный на Objective-C и C++. За рисование отвечает Cocos2D, он справляется с этим хорошо, поэтому тут ничего интересного нет.
Самое интересное же находится, как всегда, под капотом. Как мы уже обсуждали, то, что отображается на экране в каждый момент времени есть не что иное, как обыкновенный граф, со своими вершинами и ребрами. Для того, чтобы пользователю приложения было хоть что-нибудь понятно среди десятков и сотен отображенных в текущий момент вершин, необходимо решить задачку хорошего изображения графа на плоскости. Понятно, что идеала в решении данной задачи добиться невозможно (его просто-напросто не существует), однако мы попытались :)
Для решения задачи раскладки графа на плоскости было решено использовать семейство алгоритмов Force Atlas и, в частности, его модификации, разработанные французским ученым Мэтью Джэкоми (Mathieu Jacomy). Идея алгоритмов Force Atlas заключается в том, что на место каждой вершины нашего графа мы помещаем маленький грузик соответствующего веса, а все ребра графа заменяем на пружины с определенным коэффициентом упругости. Вся система при этом приходит в действие, а через некоторое время останавливается. Полученный процесс записывается и может быть показан в несколько замедленном варианте для красивой анимации постепенного изменения положения вершин на изображении.
Нами были найдены реализации подобных алгоритмов на Java и JavaScript, но нам нужен был поистине очень быстрый код. Был найден так же порт Java-реализации на C++, но количество зависимостей в нем было неимоверно велико и пугало нас. Айпад не отличается большой мощностью, особенно, по сравнению с настольными компьютерами, поэтому нам нужно было что-то действительно легковесное.
Добавив к C++ неделю времени, смешав это всё с Objective-C мы получили свою реализацию Force Atlas, которая устраивала нас по скорости и гибкости. Она оставалась гибко настраиваемой, но при этом успевала в режиме реального времени раскладывать на экране планшета сотни вершин.
Вот несколько скриншотов того, что у нас получилось (по клику — полноразмерные версии):
Что у нас получилось?
Мы бы очень хотели показать публике итоговую версию приложения. Но, к сожалению, сделать мы это не можем, так как данные, использованные для него, составляют коммерческую идею Контур.Фокуса. Чтобы все-таки показать красоту динамичной раскладки графа на плоскости, мы на коленке набросали приложение, оперирующее с данными об актёрах и фильмах. Данные эти мы взяли из всем известной базы IMDB, скачав их с одного из их FTP-серверов.
Вершинами графа стали актёры и фильмы, ребро мы проложили в том случае, если актёр сыграл в этом фильме. Чтобы не засорять данные (а также чтобы избавиться от фильмов для взрослых), мы выбросили из базы все фильмы с рейтингом строго ниже 7. Скачать получившееся приложение для Айпада можно по ссылке.
На закуску видеозапись процесса исследования графа на планшете, записанное с эмулятора, с раскрытием окрестностей и динамической подгрузкой новых фирм. Смотреть, конечно, в наилучшем качестве.
Мы будем очень рады любому фидбеку всех заинтересовавшихся читателей :-)
Автор: andgein
