Быстрое вычисление расстояния Левенштейна с помощью trie

Классический пост Стива Ханова 2009 года об эффективном нечётком поиске по словарю. Задача: для слова с опечаткой найти все словарные слова в пределах N правок. Наивный подход слишком медлителен для больших словарей. Подход на основе trie работает в 300 раз быстрее.

Наивный подход

Сравнить запрос с каждым словом в словаре, используя стандартный алгоритм динамического программирования для расстояния Левенштейна. Для каждой пары слов заполняется таблица N×M, где каждая ячейка равна минимуму из:

• Ячейка сверху + 1 (удаление)
• Ячейка слева + 1 (вставка)
• Ячейка по диагонали сверху-слева + 0 или 1 (совпадение или замена)

Сложность: O(words × max_length²). Для словаря из 98 568 слов: 4.5 секунды.

Основная идея

При сравнении "food" со словом "care", а затем с "cars", наивный подход пересчитывает всю таблицу с нуля. Но у "care" и "cars" общий префикс. Строки таблицы Левенштейна для "c", "ca", "car" полностью совпадают - отличается только последняя строка.

Trie хранит слова, объединяя общие префиксы в единые пути. Если обходить trie в глубину, слова обрабатываются именно в том порядке, который максимизирует повторное использование строк.

Алгоритм

Рекурсивный обход в глубину (DFS) по trie. Каждый вызов принимает:

• Текущий узел trie
• Букву в этом узле
• Искомое слово
• Предыдущую строку (из родительского узла)
• Аккумулятор результатов
• Максимально допустимое редакционное расстояние

Каждый узел вычисляет одну строку:

def searchRecursive(node, letter, word, previousRow, results, maxCost):
    currentRow = [previousRow[0] + 1]
    
    for column in range(1, len(word) + 1):
        insertCost = currentRow[column - 1] + 1
        deleteCost = previousRow[column] + 1
        replaceCost = previousRow[column - 1]
        if word[column - 1] != letter:
            replaceCost += 1
        currentRow.append(min(insertCost, deleteCost, replaceCost))
    
    # If this node completes a word and cost is acceptable
    if node.word and currentRow[-1] <= maxCost:
        results.append((node.word, currentRow[-1]))
    
    # Early termination: if min(row) > maxCost, no word below can match
    if min(currentRow) <= maxCost:
        for letter, child in node.children.items():
            searchRecursive(child, letter, word, currentRow, results, maxCost)

Раннее отсечение - ключевой момент. Если минимальное значение в текущей строке превышает maxCost, любое слово в этом поддереве окажется слишком далеко. Вся ветка отсекается целиком.

Производительность

Тот же словарь на 98 568 слов: 0.014 секунды. Более чем в 300 раз быстрее.

Новая оценка сложности: O(max_length × trie_nodes). В trie меньше узлов, чем суммарное количество символов во всём словаре, поскольку префиксы объединены.

Практическое применение

Автор использовал этот подход для RhymeBrain. После импорта набора данных Google N-grams (2.6 миллиона слов) запросы всё ещё выполнялись всего за 19-50 мс на нетбуке с процессором 1 ГГц. Без кэширования, без предварительных вычислений - только trie и алгоритм.

Альтернативы

Корректор опечаток Питера Норвига - генерация всех возможных мутаций запроса с 1 правкой и проверка их наличия в словаре. Быстро работает для расстояния редактирования 1, но "быстро ломается" на больших расстояниях, так как количество мутаций растёт экспоненциально.

Автоматы Левенштейна - построение регулярного выражения / NFA, сопоставляющего все строки в пределах N правок, с последующим пересечением со словарём. Сложнее в реализации ("огромные горы кода"), но может работать быстрее на очень больших словарях.

Память

Trie потребляет много памяти. В статье упоминаются последующие работы со структурами DAWG (Directed Acyclic Word Graph), которые объединяют не только префиксы, но и суффиксы, кардинально снижая число узлов.

См. также inverted-index о другом подходе к поисковому индексированию, full-text-search-indexeddb о ещё одной реализации нечёткого поиска.