Расстояние Левенштейна: как считать похожесть строк на Python

Коротко

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

Что считаем

Разрешены три операции, каждая стоит единицу:

• вставка символа;
• удаление символа;
• замена символа на другой.

котёнок → котик

котёнок → котенок  (замена ё → е)
котенок → котеок   (удаление н)
котеок  → котик    (замена е → и, удаление о)

расстояние = 3

Практический смысл: чем меньше расстояние, тем строки похожее. Отсюда применения — исправление опечаток, поиск с учётом ошибок, дедупликация записей, сравнение последовательностей ДНК, оценка качества машинного перевода.

Идея решения

Задача решается динамическим программированием. Заведём таблицу dp, где

dp[i][j] — расстояние между первыми i символами первой строки и первыми j символами второй.

Базовые случаи очевидны:

• dp[i][0] = i — чтобы превратить строку длины i в пустую, нужно i удалений;
• dp[0][j] = j — чтобы получить строку длины j из пустой, нужно j вставок.

Переход. Смотрим на последние символы a[i-1] и b[j-1]:

Если они совпадают — правка не нужна, ответ такой же, как для строк на символ короче:

dp[i][j] = dp[i-1][j-1]

Если различаются — выбираем самый дешёвый из трёх вариантов:

dp[i][j] = 1 + min(
    dp[i-1][j],     # удалили символ из первой строки
    dp[i][j-1],     # вставили символ в первую строку
    dp[i-1][j-1]    # заменили символ
)

Реализация

def levenshtein(a: str, b: str) -> int:
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    # база: превращение в пустую строку и обратно
    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]      # символы совпали
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],                # удаление
                    dp[i][j - 1],                # вставка
                    dp[i - 1][j - 1],            # замена
                )

    return dp[n][m]


print(levenshtein('котёнок', 'котик'))   # 3
print(levenshtein('kitten', 'sitting'))  # 3
print(levenshtein('', 'abc'))            # 3

Таблица в действии

Посмотрим на kitten → sitting:

        ''  s   i   t   t   i   n   g
    ''   0  1   2   3   4   5   6   7
    k    1  1   2   3   4   5   6   7
    i    2  2   1   2   3   4   5   6
    t    3  3   2   1   2   3   4   5
    t    4  4   3   2   1   2   3   4
    e    5  5   4   3   2   2   3   4
    n    6  6   5   4   3   3   2   3

Ответ в правом нижнем углу — 3. Путь: k→s (замена), e→i (замена), вставка g.

Оптимизация памяти

Матрица на две строки по 10 000 символов займёт 100 миллионов ячеек. Но заметьте: для вычисления строки i нужна только строка i-1. Значит хранить всю таблицу незачем.

def levenshtein_optimized(a: str, b: str) -> int:
    # меняем местами, чтобы память зависела от более короткой строки
    if len(a) < len(b):
        a, b = b, a

    previous = list(range(len(b) + 1))

    for i, ca in enumerate(a, start=1):
        current = [i] + [0] * len(b)

        for j, cb in enumerate(b, start=1):
            if ca == cb:
                current[j] = previous[j - 1]
            else:
                current[j] = 1 + min(previous[j], current[j - 1], previous[j - 1])

        previous = current

    return previous[-1]


print(levenshtein_optimized('kitten', 'sitting'))   # 3

Память стала O(min(n, m)). Время осталось O(n·m) — от него в общем случае избавиться нельзя.

Восстановление операций

Иногда нужно не только число, но и сами правки. Для этого идём по таблице от правого нижнего угла назад, определяя, откуда пришло значение.

def edit_operations(a: str, b: str) -> list[str]:
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

    ops = []
    i, j = n, m

    while i > 0 or j > 0:
        if i > 0 and j > 0 and a[i - 1] == b[j - 1]:
            i, j = i - 1, j - 1
        elif i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + 1:
            ops.append(f'заменить {a[i-1]!r} на {b[j-1]!r} (позиция {i-1})')
            i, j = i - 1, j - 1
        elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            ops.append(f'удалить {a[i-1]!r} (позиция {i-1})')
            i -= 1
        else:
            ops.append(f'вставить {b[j-1]!r} (позиция {i})')
            j -= 1

    return ops[::-1]


for op in edit_operations('kitten', 'sitting'):
    print(op)
# заменить 'k' на 's' (позиция 0)
# заменить 'e' на 'i' (позиция 4)
# вставить 'g' (позиция 6)

Обратите внимание: восстановление требует полной таблицы, поэтому оптимизацию памяти здесь применить нельзя.

Родственные метрики

Расстояние Дамерау-Левенштейна добавляет четвёртую операцию — перестановку соседних символов. Опечатка тавр вместо твар при обычном Левенштейне стоит 2, при Дамерау — 1. Для исправления опечаток это точнее, потому что перестановка соседей — очень частая ошибка ввода.

Расстояние Хэмминга — только замены, строки обязаны быть одной длины. Проще и быстрее, применяется в теории кодирования.

Наибольшая общая подпоследовательность (LCS) — разрешены только вставки и удаления, без замен. Лежит в основе diff в системах контроля версий.

Нормализация: как получить процент похожести

Само расстояние без контекста мало говорит: 3 правки на строке из 5 символов — много, на строке из 100 — почти ничего. Обычно приводят к отношению:

def similarity(a: str, b: str) -> float:
    if not a and not b:
        return 1.0
    return 1 - levenshtein_optimized(a, b) / max(len(a), len(b))


print(round(similarity('котёнок', 'котик'), 2))   # 0.57

Оптимизация для практики

Полная таблица O(n·m) дорога при массовых сравнениях. Два приёма из реальных систем:

Ранняя отсечка по длине. Если разница длин больше допустимого порога, расстояние точно больше — считать не нужно.

if abs(len(a) - len(b)) > max_distance:
    return max_distance + 1

Ограниченная полоса. Если нас интересует только «расстояние не больше k», достаточно считать ячейки в полосе шириной 2k+1 вокруг диагонали. Сложность падает до O(n·k).

В Python для боевых задач стоит взять готовую библиотеку rapidfuzz — она написана на C++ и работает на порядки быстрее чистого Python.

Частые ошибки

Забытая инициализация первой строки и столбца. Без базовых случаев вся таблица посчитается неверно.

Путаница между индексами строк и символов. dp[i][j] соответствует символам a[i-1] и b[j-1] — смещение на единицу постоянно ловит новичков.

Симметричное сравнение при разных стоимостях операций. Если вставка и удаление стоят по-разному, расстояние перестаёт быть симметричным, и d(a,b) != d(b,a).

Использование в цикле по большому словарю. Сравнение слова со ста тысячами вариантов через Левенштейна — это секунды. Для поиска по словарю применяют BK-деревья или автоматы Левенштейна.

Что запомнить

• Расстояние Левенштейна — минимальное число вставок, удалений и замен.
• Решается динамическим программированием за O(n·m).
• Совпали символы — берём диагональ; не совпали — минимум из трёх соседей плюс единица.
• Память сводится к O(min(n, m)), если не нужно восстанавливать операции.
• Для исправления опечаток точнее вариант Дамерау-Левенштейна с перестановками.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→