Расстояние Левенштейна

Коротко: о чём здесь пойдёт речь

Расстояние Левенштейна (Levenshtein distance) — это минимальное число вставок, удалений и замен символов, необходимых, чтобы превратить строку s в строку t.

Например, возьмём слово kitten: преобразование kitten → sitting требует 3 операции: k→s (замена), e→i (замена), ∅→g (вставка). Следовательно, d("kitten", "sitting") = 3.

Зачем это нужно?

Вы никогда не задумывались, каким образом ваш компьютер или поисковая строка Google понимает, что вы имели в виду, и как она исправляет ошибки? Причём эта способность появилась ещё на раннем этапе развития NLP. Всё это возможно благодаря данному незамысловатому подходу (да, знаю: сначала выглядит страшно, но поверьте, дальше будет проще).

Небольшой исторический экскурс

Метрику предложил академик Владимир Левенштейн в 1965 году при изучении последовательностей 0–1 (проще говоря, при работе с битовыми операциями). В итоге была получена следующая рекурсивная формула для расчёта схожести строк/последовательностей:

Позже, в 1974 году, при решении задачи исправления строк (String-to-string correction problem) Роберт А. Вагнер и Майкл Дж. Фишер разработали одноимённый алгоритм Вагнера—Фишера, о котором мы подробнее поговорим далее. Данный алгоритм позволил эффективно рассчитывать расстояние Левенштейна став основой для большинства алгоритмов автокоррекции текста (правда уже в более оптимизированном виде).

Псевдокод алгоритма

Пусть d(i, j) — редакционное расстояние между первыми i символами строки s и первыми j символами строки t.

Граничные условия:

• d(0, j) = j
• d(i, 0) = i

Рекуррентное соотношение для i > 0, j > 0:

d(i, j) = min(
    d(i-1, j) + 1,                 # удаление
    d(i, j-1) + 1,                 # вставка
    d(i-1, j-1) + [s[i] != t[j]]   # замена (0, если символы равны)
)

Это классический алгоритм Вагнера—Фишера. Сложность по времени — O(mn), где m = len(s), n = len(t).

Для наглядности можно поэкспериментировать с интерактивной демонстрацией здесь.

Минимальная реализация на Python

def levenshtein(s: str, t: str) -> int:
    if s == t:
        return 0
    if len(s) < len(t):
        s, t = t, s  # пусть s — не короче t
    prev = list(range(len(t) + 1))
    for i, cs in enumerate(s, 1):
        curr = [i]
        for j, ct in enumerate(t, 1):
            ins = curr[j-1] + 1
            delete = prev[j] + 1
            sub = prev[j-1] + (cs != ct)
            curr.append(min(ins, delete, sub))
        prev = curr
    return prev[-1]

Почему так: хранить всю матрицу не нужно — достаточно двух строк (prev и curr). Это снижает потребление памяти с O(mn) до O(min(m, n)).

Интуитивно

Мы строим матрицу размера (m+1) × (n+1), где каждая ячейка — «лучшая цена» преобразования соответствующих префиксов строк. Решение для всей строки находится в правом нижнем углу матрицы. Благодаря локальной оптимальности переходов (вставка/удаление/замена) получаем глобальный оптимум.

Чтобы оценить близость слов по синтаксису, можно использовать, например, sim = 1 − d / max(len(s), len(t)), где sim ∈ [0, 1]. Так, слово «котик» будет ближе к «кошка», чем к «антрекот», хотя оба содержат повторяющуюся комбинацию «кот».

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

• он фактически читает строки слева направо и сильно штрафует удаления, осебенно на раниних этапах работы алгоритма, например замена в начале работы алгоритма будет иметь большее значение чем замена в конце работы алгоритма (потому что в начале сразу заставит нас спуститься на один элемент диагонали ниже);

по этой причине, например, «котик» может оказаться ближе к «мотик», чем к «кошка» (хотя интуитивно кажется наоборот).

Не спешите расстраиваться: эти недостатки характерны именно для базовой реализации. Более специфичные варианты алгоритма исправляют указанные проблемы.

Какие вариации алгоритма существуют?

• Дамерау—Левенштейн: добавляет операцию транспозиции соседних символов (ab ↔ ba). Полезно для типичных опечаток.
• Jaro / Jaro–Winkler: более устойчивы к перестановкам и «перепутанным» символам; часто лучше подходят для сопоставления имён.
• Расстояние Хэмминга: если строки одинаковой длины и интересуют только замены.
• Токен-уровень: редакционное расстояние по словам (а не символам) — для сравнения фраз и предложений.
• Взвешенный Левенштейн: разные стоимости операций (например, замена i↔j дешевле, чем i↔x), учёт раскладки клавиатуры и частот ошибок.

Когда стоит использовать?

• Автокоррекция и подсказки: поиск ближайших слов к опечатке (например, в поисковой строке).

• Fuzzy join / дедупликация: объединение записей из разных источников (имена, адреса, бренды) при расхождениях в написании (из личного опыта, когда имелся полный списко брендов, и надо было по описанию товара понять к какому бренду он относится).

• Поиск по каталогу: tolerant search, когда пользователь вводит «как слышит» («гугл найди песню, в которой поётся “оппа гангнам стайл”»).

Когда не стоит использовать?

Как вы уже поняли, что Levenshtein подходит только для примитивного поиска и он вам точне не подойдет если:

• важна семантика, а не форма слова

• Если критичны большие перестановки внутри слова: базовая версия их не «понимает» (лучше Jaro–Winkler или токен-уровень).

• Если строки очень длинные, а число удалений слишком большое.

Послесловие

Честно, никогда не задумывался о такой базовой функции как автодополнение, за которой стоит на самом деле очень даже интуитивно понятная и приятная для восприятия математика. Надеюсь мой краткий пересказ работы алгоритма который очень сильно помогает вам в повседневной жизни (не про тебя T9) ваш тоже заинтерисовал и вы немного расширили свой горизонт знаний, и вы так же приоткрыли тайну которая стоит за поисковой строкой вашего браузера или вордовского документа.