Инвертированный индекс (англ. inverted index) — структура данных, в которой для каждого слова коллекции документов в соответствующем списке перечислены все документы в коллекции, в которых оно встретилось. Инвертированный индекс используется для поиска по текстам.
Есть два варианта инвертированного индекса:
Опишем, как решается задача нахождения документов, в которых встречаются все слова из поискового запроса. При обработке однословного поискового запроса ответ уже есть в инвертированном индексе — достаточно взять список, соответствующий слову из запроса. При обработке многословного запроса берётся пересечение списков, соответствующих каждому из слов запроса.
Обычно в поисковых системах после построения с помощью инвертированного индекса списка документов, содержащих слова из запроса, идет ранжирование документов из списка. Инвертированный индекс — это самая популярная структура данных, которая используется в информационном поиске[2].
Пусть у нас есть корпус из трёх текстов
"it is what it is"
,
"what is it"
и
"it is a banana"
,
тогда инвертированный индекс будет выглядеть следующим образом:
"a": {2} "banana": {2} "is": {0, 1, 2} "it": {0, 1, 2} "what": {0, 1}
Здесь цифры обозначают номера текстов, в которых встретилось соответствующее слово.
Тогда отработка поискового "what is it"
запроса даст следующий результат
.
В списке вхождений слова в документы, помимо id документов, обычно также указываются факторы (TF-IDF, бинарный фактор: «попало слово в заголовок или не попало», другие факторы), которые используются при ранжировании. Индекс может строиться не по всем словоформам, а по леммам (по каноническим формам слов). Стоп-слова можно исключить и не строить для них индекс, считая, что каждое из них встречается почти во всех документах корпуса. Для ускорения вычисления пересечений используют эвристику skip-pointer-ов. При обработке запросов, содержащих много слов, используют функцию кворума, которая пропускает на следующую стадию ранжирования часть документов, в которых встретились не все слова из запроса.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .