Что такое инвертированный индекс и как он работает?
Инвертированный индекс — это структура данных, которая сопоставляет каждому слову список документов, где оно встречается. Вместо поиска слова внутри всех документов поиск выполняется по ключу в индексе. Это резко ускоряет поиск по текстам.
Инвертированный индекс — фундаментальный приём оптимизации текстового поиска.
Инвертированный индекс — это отображение вида «терм → список документов», в которых этот терм присутствует.
все документы разбиваются на слова,
для каждого слова фиксируется идентификатор документа,
формируется отображение слова в список документов.
{
"python": [1, 3, 7],
"index": [2, 3],
"search": [1, 4]
}
без индекса: перебор всех документов,
с индексом: один доступ по ключу.
плюсы: быстрый поиск, масштабируемость,
минусы: дополнительная память, этап предобработки.
Инвертированный индекс переводит поиск из линейного перебора в быстрый доступ по ключу и является стандартом для текстовых поисковых систем.
