Как мы фирмы российские исследовали



    СКБ Контур — федеральный разработчик программного обеспечения с 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. Скачать получившееся приложение для Айпада можно по ссылке.

    На закуску видеозапись процесса исследования графа на планшете, записанное с эмулятора, с раскрытием окрестностей и динамической подгрузкой новых фирм. Смотреть, конечно, в наилучшем качестве.



    Мы будем очень рады любому фидбеку всех заинтересовавшихся читателей :-)
    • +11
    • 11,2k
    • 8
    СКБ Контур 109,24
    Компания
    Поделиться публикацией

    Вакансии компании СКБ Контур

    Комментарии 8
    • +1
      Страшная база, на самом деле.
      • 0
        Пользуюсь Контур.Фокусом, как скоро там ждать эту радость? )
        • 0
          Тем быстрее, чем настойчивее этого будут требовать пользователи )
          • 0
            Поясню: Контур Лабс занимается исследованиями в целом независимо от команд Контура, производящих коммерческие продукты. В большинстве случаев наши исследования ложатся в основу дополнительных фич продуктов или даже каких-нибудь новых, только запускаемых, сервисов. Однако в случае с Фокусом нам пока не удалось окончательно убедить команду и ее руководство в полезности подобных инструментов. Именно поэтому явно выраженное желание пользователей может помочь нам ускорить этот процесс убеждения :-)
        • 0
          На iPad Mini 2 с iOS 7.0.4 приложение весело крашится при попытке запустить.
          • 0
            Попробую раздобыть iPad Mini 2 и понять, что там происходит.
          • 0
            Я правильно понимаю, что вы просто рассказали, что сделали, но воспользоваться графами нельзя? То есть хотелось бы посмотреть данные по некоторым организациям и не пойму, где это можно сделать. Можете ли пояснить?

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое