Информационный поиск

Query Autocomplete и Suggest

Строка поиска Google отвечает за 200 мс. За это время нужно пройти через trie с миллиардами записей, смешать глобальные и персональные сигналы, проверить трендовость - и вернуть 10 релевантных подсказок. Как это работает под нагрузкой 100 000 запросов в секунду?

**Google Search:** trie с сотнями миллиардов n-грамм, персонализация, локализация
**Spotify:** suggest по трекам/артистам/плейлистам с учётом вкусов пользователя
**Amazon:** suggest по товарам с учётом истории покупок и трендов категории
**IDE autocomplete (LSP):** trie по символам кода, приоритет ближайших по области видимости

Trie для prefix search

Пользователь ввёл «py» - через 50 мс уже должен видеть «python tutorial», «python download», «pyramid». За этими 50 мс скрыта структура данных **trie** (префиксное дерево): каждый узел - символ, путь от корня до узла - префикс. Все строки с данным префиксом живут в поддереве этого узла.

**Память trie:** в худшем случае O(N * L) узлов, где N - число строк, L - средняя длина. Для словаря из 1M запросов длиной ~20 символов - это 20M узлов. **Compressed trie (Patricia trie)** схлопывает цепочки без разветвлений в один узел, уменьшая память в 2-5 раз.

Какова сложность поиска всех дополнений для префикса длиной k в trie с N строками?

Prefix-based suggest с весами

Простой trie возвращает все дополнения и сортирует их по частоте. Но реальный suggest сложнее: нужно хранить топ-K для каждого префикса, обновлять веса, учитывать свежесть данных. И делать это за миллисекунды под нагрузкой миллионов запросов в секунду.

**Оптимизация 1: хранить топ-K прямо в узлах.** Каждый узел trie хранит не просто счётчик, а список топ-K лучших дополнений. Тогда suggest - это O(k) спуск + O(1) чтение готового результата, без DFS. Платим памятью, выигрываем временем.

**Оптимизация 2: разбиение на диапазоны (range partitioning).** Trie для suggest обычно слишком велик для одной машины. Запросы на «a*», «b*» и т.д. распределяются по разным серверам. Первый символ или первые два определяют шард - балансировщик маршрутизирует запрос на нужный сервер.

**Inverted index как альтернатива.** Для коротких префиксов trie быстр, но для опечаток и нечёткого поиска лучше работает **inverted index по n-graмам**: разбиваем каждый запрос на n-граммы символов и индексируем. Поиск похожих строк становится поиском по пересечению n-грамм.

Зачем хранить топ-K дополнений прямо в каждом узле trie?

Персонализированный suggest

Глобальный suggest показывает топ-запросы для всех. Но пользователь, ищущий «python» в контексте программирования, получит другой suggest, чем тот, кто ищет питомника. **Персонализация** - смешивание глобального и пользовательского сигналов.

Источники персонального сигнала: история поиска пользователя, его предыдущие клики, геолокация, язык браузера, время суток. Все эти сигналы повышают score релевантных запросов при финальном ранжировании suggest-а.

**Privacy trade-off.** Хранение истории поиска для персонализации требует решения: где хранить (на устройстве vs сервере), как долго (сессия vs месяц vs навсегда), как обрабатывать (in-house vs third-party). Google хранит историю поиска на сервере, Safari Suggestions - только локально на устройстве.

Параметр alpha=0.3 в персонализированном suggest означает:

Trending queries и real-time update

Когда происходит что-то значимое - землетрясение, матч, выход фильма - тысячи людей одновременно начинают искать. Статичный trie это не отразит. **Trending queries** - механизм детекции и продвижения резко набирающих популярность запросов.

Простой счётчик частоты не работает для трендов: запрос с 10 000 поисков сегодня и 100 вчера - тренд. Запрос с 50 000 поисков сегодня и 49 000 вчера - нет. Нужно отслеживать **скорость роста** (velocity), а не абсолютное число.

**Count-Min Sketch для частот.** При миллиардах поисков хранить точные счётчики для всех n-грамм невозможно. Count-Min Sketch - вероятностная структура данных: O(ε^-1 * log δ^-1) памяти вместо O(N). Переоценивает частоты, но никогда не недооценивает. Используется в Google, Twitter для трендов.

Почему для определения трендовых запросов недостаточно просто отсортировать по абсолютной частоте?