Это старая версия документа.


Поисковый индекс

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

Более подробный индекс — алфавитный указатель, где уже реализована связь «один ко многим»: каждому значимому термину сопоставлен список страниц, где этот термин упоминается. Следующая ступенька — конкорданс. Это словарь, где каждому слову сопоставлены «координаты» вхождений этого слова в текст. В общем виде это и есть то, что называется «инвертированным индексом», который используют наиболее известные поисковые системы.

Прямой и инвертированный индекс

Это две разновидности индекса, которые реализуют связи в разных направлениях. Представим себе коллекцию текстовых документов и полный список слов, найденных в этих документах. Каждому документу в коллекции присвоен уникальный идентификатор DocID, каждому слову — уникальный идентификатор WordID.

Прямой индекс — таблица связей, где каждому DocID сопоставлен полный список WordID входящих в этот документ слов.

Инвертированный индекс — таблица связей, где каждому WordID сопоставлен список DocID, где это слово встречается.

Инвертированный индекс идеально приспособлен для поиска. Из него очень просто берется список DocID документов, в которые входит искомое слово. Если в запросе два слова, выбираем два списка документов (по WordID обоих слов). Затем выбираем те DocID, которые входят в оба эти списка и получаем итоговый список DocID всех документов, где встречаются оба слова.

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

Естественно, прежде чем пользоваться этими инструментами, нужно обработать (проиндексировать) всю коллекцию документов. Для этого нужно каждый документ разобрать на слова, попутно подсчитать число вхождений каждого слова, собрать словарь и индексы. Если не подходить к важности слова в тексте так грубо, а подсчитать важность слов в тексте по законам Зипфа, то мы получим уже вполне пригодный инструмент ранжирования найденных текстов.

поисковый-индекс.1346950262.txt.gz · создано: 2010/08/02 21:25 — Zanuda · Последние изменения: 2012/09/06 20:51 — Spinne
Наверх
Driven by DokuWiki