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

Версия 15:03, 29 октября 2010

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

...

Сжатие.