Инвертированный индекс

Инвертированный индекс (англ. inverted index) — структура данных, в которой для каждого слова коллекции документов в соответствующем списке перечислены все документы в коллекции, в которых оно встретилось. Инвертированный индекс используется для поиска по текстам.

Есть два варианта инвертированного индекса:

индекс, содержащий только список документов для каждого слова,
индекс, дополнительно включающий позицию слова в каждом документе^[1].

Применение

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

Обычно в поисковых системах после построения с помощью инвертированного индекса списка документов, содержащих слова из запроса, идет ранжирование документов из списка. Инвертированный индекс — это самая популярная структура данных, которая используется в информационном поиске^[2].

Пример

Пусть у нас есть корпус из трёх текстов $T_{0}=$ "it is what it is", $T_{1}=$ "what is it" и $T_{2}=$ "it is a banana", тогда инвертированный индекс будет выглядеть следующим образом:

"a":      {2}
"banana": {2}
"is":     {0, 1, 2}
"it":     {0, 1, 2}
"what":   {0, 1}

Здесь цифры обозначают номера текстов, в которых встретилось соответствующее слово. Тогда отработка поискового "what is it" запроса даст следующий результат $\{0,1\}\cap \{0,1,2\}\cap \{0,1,2\}=\{0,1\}$ .

Особенности применения в реальных поисковых системах

В списке вхождений слова в документы, помимо id документов, обычно также указываются факторы (TF-IDF, бинарный фактор: «попало слово в заголовок или не попало», другие факторы), которые используются при ранжировании. Индекс может строиться не по всем словоформам, а по леммам (по каноническим формам слов). Стоп-слова можно исключить и не строить для них индекс, считая, что каждое из них встречается почти во всех документах корпуса. Для ускорения вычисления пересечений используют эвристику skip-pointer-ов. При обработке запросов, содержащих много слов, используют функцию кворума, которая пропускает на следующую стадию ранжирования часть документов, в которых встретились не все слова из запроса.

См. также

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

Литература

Ricardo Baeza-Yates, Berthier Ribeiro-Neto. Modern information retrieval. — Reading, Massachusetts: Addison-Wesley Longman, 1999. — 192 с. — ISBN 0-201-39829-X.
Justin Zobel, Alistair Moffat, Kotagiri Ramamohanarao. Inverted files versus signature files for text indexing (англ.) // ACM Transactions on Database Systems (TODS) : Journal. — 1998. — No. 23. — P. 453 - 490. — doi:10.1145/296854.277632.

[_99d9d1f145b5bf29-1] Baeza-Yates, 1999.

[_61b37dfdd33afd08-2] Zobel, Moffat, Ramamohanarao, 1998.

[1]

[2]