Лексический поиск

Релизнуто 10.06.2026

Узнали 1 073 асошника

Лексический поиск — это извлечение и ранжирование документов по совпадению термов запроса с термами, сохраненными в индексе. Запрос и документы проходят анализ текста: разбиение на токены, нормализацию, иногда стемминг, лемматизацию, удаление стоп-слов и расширение синонимами. После этого поисковый движок берет списки вхождений из инвертированного индекса, объединяет или пересекает их и считает оценку документа.

Результат — список документов-кандидатов с оценками, совпавшими термами, полями и служебными признаками. Лексический поиск отличается от векторного тем, что опирается на явное совпадение термов или их заранее заданных расширений, а не на близость плотных векторных представлений.

Место в поисковой системе

Контур:

Обход, загрузка или импорт документов.
Разбор документа: выделение полей, языка, кодировки, основного текста, заголовков, метаданных.
Анализ текста: токены, нормализация, стемминг или лемматизация, синонимы, позиции.
Построение инвертированного индекса: term -> [(doc_id, tf, positions, field)].
Лексический поиск: разбор запроса тем же или совместимым анализатором, чтение, отбор кандидатов, BM25/Boolean/phrase/proximity-оценка.
Переупорядочивание: модель ранжирования, правила, персонализация, гибридное слияние с векторным поиском.
Логи, оценка, A/B-тесты, мониторинг задержек и отказов.

Вход:

документы: doc_id, поля title, body, brand, category, anchor, metadata;
индексные структуры: словарь термов, запись, позиции, документные частоты, длины полей, нормы;
запрос: строка пользователя, язык, регион, фильтры, контекст сессии;
обновление: пакетная переиндексация, потоковые обновления или near-real-time сегменты.

Выход:

topK кандидатов: doc_id, оценка, совпавшие термы, поле совпадения, объяснение оценки;
признаки для следующего этапа: BM25 по полям, количество совпавших термов, покрытие запроса, фразовое совпадение, близость термов, длина поля;
системные данные: число просмотренных записей, время чтения индекса, число кандидатов, версия анализатора, версия индекса.

Если первый этап не вернул релевантный документ в глубине передачи, поздняя модель его уже не восстановит. Поэтому для лексического поиска как первого этапа измеряют не только качество верхних позиций, но и полноту кандидатов на глубине K: например, Recall@100, Recall@1000, покрытие по классам запросов и долю нулевых выдач.

Место в рекомендательной системе

В рекомендациях лексический поиск не заменяет модель предпочтений. Он нужен там, где есть текстовый сигнал:

пользователь ввел поисковый запрос внутри каталога;
товар, видео, статья или профиль имеют текстовые поля;
сессия пользователя превращается в короткий текстовый запрос: последние просмотренные категории, бренды, атрибуты;
нужно быстро получить кандидатов до дорогого скоринга.

Контур рекомендаций:

Сбор событий: показы, клики, покупки, сохранения, пропуски.
Построение признаков: текст объекта, категории, бренды, атрибуты, пользовательские интересы.
Лексический отбор кандидатов: запрос из сессии или профиля ищет объекты по title, description, category.
Скоринг: модель считает вероятность клика, покупки, досмотра или другого действия.
Переупорядочивание: бизнес-ограничения, разнообразие, свежесть, дедупликация.
Эксперимент: кандидатная полнота по журналу событий и метрики.

Финальная релевантность зависит от модели, которая использует события, признаки пользователя, контекст, свежесть и ограничения показа.

История и происхождение

Техническое ядро лексического поиска выросло из Boolean retrieval и инвертированного индекса: вместо полного прохода по коллекции система хранит словарь термов и списки документов, где каждый терм встретился. Это решило задачу быстрого поиска по большим текстовым коллекциям.

Следующий шаг — статистическое взвешивание термов. Karen Spärck Jones в работе 1972 года сформулировала статистическую специфичность терма: редкие термы должны весить больше частых, потому что лучше различают документы. Salton, Wong и Yang в 1975 году описали векторную модель: документ представляется вектором весов термов, а близость можно считать через скалярное произведение или угол между векторами.

BM25 добавил две инженерные вещи, которых не хватает простому tf-idf: насыщение по частоте терма и нормализацию по длине документа. Robertson и Zaragoza описывают BM25 внутри вероятностной модели релевантности; в Lucene и OpenSearch BM25 стал стандартной функцией оценки для текстовых полей.

Современная граница термина проходит не по возрасту метода, а по индексному представлению. Если система ищет по явному разреженному словарю и записям, это лексическое семейство. Если система ищет ближайшие плотные векторы, это векторный поиск. Гибридная система запускает оба отбора и сливает результаты на ранжировании.

Математическая и алгоритмическая основа

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

Пусть V — словарь термов, а P_t — список вхождений для терма t.

Минимальная запись:

(doc_id, tf, positions)

где:

doc_id — внутренний идентификатор документа;
tf — сколько раз терм встретился в документе или поле;
positions — позиции терма в поле, нужны для фраз и близости.

Для запроса q = {t1, t2, ..., tm}:

C_AND(q) = P_t1 ∩ P_t2 ∩ ... ∩ P_tm
C_OR(q)  = P_t1 ∪ P_t2 ∪ ... ∪ P_tm

AND дает меньше кандидатов и выше точность, но может потерять релевантные документы из-за несовпадения словаря. OR дает больше кандидатов, но требует ранжирования и отсечения слабых документов.

Сложность построения индекса — O(T), где T — число токенов в коллекции. Память — O(number_of_postings + positions). Запрос в наивном варианте стоит O(sum |P_t|) по термам запроса. На практике движок использует сжатие, skip-структуры, WAND, Block-Max WAND и другие способы не смотреть документы, которые не могут попасть в topK.

TF-IDF

Базовый вес терма:

w(t, d) = tf(t, d) * idf(t)
idf(t) = log(N / df(t))

где:

N — число документов;
df(t) — число документов, где встретился терм t;
tf(t, d) — частота терма в документе.

Вес растет, если терм часто встречается в документе. Вес падает, если терм встречается во многих документах коллекции. Линейный tf плохо ведет себя на длинных документах: десятое повторение терма обычно не в десять раз полезнее первого.

BM25

Классическая форма BM25:

score(q, d) =
Σ_{t ∈ q ∩ d} idf(t) *
(tf(t,d) * (k1 + 1)) /
(tf(t,d) + k1 * (1 - b + b * |d| / avgdl))

где:

tf(t,d) — частота терма в документе;
idf(t) — редкость терма в коллекции;
|d| — длина документа или поля;
avgdl — средняя длина документа или поля;
k1 — сила насыщения по tf;
b — сила нормализации по длине.

k1 управляет тем, насколько быстро повторения терма перестают добавлять оценку. При малом k1 насыщение быстрое. При большом k1 поведение ближе к линейному tf. b = 0 отключает нормализацию по длине; b = 1 делает ее полной. В Lucene значения по умолчанию: k1 = 1.2, b = 0.75 [5].

Lucene использует вариант IDF:

idf(t) = log(1 + (N - df(t) + 0.5) / (df(t) + 0.5))

Это не единственная форма BM25. При сравнении экспериментов нужно фиксировать движок, версию, функцию похожести, анализатор, схему полей и глубину выдачи.

Фразы и близость

BM25 в базовом виде не видит порядок слов. Для запроса "inverted index" нужны позиции:

exists p:
  p ∈ positions("inverted", d)
  and p + 1 ∈ positions("index", d)

Для близости можно считать минимальное окно, в котором встретились все термы запроса. Чем меньше окно, тем сильнее сигнал. Это все еще лексический поиск: система работает с термами и позициями, а не с плотными векторами.

Минимальный пример

Документы:

d1: car insurance pricing for young drivers
d2: automobile insurance pricing for young drivers
d3: car rental at airport with pickup
d4: vector search with embeddings and nearest neighbors

Запрос:

auto coverage

Без расширения анализатор получает термы:

auto, coverage

В индексе таких термов нет. Кандидатов нет. Recall@2 = 0.

Если добавить расширение:

auto -> car, automobile
coverage -> insurance

запрос превращается в:

car, automobile, insurance

Теперь d1 и d2 попадают в кандидаты. Recall@2 растет до 1.0. Но появляется новый риск: d2 может обогнать d1, потому что automobile встречается реже, получает больший IDF и добавляет сильный вес. Если по оценкам релевантности d1 лучше d2, NDCG@2 падает. Синонимы чинят словарное несовпадение, но могут испортить порядок.

Пример на Python

Код показывает: построение инвертированного индекса, отбор кандидатов через запись, расчет BM25 и метрики Recall@K/NDCG@K. Пример специально короткий. Он не имитирует Lucene, но показывает механику первого этапа поиска.

Установка

# Нужен только Python 3.11+
# Внешние библиотеки не нужны

Код

from __future__ import annotations

import math
import re
from collections import Counter, defaultdict
from typing import Dict, Iterable, List, Tuple


def analyze(text: str) -> List[str]:
    return re.findall(r"[a-z0-9]+", text.lower())


class BM25Index:
    def __init__(self, docs: Dict[str, str], k1: float = 1.2, b: float = 0.75) -> None:
        if not docs:
            raise ValueError("docs must not be empty")
        if k1 < 0:
            raise ValueError("k1 must be non-negative")
        if not 0 <= b <= 1:
            raise ValueError("b must be in [0, 1]")

        self.raw_docs = docs
        self.docs = {doc_id: analyze(text) for doc_id, text in docs.items()}
        self.k1 = k1
        self.b = b
        self.N = len(self.docs)
        self.avgdl = sum(len(tokens) for tokens in self.docs.values()) / self.N

        self.tf: Dict[str, Counter[str]] = {}
        self.df: Counter[str] = Counter()
        self.inverted: dict[str, list[tuple[str, int]]] = defaultdict(list)

        for doc_id, tokens in self.docs.items():
            counts = Counter(tokens)
            self.tf[doc_id] = counts

            for term, freq in counts.items():
                self.df[term] += 1
                self.inverted[term].append((doc_id, freq))

    def idf(self, term: str) -> float:
        df = self.df.get(term, 0)
        if df == 0:
            return 0.0
        return math.log(1.0 + (self.N - df + 0.5) / (df + 0.5))

    def score_doc(self, query_terms: Iterable[str], doc_id: str) -> float:
        dl = len(self.docs[doc_id])
        norm = self.k1 * (1.0 - self.b + self.b * dl / self.avgdl)

        score = 0.0
        for term in query_terms:
            tf = self.tf[doc_id].get(term, 0)
            if tf == 0:
                continue

            score += self.idf(term) * (tf * (self.k1 + 1.0)) / (tf + norm)

        return score

    def search(
        self,
        query: str,
        expansion: Dict[str, List[str]] | None = None,
        k: int = 10,
    ) -> tuple[list[str], list[tuple[str, float]]]:
        query_terms = analyze(query)

        if expansion:
            expanded: list[str] = []
            seen: set[str] = set()

            for term in query_terms:
                for variant in expansion.get(term, [term]):
                    if variant not in seen:
                        expanded.append(variant)
                        seen.add(variant)

            query_terms = expanded

        candidate_ids: set[str] = set()
        for term in query_terms:
            candidate_ids.update(doc_id for doc_id, _ in self.inverted.get(term, []))

        ranking = sorted(
            ((doc_id, self.score_doc(query_terms, doc_id)) for doc_id in candidate_ids),
            key=lambda item: (-item[1], item[0]),
        )

        return query_terms, ranking[:k]


def dcg(grades: list[int]) -> float:
    return sum((2**grade - 1) / math.log2(rank + 2) for rank, grade in enumerate(grades))


def ndcg_at_k(ranking: list[str], qrels: dict[str, int], k: int) -> float:
    grades = [qrels.get(doc_id, 0) for doc_id in ranking[:k]]
    ideal = sorted(qrels.values(), reverse=True)[:k]
    ideal_dcg = dcg(ideal)

    if ideal_dcg == 0:
        return 0.0

    return dcg(grades) / ideal_dcg


def recall_at_k(ranking: list[str], qrels: dict[str, int], k: int) -> float:
    relevant = {doc_id for doc_id, grade in qrels.items() if grade > 0}

    if not relevant:
        return 0.0

    return len(set(ranking[:k]) & relevant) / len(relevant)


def print_run(
    label: str,
    terms: list[str],
    ranking: list[tuple[str, float]],
    docs: dict[str, str],
    qrels: dict[str, int],
) -> None:
    ids = [doc_id for doc_id, _ in ranking]

    print(f"\n{label}")
    print("terms:", terms)

    for doc_id, score in ranking:
        print(f"{doc_id} {score:.3f} | {docs[doc_id]}")

    print("Recall@2:", round(recall_at_k(ids, qrels, 2), 3))
    print("NDCG@2:", round(ndcg_at_k(ids, qrels, 2), 3))


if __name__ == "__main__":
    docs = {
        "d1": "car insurance pricing for young drivers",
        "d2": "automobile insurance pricing for young drivers",
        "d3": "car rental at airport with pickup",
        "d4": "vector search with embeddings and nearest neighbors",
    }

    qrels = {
        "d1": 3,
        "d2": 2,
    }

    index = BM25Index(docs)
    query = "auto coverage"

    terms, ranking = index.search(query, k=3)
    print_run("Без расширения", terms, ranking, docs, qrels)

    expansion = {
        "auto": ["car", "automobile"],
        "coverage": ["insurance"],
    }

    terms_expanded, ranking_expanded = index.search(query, expansion=expansion, k=3)
    print_run("С расширением запроса", terms_expanded, ranking_expanded, docs, qrels)

Ожидаемый вывод

Без расширения
terms: ['auto', 'coverage']
Recall@2: 0.0
NDCG@2: 0.0

С расширением запроса
terms: ['car', 'automobile', 'insurance']
d2 1.929 | automobile insurance pricing for young drivers
d1 1.409 | car insurance pricing for young drivers
d3 0.705 | car rental at airport with pickup
Recall@2: 1.0
NDCG@2: 0.834

Ограничения примера

В примере нет полей, позиций, сжатия, сегментов, WAND, Block-Max WAND, шардирования, обновлений индекса, разных анализаторов для индекса и запроса, query-time и index-time синонимов. Это учебная механика.

Метрики

Метрики качества отбора кандидатов

Для первого этапа поиска главная метрика — Recall@K на глубине передачи:

Recall@K = |Retrieved@K ∩ Relevant| / |Relevant|

Если лексический этап отдает 1000 кандидатов в модель ранжирования, нужно мерить Recall@1000, а не только NDCG@10. Иначе можно получить красивый верх выдачи на легких запросах и тихо терять релевантные документы на словарном несовпадении.

Дополнительно:

доля нулевых выдач;
доля запросов, где найден меньше чем K кандидатов;
покрытие по типам запросов: брендовые, навигационные, категорийные, длинные, с опечатками, с артикулом;
Recall@K по сегментам языка, категории, длины запроса.

Метрики ранжирования

Для отсортированного списка:

Precision@K — доля релевантных документов в верхних K;
MAP — средняя точность в позициях, где найден релевантный документ;
MRR — обратная позиция первого релевантного документа;
NDCG@K — качество порядка при graded relevance (радуированная релевантность или многоуровневая релевантность).

NDCG@K нужен, когда есть несколько уровней релевантности. Например, документ с точным ответом лучше документа с частичным совпадением.

Системные метрики

Лексический поиск может быть качественным и все равно непригодным в проде, если он ломает задержку или память. Мерить нужно:

p50/p95/p99 задержки по фазам: анализ запроса, чтение записи, скоринг, сортировка, переупорядочивание;
число просмотренных записей;
число полностью оцененных документов;
размер индекса;
размер словаря;
долю запросов с timeout;
refresh lag: задержку между записью документа и видимостью в поиске;
merge time и merge backlog;
heap, page cache, долю cache miss;
число документов в сегментах и долю удаленных документов до слияния.

Средняя задержка не годится как основная системная метрика. Хвостовые запросы с длинными записями ломают SLA (Service Level Agreement — соглашение об уровне сервиса).

Online-метрики

Клики нельзя читать как прямую релевантность: позиция, сниппет, бренд, цена, картинка и доверие к источнику смещают поведение. Для online-проверки нужны A/B-тесты или interleaving (Interleaving — способ сравнить две поисковые системы (или два ранжирования) на реальных пользователях быстрее и точнее, чем через обычный A/B-тест).

Смотреть стоит:

CTR по позициям;
reformulation rate: доля пользователей, которые сразу меняют запрос;
zero-results recovery: что делает пользователь после пустой выдачи;
add-to-cart, purchase, save, read, watch — в зависимости от продукта;
latency guardrails: p95/p99 не должны ухудшаться сильнее заданного порога;
доля запросов, где лексический этап не вернул кандидатов для модели.

Ограничения и отказы

1. Словарное несовпадение

Запрос и документ говорят об одном, но используют разные слова:

auto coverage
car insurance
automobile insurance

BM25 не найдет документ без общего терма. Синонимы, нормализация, исправление опечаток, расширение документов и гибридный поиск уменьшают проблему, но каждый метод добавляет цену: рост индекса, ложные совпадения, сложность отладки, дополнительную модель или ручной словарь.

2. Несовпадение анализаторов

Если документ индексировали одним анализатором, а запрос разбирают другим, точное совпадение ломается до ранжирования. Это частая причина нулевых выдач после безобидного изменения стеммера, стоп-слов или синонимов.

Нужно версионировать:

анализатор индекса;
анализатор запроса;
словарь синонимов;
правила нормализации;
схему полей;
версию движка.

Любое изменение анализатора требует теста на qrels, снимка _analyze-вывода и часто полной переиндексации.

3. Синонимы

Синонимы чинят recall, но легко портят precision и NDCG. Проблемы:

широкие синонимы: apple -> fruit, company;
порядок фильтров: stop-filter до synonym-filter может сделать правило невалидным;
рост памяти при больших synonym maps;
разные результаты при index-time и query-time расширении;
невозможность объяснить, почему документ поднялся, если не логировать расширенные термы.

Синонимы нельзя выкатывать как текстовый файл без тестов. Нужны unit-тесты анализатора, offline-оценка качества, проверка памяти и откат.

4. Фразы и порядок слов

Запросы вроде "new york" или "inverted index" требуют позиций. Если индекс хранит только doc_id и tf, система не отличит точную фразу от разрозненных терминов в разных частях документа.

Позиции увеличивают индекс, но без них нельзя нормально поддерживать phrase query, proximity scoring и точные подсветки.

5. Длина документа

BM25 нормализует длину, но параметр b не универсален. Длинная статья, товарная карточка и короткий заголовок ведут себя по-разному. Для структурированных документов лучше считать признаки по полям: title, body, brand, category. В BM25F доказательство по полям сначала накапливается по каждому терму, а насыщение применяется после агрегации полевого сигнала.

6. Большие коллекции и хвост задержек

Популярный терм имеет длинный postings list (posting = запись о вхождении терма в конкретный документ, а posting list — список таких записей для одного терма). Запрос из нескольких популярных термов может заставить движок просмотреть много записей и породить хвост задержки. WAND и Block-Max WAND уменьшают число полностью оцененных документов, но хвостовые запросы остаются отдельной проблемой.

Для прода нужны лимиты, профилирование по классам запросов, кэширование, warmup, контроль глубины передачи и наблюдение за p95/p99, а не только за средним временем.

7. Логи без объяснимости

Минимальный лог для отладки лексического поиска:

{
  "query_raw": "auto coverage",
  "query_terms": ["car", "automobile", "insurance"],
  "analyzer_version": "en_v12",
  "index_version": "products_2026_05_31",
  "candidate_count": 3,
  "top_docs": [
    {"doc_id": "d2", "score": 1.929, "matched_terms": ["automobile", "insurance"]},
    {"doc_id": "d1", "score": 1.409, "matched_terms": ["car", "insurance"]}
  ],
  "postings_scanned": 12,
  "latency_ms": {
    "analysis": 1.1,
    "candidate_generation": 3.8,
    "scoring": 0.9
  }
}

Без таких логов команда не отличит проблему анализатора от проблемы ранжирования.

Подытожим

Лексический поиск — это не «поиск по ключевым словам» в обычном смысле. Это индексная и ранжирующая механика: анализ текста, инвертированный индекс, записи, частоты, позиции, BM25, отсечение кандидатов и контроль задержки. Его сила — дешевый и объяснимый первый этап. Его слабость — зависимость от словаря и анализатора. Сильная система не заменяет лексический поиск векторным; она измеряет, где лексический этап теряет кандидатов, и добавляет расширения, поля, фразы, синонимы, модели или гибридный поиск только там, где это дает прирост по Recall@K, NDCG@K и online-метрикам.

Место в поисковой системе

Место в рекомендательной системе

История и происхождение

Математическая и алгоритмическая основа

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

TF-IDF

BM25

Фразы и близость

Минимальный пример

Пример на Python

Установка

Код

Ожидаемый вывод

Ограничения примера

Метрики

Метрики качества отбора кандидатов

Метрики ранжирования

Системные метрики

Online-метрики

Ограничения и отказы

1. Словарное несовпадение

2. Несовпадение анализаторов

3. Синонимы

4. Фразы и порядок слов

5. Длина документа

6. Большие коллекции и хвост задержек

7. Логи без объяснимости

Подытожим

Связные термины

Токен

Лексическая плотность

Семантическая плотность

Интент