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