Кратко — решение состоит из трёх частей: (1) эффективная структура для генерации кандидатов (prefix + typo-tolerance), (2) ранжирование с учётом частот/релевантности и (3) инженерия для realtime-обновлений и масштабирования. Ниже — конструкция, алгоритмы, API и режимы обновления.
1) Структуры данных (основа)
- Компрессированный префиксный автомат (compressed trie / FST) для точного prefix-поиска. В каждом узле хранится ограниченный список топ-N подсказок (id фразы + score) для быстрого возврата.
- K-gram inverted index или SymSpell-подобная таблица «delete-variants → фразы» для очень быстрого tolerant matching опечаток.
- Count store: точные счётчики для популярных фраз (в памяти, e.g. Redis/rocksdb) + sketch (Count-Min Sketch) для массовых/редких фраз.
- Для экономии памяти на node: хранить только top-N (обычно N = 10..100) с min-heap / bounded priority queue (Space-Saving).
2) Генерация кандидатов
- Prefix-кандидаты: пройти по FST до узла префикса и вернуть top-N из узла (O(|prefix|) + O(N)).
- Fuzzy-кандидаты:
- SymSpell: предвычислить все delete-варианты фраз до расстояния d (обычно d=1..2) и при запросе генерировать deletes от ввода, смотреть маппинг — очень быстро.
- Или k-gram: построить k-грам индекс (k=2..3). Для запроса взять k-грам, пересечь/сосчитать совпадения (dice/jaccard) → shortlist → проверить реальным edit distance и отсортировать.
- Альтернатива: BK-tree для сравнений по edit-distance, но менее удобен на больших словарях.
- Объединить кандидаты из точного prefix и fuzzy, убрать дубликаты.
3) Ранжирование (score)
- Комбинировать частотность, свежесть, CTR и возможно персонализацию:
- Пример формулы (нормализация обязательна):
$$score=\alpha \cdot \log (1+freq)+\beta \cdot e^{-\lambda \cdot (age)}+\gamma \cdot CTR+\delta \cdot personalized\_score$$ - Параметры $\alpha ,\beta ,\gamma ,\delta ,\lambda$ настраиваются A/B.
- Порог на edit-distance (например $\le 2$) и минимальный score для показа.
4) Обновления статистики в реальном времени
- Инструментарий:
- Write-ahead stream (Kafka) для событий: QueryTyped, SuggestionShown, SuggestionClicked.
- Consumers (real-time workers) агрегируют события и обновляют in-memory stores/Count-Min/Space-Saving структур.
- Подходы:
- Fast-path: инкрементать локальные in-memory счетчики и топ-N в узлах trie (atomic CAS / lock-free structures). Это даёт моментальный эффект подсказок.
- Durability: асинхронно дампить батчи в persistent DB (RocksDB, Cassandra).
- Periodic compaction: каждые T минут ре-вычислять/перестраивать FST-слои из агрегированных данных (полная/инкрементальная сборка).
- Для высокой нагрузки: использовать sharding по префиксу (например хеш первых K символов) — каждый шард поддерживает свою локальную FST/indices + лидеры реплики.
5) Масштабируемость и доступность
- Шардирование:
- По префиксу/хешу/алфавиту; запросы направляются по роутингу к соответствующим шард-нодам и агрегируются.
- Репликация для чтений; регулярная синхронизация агрегатов.
- Кэширование: CDN и edge caches для популярных префиксов.
- Хранилище подсказок: cold store (HDFS/S3) + periodic rebuild FST; hot store (in-memory per-shard).
- Ограничение памяти: хранить только top-N на узел, использовать FST для компрессии, Count-Min для редких items.
6) Конкретные операции / API
- RPC/HTTP (JSON) методы:
- Suggest
- signature: Suggest(prefix: string, user_id?: string, locale?: string, k: int = 10, fuzzy?: bool = true) -> List[(phrase, score, source)]
- поведение: собрать candidates (prefix + fuzzy if enabled), вычислить score (включая персонализацию по user_id), вернуть top-k.
- RecordQuery
- signature: RecordQuery(query: string, user_id?: string, timestamp?: ts) -> 200
- поведение: публикует событие QueryTyped в stream; локально может инкрементить query-count.
- RecordClick / RecordSelection
- signature: RecordClick(query: string, suggestion_id: string, user_id?: string, timestamp?: ts)
- поведение: публикует SuggestionClicked; consumer обновляет freq/CTR и node top-N.
- InsertPhrase / RemovePhrase (админ)
- сигнатуры для добавления/удаления фраз в словарь, триггерят реиндексацию соответствующих delete-variants и узлов trie.
- BulkRebuild
- для оффлайн/периодической перестройки FST из полного набора частот.
7) Алгоритмы обновления top-N в узле
- Для узла хранится min-heap размера N. При обновлении частоты фразы:
- Если фраза в heap — обновить значение и сделать sift.
- Иначе если heap.size < N — вставить.
- Иначе если newScore > heap.min.score — replace min и reheapify.
- Обновления атомарны (per-node lock или lock-free CAS на структуру).
8) Ошибки и эвристики
- Ограничивать fuzzy-поиск при длинных запросах (cost explosion).
- Для многобайтовых языков (CJK) использовать сегментацию / n-gram вместо char-trie.
- Поддержка транслитерации (если нужно).
9) Замечания по производительности
- Latency budget: use in-memory FST + precomputed top-N to answer in < 5–20 ms.
- Fuzzy generation + edit-distance на shortlist только (не на полный словарь).
- Rate of updates vs rebuild: критичные изменения применяются инкрементно; глобальные перестройки реже (ночные).
Резюме: храните основной словарь в сжатом FST с top-N в узлах, используйте SymSpell/k-gram для typo-tolerance, держите быстрые in-memory счётчики + Count-Min для масштаба, события через stream для реального обновления и асинхронного персистинга; API: Suggest, RecordQuery, RecordClick, Insert/Remove, BulkRebuild. Формула ранжирования — комбинированная (частота, ретроспективность, CTR, персонализация) как в примере выше.