Редактирование: Поиск, 03 лекция (от 27 октября)

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

Версия от 23:24, 30 октября 2010; 212.192.251.2 (Обсуждение)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

ПРЕДУПРЕЖДЕНИЕ: Вы редактируете устаревшую версию данной страницы. После сохранения страницы будут потеряны изменения, сделанные в последующих версиях.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

...

Сжатие.

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.name/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA%2C_03_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_27_%D0%BE%D0%BA%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29