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

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

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

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

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

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

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

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

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

Из описания индекса сразу понятно, что это идеальный инструмент для поиска по отдельно взятому слову. Задача тривиальная: по идентификатору WordID выбрать из базы все DocId документов, где это слово встречается. Ранжирование тоже не составит труда, если для каждого DocID в базе хранится информация о том, является ли это слово ключевым в тексте, или же оно второстепенное и не имеет прямого отношения к теме. То есть, для каждой связи «WordID – DocID» должна быть подготовлена информация о релевантности документа этому слову.

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

1. подряд,
2. не подряд, но в одном пассаже,
3. в смежных пассажах,
4. встречаются в разных частях текста.

Это самый грубый способ определения релевантности. В первом случае релевантность документа наибольшая, во втором более слабая, в третьем — уже сомнительная, в четвертом — минимальная. Для более точной оценки в первых двух вариантах нужно учитывать, соответствует ли запросу порядок следования слов, во втором и третьем варианте учесть расстояние между словами (сколько посторонних слов «вклинилось»).

Для обеспечения полноты поиска требуется учесть формы слов запроса — следовательно, в индексе нужно приводить слова к исходной форме (например, для существительных — единственное число, именительный падеж) и связывать со всеми возможными словоформами. В то же время для поиска по точным вхождениям нужна возможность поиска каждой словоформы. Это усложняет структуры данных поисковой системы, приводя к множеству индексов (по понятным причинам тупой стемминг здесь слабо помогает).