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

Версия 23:22, 30 октября 2010

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

Построение индекса

Координатный индекс.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

...

Сжатие.