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