Пушкин как дерево

by Max Galkin

Портрет Пушкина. Тропинин В.А. 1827 год

Пока вся прогрессивная общественность ахала-охала и топтала память ГКЧП, а Матвиенко устраивала цирк с конями под названием «выборы», я занимался написанием робота-пушкиниста.

Что я для этого покурил? А покурил я прежде всего первые слайды Стэнфордского курса «CS 276 Introduction To Information Retrieval». В них, в качестве примера небольшой поисковой системы, приводится ссылка на Shakespeare Search, где ценители могут исследовать стихи Шекспира в необычной форме дерева, построенного на наиболее частых началах строк. Скажем, чаще всего Шекспир начинал строку словом «And», после него чаще всего ставил слово «I», ну и так далее, например, можно дойти до строки And I with them the third night kept the watch; и получить ссылку на «Гамлета». Забавно.

Я решил немного поизучать теорию поиска информации1, а для начала написать робота, который бы построил такое же дерево, но для Александра, нашего, Сергеевича. Что характерно, Александр Сергеевич тоже был любитель начать строку словом «и»:

Посмотреть дерево стихов Пушкина

Работает моё дерево быстрее, поскольку страничка полностью статическая, всё просчитано заранее. Правда, нет возможности дать ссылку на частично раскрытое дерево, хотя такую возможность несложно добавить.

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

Всего проанализировано 43406 строк из 837 стихотворений.

Дольше всего робот ходил по ссылкам и скачивал все эти стихотворения: 680 секунд.

Создание обратного индекса заняло 3 секунды. В индексе 35102 терминов (то есть различных слов).

Затем еще 75 секунд ушло на запросы к этому индексу для построения дерева. На каждом уровня взято не более 20 наиболее часто встречающихся результатов. Всего сделано 936 запросов, что значит в дереве 936 вершин, а в среднем на запрос к индексу ушло 80 мс.

Затем еще 0.2 секунды ушло на преобразование дерева в HTML и вывод результатов.

P.S. В программе есть один случай, для которого известно, что дерево строится некорректно. Сможете ли вы его обнаружить?

  1. как говорится, ни с того, ни с SEO []