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

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

Основные компоненты inverted index:

• Словарь терминов (Vocabulary): множество уникальных слов из всех документов.
• Постинг-листы (Posting lists): для каждого слова хранится список документов (обычно с указанием позиций слова в документе), где оно встречается.

Типичные структуры данных для реализации:

• Хеш-таблицы или деревья (например, B-деревья) для словаря терминов.
• Связные списки или массивы для постинг-листов.

Пример:

слово: "python"
постинг-лист: [doc1: позиции [3, 15], doc5: позиции [7]]

Это позволяет эффективно выполнять запросы типа "найти все документы, содержащие слово 'python'" или более сложные запросы с несколькими словами.

Inverted index — основа для систем полнотекстового поиска и ранжирования документов.