Поиск, 03 лекция (от 27 октября)
Материал из eSyr's wiki.
Есть ещё одна задача: где в сети выложено англоязычная версия книжка Маннинга по информационному поиску.
[править] Построение индекса
На прошлой лекции рассматривался пример инвертированного файла для одного файла. Для множества файлов обычно строится аналогичный индекс, но вида "термин - документ", то есть, есть ли он там, опционально, количество вхождений.
Координатный индекс — перечень всех позиций. Как правило, номер слова.
Лексема — экземпляр последовательности символов в документе, объединённых в семантическую единицу для обр.
Тип — класс всех лексем, состоящих из одной и той же последовательности символов.
Про экзамен: разрешается пользоваться всем, чем угодно. После начала ответа пользование литературой и залом не допускается.
Термин — тип, включённый в словарь системы информационного поиска. При этом возможна нормализация.
Лексикон — множество всех терминов, включённых в словарь системы информационного поиска.
Что происходит с документом после того, как мы его откуда-то получили: на входе получаем последовательность символов.Что с этой последовательностью нужно сделать? Её нужно поделить на лексемы, которые мы потом будем включать в индекс. Простейшее, что может быть — слова. Но лексемой может быть и что-то, не являющееся словом.
К слову об ограничителях: довольно долго такие лексемы, как C++, не попадали в индекс, так как + — символ-разделитель.
Про нормализацию: для русского языка, где слова изменяются хорошо и сильно, информация в индексе хранится для нормализованного слова, подробнее мы об этом поговорим потом, но на предварительном этапе, перед тем, ка мы строим индекс, происходит определение и выделение того, что попадает в лексикон, совсем-совсем. Например, слова "яблоко", "яблока", "яблоки" — это разные словоформы одного и того же слова. Логично, чтобы это хранилось в одной единице и где-то рядом была информация, в каком падеже это слово было употреблено.
Прежде, чем мы перейдём непосредственно к алгоритмам, введём ещё понятия:
Детализация индексирования (гранулярность) — что мы считаем единицей индекса, что именно является документом. Например, когда мы ищем человека, и его зовут, условно говоря, Иван Петров, то совершенно бессмысленно выдавать пользователю документ, где Иван находится в начале документа, а Петров в конце. Для слов высокой частотности вероятность того, что они встретятся в документе, довольно высока. Или, например, ищем зелёное яблоко. В этом случае совершенно необязательно встречаться словам подряд. Возможно и обратное — представление одного документа в нескольких файлах. В поисковых системах считается, что единица индексации — документ, каким бы он ни был.
Какой самый простейший способ построения инвертированного индекса? Это построение индекса с помощью сортировки и групппирования. Что здесь есть в плане информации: есть термин, и есть id документа.
Термин id документа а 1 б 1 е 2 в 2 а 2
Первый шаг — алфавитное упорядочивание (лексикографическая сортировка) по терминам.
Второй этап — группировка. Кроме этого сохраняются позиция в документе, специальные отметки.
Вот простейший алгоритм.
Что ещё нужно учитывать? Есть абстрактные теоретические модели, и есть то, как эти алгоритмы на самом деле работают на конкретном аппаратном обеспечении. То есть, соотношение всех теоретических свойств и теоретической сложности алгоритмов, оно должно учитывать на практике возможности аппаратного обеспечения, особенно при тех объёмах данных, которые обрабатывают крупные поисковые системы.
Особенность номер раз: то, что доступ к данным в памяти осуществляется быстрее доступа к данным на диске. Поэтому данные, использующиеся чаще, должны хранится там, где доступ быстрее. Что ещё: любопытный факт, что индекс, который используется при ответе пользователю, хранится полностью в оперативной памяти.
Ещё свойства: данные хранятся блоками, это частично имеет отношение к тому, как ОС имеет дело с ФС.
Можно произвольно параллельно обрабатывать информацию (?) и чтение/запись данных.
Данных много, всё в оперативную память не влезает. Приходиться выкручиваться, держать часть данных на диске и периодически обмениваться.
Следующий алгоритм: блочное индексирование, основанное на сортировке (BSBI). Чем-то похоже на сортировку слиянием. Здесь можно выделить 4 этапа:
* Сегментация коллекции * Сортировка пар «идентификатор термина - идентификатор документа» (каждая часть влезает в память) * Запись блоков на диск * Объединение всех блоков
Дополнительная информация (языковая характиристика, шрифты, частотность) может записываться.
Второй из хороших алгоритмов — однопроходное индексирование в оперативной памяти (SPIMI). Здесь используется отдельный словарь для каждого документа. Для каждого нового термина при обработке документа он сохраняется в локальном словаре. Что стоит отметить: возникают проблемы с упорядоченностью при построении, и потом прихожится ещё переупорядочивать. Каждый из соответствующих списков по умолчанию под него выделяется некий объём памяти (встретили термин, нельзя сказать, сколько ещё раз он встретится; в предыдущем алгоритме в случае, когда есть полный список пар терм/документ, фиксированное количество таких пар). Это позволяет экономить память в некоторых случаях. Есть ещё некоторый плюс: можно от лексикографической сортировки избавиться, поскольку каждый раз, когда нам встречается слово, мы знаем, куда его записывать и этой сортировки нет. Поскольку количество различных слов в документе не может превосходить общего количества слов в документе, а на практике количество существенно меньше общего количества слов в документе, то на отсутствии этой сортировки достигается приличная экономия. Когда блок закончился, мы отправляем его и начинаем строить новый инвертированный индекс для нового блока.
Вот, получили мы некоторое количество блоков, можно их объединить, объединение здесь происходит аналогично предыдущему алгоритму, но здесь сливаются не только вхождения, но и словари.
...
Сжатие.