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

Google обрабатывает 8.5 миллиарда запросов в день. PageRank - уже не главный алгоритм. BERT, RankBrain, MUM, Multitask Unified Model - каждый запрос проходит через 200+ сигналов. Всё началось с inverted index 1960-х. Когда поиск в Google занимает 200 миллисекунд - 190 из них это fetch из индекса. Без него ни один из современных алгоритмов не смог бы работать в real-time.

• **Lucene/Elasticsearch** - open-source движок, на котором работает поиск в Wikipedia, GitHub, Netflix, eBay; индекс обновляется в near-realtime через segment merging
• **Google** хранит индекс размером в сотни петабайт, распределённый по тысячам серверов; каждый запрос проходит через многоуровневую иерархию индексов
• **VS Code** (Find in Files) использует упрощённый инвертированный индекс для мгновенного поиска по проекту - миллисекунды вместо секунд линейного scan
• **Cloudflare** использует Lucene-based индексирование для поиска по 100+ триллионам DNS-записей и log-событий в real-time
• **Typesense и Meilisearch** - современные open-source поисковые движки с inverted index + BM25 + typo-tolerance как hosted service

Предварительные знания

• Introduction to Information Retrieval

Gerald Salton и рождение современного поиска

В 1960-х Джеральд Салтон в Корнельском университете создал **SMART-систему** (System for the Mechanical Analysis and Retrieval of Text) - первый прообраз современного поиска. Он формализовал понятие inverted index, ввёл **TF-IDF** (term frequency - inverse document frequency) и vector space model. Без этой работы ни Lucene, ни Google не существовали бы в нынешнем виде. Статья Salton 1975 «A Vector Space Model for Automatic Indexing» - это фундамент, на котором стоят все современные поисковые системы.

Posting List

Google обрабатывает 8.5 миллиарда запросов в день. PageRank - уже не главный алгоритм. BERT, RankBrain, MUM - каждый запрос проходит через 200+ сигналов. Всё началось с inverted index 1960-х. Без него ни один из этих алгоритмов не мог бы работать за 200 миллисекунд.

Инвертированный индекс состоит из двух частей: **словарь** (dictionary) - список всех уникальных слов, и **posting lists** - для каждого слова список документов, в которых оно встречается. Posting list - это сердце поисковой системы.

Для ответа на запрос из нескольких слов (например, «binary algorithm») нужно найти **пересечение** (intersection) их posting lists. Запрос «binary AND algorithm» означает: найти документы, которые есть в обоих списках.

Posting lists **всегда отсортированы** по doc_id. Это позволяет выполнять пересечение за O(n + m) вместо O(n * m). Для запроса из k слов оптимально начинать пересечение с самого короткого списка.

Помимо пересечения (AND), поддерживаются операции: **объединение** (OR) - merge двух списков, и **вычитание** (NOT) - разность. Вместе они позволяют выполнять boolean queries: `(python OR java) AND NOT javascript`.

Tokenization

Прежде чем построить индекс, нужно превратить текст в список **токенов** (tokens). Токенизация - это процесс разбиения текста на единицы индексирования. Кажется просто - разбить по пробелам? На практике всё намного сложнее. Gerald Salton и SMART-система в 1960-х впервые формализовали этот процесс - и заложили фундамент TF-IDF, на котором стоит современный поиск.

**Стемминг vs Лемматизация**: стемминг (Porter Stemmer) обрезает окончания по правилам (быстро, но грубо: «university» -> «univers»). Лемматизация использует словарь и морфологию (точнее, но медленнее: «better» -> «good»). Большинство поисковых систем используют стемминг + словарь синонимов.

Особенно сложна токенизация для **CJK языков** (китайский, японский, корейский) - там нет пробелов между словами. Для русского языка нужен отдельный стеммер (Snowball Russian Stemmer), учитывающий падежи, склонения и спряжения.

Результат токенизации критически влияет на качество поиска. Слишком агрессивный стемминг объединит разные слова (например, «arm» и «army»). Слишком мягкий - не найдёт разные формы одного слова.

Compression

Posting list для частого слова вроде «the» может содержать миллиарды doc_id. Google хранит индекс размером в сотни петабайт - без сжатия это было бы невозможно. **Delta encoding + Variable Byte** уменьшает размер индекса в 4-10 раз. Это не инженерная деталь - это условие работоспособности системы.

Ключевая идея - **delta encoding** (gap encoding). Вместо абсолютных doc_id хранить разницы (gaps) между соседними значениями. Поскольку списки отсортированы, gaps всегда положительны и часто невелики.

После delta encoding маленькие gaps кодируются **Variable Byte Encoding** (VByte): используем 7 бит на байт для данных и 1 бит как флаг продолжения. Число 5 займёт 1 байт вместо 4. Elasticsearch и Lucene используют именно VByte. Google использует более эффективные кодировки: **PForDelta** и **SIMD-BP128**.

Сжатие словаря (dictionary) - отдельная задача. Используют **front coding**: общие префиксы хранятся один раз (auto -> autom -> automat -> automatic -> automobile). Это экономит до 50% пространства словаря.

Skip Lists

Пересечение двух posting lists длиной n и m требует O(n + m). Можно ли быстрее? **Skip lists** позволяют «перепрыгивать» через блоки элементов, которые точно не нужны, ускоряя пересечение до O(sqrt(n)). Это та же идея, что и бинарный поиск, но встроенная в структуру данных.

Оптимальное расстояние между skip pointers - **sqrt(L)**, где L - длина posting list. Для списка из 10000 элементов ставим skip pointer каждые 100 элементов. Слишком частые - занимают много памяти. Слишком редкие - не дают ускорения.

На практике skip lists в чистом виде встречаются в учебных реализациях. Промышленные системы (Lucene, Elasticsearch) используют **block-based индексы**: posting list разбивается на блоки по 128 doc_id, каждый блок сжат отдельно, а skip поинтеры указывают на начало блока. Это сочетает сжатие и быстрый skip.

Ещё одна оптимизация - **query optimization**: при AND-запросе из нескольких слов начинаем пересечение с самого короткого posting list. Для запроса «the AND algorithm AND quantum» сначала пересекаем «quantum» (редкое) с «algorithm» (среднее), а «the» (очень частое) - в последнюю очередь или вообще пропускаем.

Ключевые идеи

• **Posting list** - отсортированный список doc_id для каждого термина; пересечение за O(n + m) через two-pointer алгоритм
• **Токенизация** - превращение текста в термины: lowercase, стемминг, удаление стоп-слов. Gerald Salton и SMART-система 1960-х - основа современных подходов
• **Delta encoding + VByte** сжимает posting lists в 4-10 раз, кодируя разницы между doc_id. Google использует PForDelta и SIMD-BP128
• **Skip lists** ускоряют пересечение до O(sqrt(n)), позволяя перепрыгивать через ненужные блоки. Оптимальный шаг - sqrt(L)
• **Block-based индексы** в Lucene/Elasticsearch: 128 doc_id в блоке, сжатие + skip между блоками - SIMD-параллелизм в production

Связанные темы

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

• Введение в IR — Этот урок детализирует структуру индекса, описанную в первом уроке
• TF-IDF и BM25 — Posting lists хранят term frequency - основу для вычисления TF-IDF скоров

Вопросы для размышления

• Почему стоп-слова (the, is, a) обычно исключают из индекса? В каких случаях это может навредить?
• Как реализовать фразовый поиск («машинное обучение» как фразу, а не два отдельных слова)?
• Если posting list содержит 1 миллион doc_id, сколько skip pointers будет оптимально?

Связанные уроки

• ir-01 — Базовая модель IR перед погружением в структуру индекса
• ir-03 — TF-IDF и BM25 строятся поверх posting lists с term frequency
• alg-12-bfs — Обход графов через очередь - та же идея merge двух sorted lists
• ds-24-bloom-filter — Bloom filter - вероятностная структура для быстрой проверки наличия в индексе
• aie-10-vector-databases — Vector DB - современная альтернатива: ANN вместо inverted index для семантического поиска
• alg-26-two-pointers — Two-pointer техника - механика пересечения posting lists
• ml-01-intro