Поиск как у Google: инвертированный индекс, BM25 и Trie

Как работает поиск как у Google: разбор алгоритмов

Вы когда-нибудь задумывались, что происходит за кулисами поисковой строки Google? Каждый день миллионы пользователей вводят запросы, и система мгновенно выдаёт релевантные результаты, исправляет опечатки и предлагает подсказки. В этой статье мы разберём, как устроен такой поиск: от инвертированного индекса до BM25-ранжирования и BK-дерева. Вы узнаете, как реализовать поисковый движок с нуля на Python и когда разумнее использовать готовые решения вроде Atlas Search от MongoDB.

Мы создадим упрощённый поисковый движок, который обрабатывает документы, индексирует их и отвечает на запросы. Вы увидите, как каждый алгоритм вносит вклад в конечный результат, и поймёте, какие компромиссы существуют между производительностью и качеством.

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

Представьте, что у вас есть база данных с миллионами страниц. Как найти все документы, содержащие слово «алгоритм»? Самый наивный способ — перебрать каждую страницу и проверить, есть ли там это слово. Это медленно и неэффективно. Решение — инвертированный индекс. Вместо того чтобы хранить документы и искать по ним, мы храним слова и для каждого слова список документов, где оно встречается.

# Пример структуры инвертированного индекса
inverted_index = {
    'алгоритм': [0, 2, 5],  # ID документов
    'поиск': [1, 2, 3, 5],
    'данные': [0, 4]
}

Такой подход позволяет искать слово за O(1) по хеш-таблице, независимо от количества документов. В реальных системах индекс хранит не только ID документов, но и позиции вхождений, частоту термина и другую информацию для ранжирования.

Токенизация и нормализация

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

import unicodedata

def normalize(word: str) -> str:
    """Убираем диакритические знаки и приводим к нижнему регистру"""
    decomposed = unicodedata.normalize('NFD', word)
    return ''.join(ch for ch in decomposed if unicodedata.category(ch) != 'Mn').lower()

Также стоит удалить стоп-слова (например, «и», «в», «на»), которые не несут смысловой нагрузки. Это уменьшает размер индекса и ускоряет поиск.

Ранжирование BM25: почему один документ важнее другого

Когда у вас есть несколько документов с искомым словом, нужно отсортировать их по релевантности. Классический алгоритм — BM25 (Best Matching 25). Он учитывает три фактора:

• Частота термина (TF): чем чаще слово встречается в документе, тем он релевантнее, но нелинейно.
• Обратная частота документа (IDF): редкие слова важнее частых.
• Длина документа: длинные документы не должны получать преимущество только из-за размера.

import math

def bm25_score(tf, df, total_docs, doc_len, avg_doc_len, k1=1.5, b=0.75):
    """Вычисляет BM25-оценку для термина"""
    idf = math.log((total_docs - df + 0.5) / (df + 0.5) + 1)
    length_norm = 1 - b + b * (doc_len / avg_doc_len)
    saturation = tf * (k1 + 1) / (tf + k1 * length_norm)
    return idf * saturation

Для каждого документа мы суммируем оценки по всем словам запроса. Чем выше сумма, тем релевантнее документ.

Усиление фраз (Phrase Boost)

Иногда пользователь ищет точную фразу, например «машинное обучение». Если мы просто сложим баллы за слова «машинное» и «обучение», документы, где они встречаются далеко друг от друга, могут получить высокий балл. Чтобы исправить это, мы добавляем буст, если слова идут подряд в правильном порядке.

def phrase_boost(doc, phrase):
    """Возвращает True, если фраза встречается в документе"""
    return phrase in doc['text']

Этот буст может умножать итоговый балл на коэффициент, например 1.5.

Исправление опечаток: расстояние Дамерау-Левенштейна

Когда пользователь вводит «полморфизм» вместо «полиморфизм», поисковая система должна предложить правильный вариант. Для этого используется расстояние Дамерау-Левенштейна — метрика, которая считает минимальное количество операций (вставка, удаление, замена, транспозиция) для превращения одной строки в другую.

def damerau_levenshtein(a: str, b: str) -> int:
    """Расстояние Дамерау-Левенштейна между строками a и b"""
    da = {}
    for i, ch in enumerate(a):
        da[ch] = i
    for ch in b:
        if ch not in da:
            da[ch] = 0
    maxdist = len(a) + len(b)
    d = [[maxdist] * (len(b) + 2) for _ in range(len(a) + 2)]
    d[0][0] = maxdist
    for i in range(len(a) + 1):
        d[i + 1][0] = maxdist
        d[i + 1][1] = i
    for j in range(len(b) + 1):
        d[0][j + 1] = maxdist
        d[1][j + 1] = j
    for i in range(1, len(a) + 1):
        db = 0
        for j in range(1, len(b) + 1):
            k = da.get(b[j - 1], 0)
            l = db
            cost = 0 if a[i - 1] == b[j - 1] else 1
            if cost == 0:
                db = j
            d[i + 1][j + 1] = min(
                d[i][j] + cost,          # замена
                d[i + 1][j] + 1,         # вставка
                d[i][j + 1] + 1,         # удаление
                d[k][l] + (i - k - 1) + cost + (j - l - 1)  # транспозиция
            )
        da[a[i - 1]] = i
    return d[len(a) + 1][len(b) + 1]

Транспозиция — это обмен соседних символов, например «dotnte» → «dotnet». Это распространённая ошибка при быстром наборе, и её учёт делает исправление точнее.

BK-дерево: быстрый поиск похожих слов

Если у нас есть словарь из миллионов слов, перебирать все и считать расстояние для каждого — слишком медленно. BK-дерево (Burkhard-Keller) позволяет находить слова в пределах заданного расстояния за O(log n) в среднем. Идея в том, чтобы строить дерево, где каждый узел — слово, а рёбра — расстояния до потомков.

class BKNode:
    def __init__(self, word):
        self.word = word
        self.children = {}  # расстояние -> узел

def bk_insert(root, word):
    if root is None:
        return BKNode(word)
    dist = damerau_levenshtein(root.word, word)
    if dist in root.children:
        bk_insert(root.children[dist], word)
    else:
        root.children[dist] = BKNode(word)

def bk_search(root, query, max_dist):
    """Возвращает слова, расстояние до которых <= max_dist"""
    results = []
    if root is None:
        return results
    dist = damerau_levenshtein(root.word, query)
    if dist <= max_dist:
        results.append(root.word)
    for d, child in root.children.items():
        if d - max_dist <= dist <= d + max_dist:
            results.extend(bk_search(child, query, max_dist))
    return results

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

Практический вывод: что делать прямо сейчас

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

Если вам нужно промышленное решение, обратите внимание на готовые инструменты: Apache Lucene, Elasticsearch или Atlas Search от MongoDB. Они реализуют все эти алгоритмы с оптимизациями и масштабированием. Но знание внутренностей поможет вам правильно настраивать параметры и понимать, почему поиск ведёт себя так, а не иначе.

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