Как обновлять минимальное расстояние при проходе по строке?

Обновление минимального расстояния при проходе по строке

Алгоритм Левенштейна использует динамическое программирование для нахождения минимального количества операций (вставка, удаление, замена), необходимых для преобразования одной строки в другую. Основная идея заключается в построении матрицы размером (m+1) x (n+1), где m и n — длины строк. Каждая ячейка dp[i][j] представляет минимальное расстояние для префиксов длиной i и j.

Как обновляется значение

При проходе по строке значение в ячейке dp[i][j] вычисляется на основе трех возможных операций:

• Удаление: dp[i-1][j] + 1 — удаляем символ из первой строки.
• Вставка: dp[i][j-1] + 1 — вставляем символ во вторую строку.
• Замена: dp[i-1][j-1] + cost, где cost = 0, если символы совпадают, иначе 1.

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

Пример кода на Python

def levenshtein_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if s1[i-1] == s2[j-1] else 1
            dp[i][j] = min(
                dp[i-1][j] + 1,      # удаление
                dp[i][j-1] + 1,      # вставка
                dp[i-1][j-1] + cost  # замена
            )
    return dp[m][n]

Применение

Этот алгоритм широко используется в системах проверки орфографии, биоинформатике (сравнение ДНК), а также в задачах нечеткого поиска. Он позволяет эффективно находить минимальное количество изменений между строками.

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