Поиск, 03 лекция (от 27 октября)

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

(Различия между версиями)
Перейти к: навигация, поиск

ESyr01 (Обсуждение | вклад)
(Новая: есть ещё одна заадча: где в сети выложено англоязычная версия книжка Маннинга по инф. поиску. = Постро...)
К следующему изменению →

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

...

Сжатие.


Введение в информационный поиск


01 02 03 04 05 06 07 08 09


Календарь

Октябрь
13 20 27
Ноябрь
17 24
Декабрь
01 08 15 22


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Личные инструменты
Разделы