Введение в информационный поиск

1998 год. AltaVista - крупнейший поисковик планеты, 200 миллионов проиндексированных страниц. Медленный. Нерелевантный. Два студента из Стэнфорда запускают Google с вдвое меньшим индексом - и уничтожают AltaVista за два года. Секрет? Один трюк: инвертированный индекс плюс PageRank. Не больше железа, не больше денег - другая структура данных. Сегодня Google обрабатывает 8.5 миллиарда запросов в день, каждый - за 200 миллисекунд.

• **Google Search** - инвертированный индекс из 100B+ страниц плюс BERT-ранжирование: от структуры данных 1998 года до нейросетей 2019-го
• **Elasticsearch** обслуживает поиск в GitHub (500M+ репозиториев), Wikipedia, Uber - полнотекстовый поиск за миллисекунды
• **Algolia** даёт e-commerce поиск быстрее 10 мс; **Qdrant и Pinecone** - векторный поиск для семантики, где «автомобиль» находит «машина»

Indexing

Миллиард документов. Один запрос. 200 миллисекунд. Линейный перебор за это время - физически невозможен. Скорость света не поможет. Нужна другая идея. **Индексирование** - это построение структуры данных, которая делает «найти» дешёвым. Не быстрее железо, а умнее структура.

Google индексирует более **100 миллиардов** страниц. Без индекса - перебор занял бы дни. С инвертированным индексом ответ приходит за **0.2 секунды**. Разрыв не в скорости процессора - в алгоритмической сложности: O(n) против O(1).

Идея проста до неприличия: вместо «документ → слова» хранить «слово → документы». Перевернуть направление маппинга. Это и есть **инвертированный индекс** - структура, на которой работает каждый поисковик. AltaVista её тоже имел. Но Google добавил к ней PageRank - и победил.

Ranking

Индекс нашёл миллион страниц по запросу «Python». Поздравляем. Теперь главный вопрос: какую показать первой? Это задача **ранжирования** - и именно здесь кроется вся ценность поисковика. Найти легко. Правильно упорядочить - сложно.

75% кликов приходится на первые три результата поисковой выдачи. Большинство пользователей не уходят дальше первой страницы. Ранжирование определяет, какой сайт получит трафик, а какой - нет. Это миллиарды долларов рекламного рынка, упакованные в один алгоритм.

Два фундаментальных подхода. **Content-based**: смотрим внутрь документа - частота слова, его редкость в корпусе, позиция в тексте (TF-IDF, BM25). **Link-based**: смотрим снаружи - кто ссылается, насколько авторитетны источники (PageRank). Google победил AltaVista именно потому, что первым скрестил оба.

Современный Google комбинирует сотни сигналов: BM25 за релевантность слов, PageRank за авторитетность домена, CTR и время на странице за поведение пользователей, свежесть за новизну. С 2019 года - BERT для понимания смысла запроса целиком, не по словам. Elasticsearch для внутреннего поиска в продуктах использует тот же стек: BM25 плюс опциональный нейросетевой reranker.

Relevance

Ранжирование пытается поставить «релевантные» документы выше. Но что значит **релевантный**? Это центральный и удивительно неудобный вопрос IR. Нельзя записать в код. Нельзя посчитать формулой. Это степень соответствия документа тому, что пользователь на самом деле хотел найти - не тому, что написал в строке поиска.

Релевантность **субъективна**. Два профессиональных асессора расходятся в оценке одного документа в 30-40% случаев - Cohen's kappa около 0.6-0.7. Именно поэтому Google нанимает тысячи «raters» по всему миру и тратит миллиарды на разметку данных. Субъективность нельзя убрать - только усреднить.

Три уровня. **Topical**: документ о той же теме. **User**: подходит конкретному пользователю с его контекстом. **Situational**: помогает решить задачу прямо сейчас. Запрос «Python» от школьника - туториал. От биолога - змея. От DevOps - пакетный менеджер. Один запрос, три разных правильных ответа. Именно поэтому поисковики смотрят не только на запрос, но и на историю, геолокацию, устройство.

На практике используют **шкалу релевантности**: 0 (нерелевантен), 1 (частично), 2 (релевантен), 3 (идеально). TREC (Text REtrieval Conference) с 1992 года организует соревнования, где тысячи пар запрос-документ размечают люди. Эти датасеты стали стандартом для сравнения поисковых систем - как ImageNet для компьютерного зрения.

Precision & Recall

Субъективность релевантности не мешает измерять поиск числами. Для этого есть две фундаментальные метрики: **Precision** и **Recall**. Первая спрашивает: сколько мусора в выдаче? Вторая: сколько нужного пропустили? Они тянут в разные стороны - и именно это напряжение определяет, каким поисковиком вы пользуетесь.

**Precision** - из того, что система вернула, сколько действительно полезно? **Recall** - из всего полезного, что существует, сколько нашли? Улучшая одно, портишь другое. Вернуть всё подряд - Recall = 1, Precision = мусор. Вернуть только один идеальный результат - Precision = 1, Recall = катастрофа. Баланс между ними - это и есть искусство ранжирования.

Trade-off определяет применение. Медицинская система поиска побочных эффектов - нужен максимальный Recall: пропустить важное опасно. Юридический поиск прецедентов - аналогично. Веб-поиск и e-commerce - Precision: пользователь не листает дальше третьего результата, мусор в топе - это уход к конкуренту.

Для ранжированных списков P/R недостаточно - они не учитывают позицию. Первый результат важнее десятого. Поэтому используют **NDCG** (Normalized Discounted Cumulative Gain) - метрику, которая штрафует за релевантный результат на низкой позиции. Именно NDCG использует Google для оценки своего качества внутри. **MAP** и **MRR** - для систем, где нужен единственный правильный ответ.

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

• **Инвертированный индекс** - главный трюк IR: переворот «документ → слова» в «слово → документы», O(n) в O(1). Именно он решил задачу, с которой не справлялся AltaVista
• **Ранжирование** сложнее поиска: из миллиона документов по запросу нужно вывести нужный первым. BM25, PageRank, BERT - каждое поколение решало это лучше предыдущего
• **Precision** (сколько мусора в ответе) и **Recall** (сколько нужного нашли) - постоянный trade-off: медицина хочет Recall, веб-поиск - Precision
• Релевантность субъективна: два эксперта расходятся в 30-40% случаев. Именно поэтому поисковики меряют качество A/B-тестами, а не только метриками

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

Информационный поиск объединяет идеи из нескольких областей:

• Инвертированный индекс — Основная структура данных для поиска - детально разбирается в следующем уроке
• TF-IDF и BM25 — Математические модели ранжирования на основе частоты слов

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

• AltaVista имел вдвое больше проиндексированных страниц, чем ранний Google. Почему это не помогло? Что именно решило исход конкуренции?
• В каких ситуациях Recall важнее Precision, а в каких - наоборот? Приведите примеры из реальной жизни, где неправильный выбор стоил бы дорого.
• Если строить поисковик для внутреннего корпоративного портала компании - какая архитектура подойдёт: инвертированный индекс, векторный поиск или гибрид? Почему?

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

• nlp-01 — NLP обрабатывает текст запроса и документов: токенизация, стемминг и эмбеддинги питают IR-пайплайн
• db-01-intro — Базы данных хранят индексы; SQL full-text search - простейший IR поверх СУБД
• ml-01-intro — Learning-to-rank и нейросетевые rerankers - ML применённый к задаче ранжирования
• alg-01-big-o — Переход от O(n) к O(1) через инвертированный индекс - фундаментальная алгоритмическая идея
• ir-02 — Следующий урок детально разбирает структуру инвертированного индекса
• dm-01