Материал из eSyr's wiki.

Текущая версия

Есть ещё одна задача: где в сети выложено англоязычная версия книжка Маннинга по информационному поиску.

[править] Построение индекса

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

Координатный индекс — перечень всех позиций. Как правило, номер слова.

Лексема — экземпляр последовательности символов в документе, объединённых в семантическую единицу для обр.

Тип — класс всех лексем, состоящих из одной и той же последовательности символов.

Про экзамен: разрешается пользоваться всем, чем угодно. После начала ответа пользование литературой и залом не допускается.

Термин — тип, включённый в словарь системы информационного поиска. При этом возможна нормализация.

Лексикон — множество всех терминов, включённых в словарь системы информационного поиска.

Что происходит с документом после того, как мы его откуда-то получили: на входе получаем последовательность символов.Что с этой последовательностью нужно сделать? Её нужно поделить на лексемы, которые мы потом будем включать в индекс. Простейшее, что может быть — слова. Но лексемой может быть и что-то, не являющееся словом.

К слову об ограничителях: довольно долго такие лексемы, как C++, не попадали в индекс, так как + — символ-разделитель.

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

Прежде, чем мы перейдём непосредственно к алгоритмам, введём ещё понятия:

Детализация индексирования (гранулярность) — что мы считаем единицей индекса, что именно является документом. Например, когда мы ищем человека, и его зовут, условно говоря, Иван Петров, то совершенно бессмысленно выдавать пользователю документ, где Иван находится в начале документа, а Петров в конце. Для слов высокой частотности вероятность того, что они встретятся в документе, довольно высока. Или, например, ищем зелёное яблоко. В этом случае совершенно необязательно встречаться словам подряд. Возможно и обратное — представление одного документа в нескольких файлах. В поисковых системах считается, что единица индексации — документ, каким бы он ни был.

Какой самый простейший способ построения инвертированного индекса? Это построение индекса с помощью сортировки и групппирования. Что здесь есть в плане информации: есть термин, и есть id документа.

Термин  id документа
а         1
б         1
е         2
в         2
а         2

Первый шаг — алфавитное упорядочивание (лексикографическая сортировка) по терминам.

Второй этап — группировка. Кроме этого сохраняются позиция в документе, специальные отметки.

Вот простейший алгоритм.

Что ещё нужно учитывать? Есть абстрактные теоретические модели, и есть то, как эти алгоритмы на самом деле работают на конкретном аппаратном обеспечении. То есть, соотношение всех теоретических свойств и теоретической сложности алгоритмов, оно должно учитывать на практике возможности аппаратного обеспечения, особенно при тех объёмах данных, которые обрабатывают крупные поисковые системы.

Особенность номер раз: то, что доступ к данным в памяти осуществляется быстрее доступа к данным на диске. Поэтому данные, использующиеся чаще, должны хранится там, где доступ быстрее. Что ещё: любопытный факт, что индекс, который используется при ответе пользователю, хранится полностью в оперативной памяти.

Ещё свойства: данные хранятся блоками, это частично имеет отношение к тому, как ОС имеет дело с ФС.

Можно произвольно параллельно обрабатывать информацию (?) и чтение/запись данных.

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

Следующий алгоритм: блочное индексирование, основанное на сортировке (BSBI). Чем-то похоже на сортировку слиянием. Здесь можно выделить 4 этапа:

* Сегментация коллекции
* Сортировка пар «идентификатор термина - идентификатор документа» (каждая часть влезает в память)
* Запись блоков на диск
* Объединение всех блоков

Дополнительная информация (языковая характиристика, шрифты, частотность) может записываться.

Второй из хороших алгоритмов — однопроходное индексирование в оперативной памяти (SPIMI). Здесь используется отдельный словарь для каждого документа. Для каждого нового термина при обработке документа он сохраняется в локальном словаре. Что стоит отметить: возникают проблемы с упорядоченностью при построении, и потом прихожится ещё переупорядочивать. Каждый из соответствующих списков по умолчанию под него выделяется некий объём памяти (встретили термин, нельзя сказать, сколько ещё раз он встретится; в предыдущем алгоритме в случае, когда есть полный список пар терм/документ, фиксированное количество таких пар). Это позволяет экономить память в некоторых случаях. Есть ещё некоторый плюс: можно от лексикографической сортировки избавиться, поскольку каждый раз, когда нам встречается слово, мы знаем, куда его записывать и этой сортировки нет. Поскольку количество различных слов в документе не может превосходить общего количества слов в документе, а на практике количество существенно меньше общего количества слов в документе, то на отсутствии этой сортировки достигается приличная экономия. Когда блок закончился, мы отправляем его и начинаем строить новый инвертированный индекс для нового блока.

Вот, получили мы некоторое количество блоков, можно их объединить, объединение здесь происходит аналогично предыдущему алгоритму, но здесь сливаются не только вхождения, но и словари.

...

Сжатие.