Что хотят услышать интервьюеры:

Inverted index — это базовая структура для быстрого поиска по текстам: она сопоставляет термины с документами, где они встречаются. В отличие от прямого индекса по документам, здесь ищут не документ по ключу, а все документы по слову. В поисковых системах часто дополнительно хранят позиции слов, частоты и служебные метаданные для ранжирования.

Определение:

Inverted index, или обратный индекс, — это структура данных, которая для каждого термина хранит список документов, в которых этот термин встречается. Обычно список не просто содержит идентификаторы документов, а включает дополнительные данные: частоту термина в документе, позиции слова в тексте, иногда поля документа.

На практике это позволяет быстро выполнять поиск по запросу без полного перебора всех документов. Вместо просмотра каждого текста система сразу обращается к спискам документов для нужных слов и затем объединяет или пересекает их.

Пример использования:

Допустим, есть три документа:

D1: cat sat on mat
D2: dog sat on rug
D3: cat and dog

Инвертированный индекс будет выглядеть примерно так:

cat -> [D1, D3]
sat -> [D1, D2]
dog -> [D2, D3]
on  -> [D1, D2]
mat -> [D1]
rug -> [D2]
and -> [D3]

Если пользователь ищет cat AND dog, система быстро берет списки для cat и dog и пересекает их. Результат будет D3.

Пояснение кода:

Код не требуется, но логика построения индекса выглядит так:

Берется документ.
Текст токенизируется: слова нормализуются, например приводятся к нижнему регистру.
Для каждого слова в структуру индекса добавляется ссылка на документ.
Если нужны позиции, к записи добавляется номер слова в тексте.
При обработке запроса система читает списки по словам и выполняет пересечение, объединение или ранжирование.

Пример псевдокода:

index = {}

for doc_id, text in documents:
    for position, term in enumerate(tokenize(text)):
        index[term].add(doc_id)
        positions[term][doc_id].append(position)

Здесь index хранит postings list для каждого термина, а positions — позиции слов внутри документов.

Ключевые моменты:

Основная идея: отображение term -> список документов, а не document -> список терминов.
Обычно используются postings lists — списки идентификаторов документов, часто с частотами и позициями.
Для быстрого доступа к термам обычно применяется хеш-таблица, trie или словарь.
Списки документов часто хранят в отсортированном виде, чтобы эффективно делать пересечения.
Для экономии памяти применяют сжатие списков и кодирование разностей между docID.
Инвертированный индекс — фундамент поисковых систем и retrieval-части LTR/IR pipelines.

Что такое inverted index и какие структуры данных используются?