Разбор робота-пушкиниста. Часть первая. Теория.

by Max Galkin

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

Обратите внимание, я улучшил код робота, исправил некоторые ошибки и дописал комментарии, новый код лежит тут

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

 

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

 

Как работает Яндекс

 

Шаги работы простейшей текстовой поисковой системы показаны на следующей блок-схеме.

Шаги работы поисковой системы

 

Давайте разберем каждый шаг подробнее и посмотрим какие сложности возникают в реальной системе. Отдельно синим цветом я буду описывать особенности робота-пушкиниста.

  1. Обработка документов.
    1. Сбор документов. Этот  модуль еще называют web spider или web crawlerНаш робот умеет ходить по ссылкам внутри виртуальной библиотеки и отличать «нужные» ссылки от «ненужных». 
    2. Определить формат документа, кодировку текста, язык текста. В случае с роботом-пушкинистом мы всегда работаем на русском языке в кодировке Win-1251, а документы в формате HTML.
    3. Разбить документ на слова. Во многих случаях это просто, но в зависмости от языка и от контекста могут быть исключения. Например, апостроф в английском языке может требовать отдельной обработки: «it’s» лучше всего разбить на два слова «it is». Точки в аббревиатурах или, например, в названиии игры «S.T.A.L.K.E.R.» следует проигнорировать. Отдельно нужно обработать даты, числа, номера телефонов, для которых используют очень разные форматы. Мы будем считать словами только непрерывные последовательности русских букв, то есть считать любые остальные символы разделителями слов.
    4. Обобщить формы слов. Например, избавиться от множественного числа, падежа, времени. Также применяются преобразования, отбрасывающие суффиксы слов, например слова «звонок» и «звонит»1 сводятся к слову «звон». Все буквы переводят в строчные (снова особый случай — аббревиатуры, чтобы не спутать «U.S.» и местоимение «us»). Здесь же в отдельных случаях возможна и корректировка орфографии. Много примеров и методик, применямых на данном этапе описаны во второй лекции стэнфордского курсаЗа исключением перевода букв в строчные, мы не будем делать никаких обобщений слов — это тема для отдельной большой работы.
  2. Индексация.
    1. При создании небольшой поисковой системы предполагаем для простоты, что весь индекс помещается в память. Мы начинаем с того, что строим прямой индекс, в нём каждому документу соответствует список слов из него с порядковым номером этого слова в этом документе.

      Прямой индекс

       

    2. По прямому индексу строим обратный индекс, в котором каждому слову соответствует список документов и позиций внутри документа, в которых это слово встречается. Технически это можно сделать, собрав прямой индекс в таблицу «Документ — Слово — Позиция» и сгруппировав по слову, а внутри слова по документу. Одновременно мы упорядочиваем индекс по слову, номеру документа и номеру позиции, чтобы оптимизировать дальнейшие запросы.

      Обратный индекс

       

    3. Обратный индекс может содержать дополнительные сведения и иметь более сложную структуру в зависмости от того, на какие запросы он должен уметь отвечать. Нашему роботу требуется отвечать на запросы, касающиеся положения слова внутри строки, поэтому вместо номера позиции в тексте мы храним пару [Номер стихотворной строки — Номер слова внутри строки].
  3. Запросы к индексу.
    1. Основным инструментом при обработке запросов к обратному индексу является функция слияния двух упорядоченных списков, имеющая линейную сложность. Допустим, мы хотим проверить, встречается ли в каком-нибудь тексте словосочетание «и ночью». Мы начнем со слияния списков документов слов «и» и «ночью», получим единственный элемент «Текст №1». Теперь сольем списки позиций слов внутри этого документа. Для «и» список позиций — (10, 12), а для «ночью» — (13). При слиянии находим, что в данном документе есть последовательность [12,13], следовательно документ удовлетворяет запросу. В слайдах стэнфордского курса имеется следующий псевдокод для функции слияния (или пересечения) двух упорядоченных списков.

      Псевдокод слияния (пересечения) упорядоченных списков

  4. Вывод результата.
    1. В обычных поисковых системах перед выводом результатов они упорядочиваются по степени соответствия запросу и затем несколько наиболее подходящих показываются человеку. У нас робот делает запросы к индексу, пока не построит полное дерево2, после чего это дерево преобразуется в HTML с использованием специальных идентификаторов, которые в дальнейшем используются скриптом на странице для динамического сворачивания-разворачивания дерева.

 

  1. ударение на последний слог — звонИт []
  2. около одной тысячи запросов []