В мире обработки текста и естественного языка измерение сходства или различия между двумя строками является распространенной задачей. Алгоритм расстояния Левенштейна, также известный как расстояние редактирования, обеспечивает количественную меру минимального количества операций (вставок, удалений и замен), необходимых для преобразования одной строки в другую. В этой статье блога мы рассмотрим различные методы расчета расстояния Левенштейна в Python, используя разговорный язык и практические примеры кода.

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

def levenshtein_distance_recursive(s1, s2):
    if len(s1) == 0:
        return len(s2)
    if len(s2) == 0:
        return len(s1)

    if s1[0] == s2[0]:
        return levenshtein_distance_recursive(s1[1:], s2[1:])

    substitute = levenshtein_distance_recursive(s1[1:], s2[1:])
    delete = levenshtein_distance_recursive(s1[1:], s2)
    insert = levenshtein_distance_recursive(s1, s2[1:])

    return 1 + min(substitute, delete, insert)

Метод 2: динамическое программирование (табуляция)
Подход грубой силы может быть неэффективен для больших строк из-за избыточных вычислений. Динамическое программирование предлагает оптимизированное решение за счет использования 2D-таблицы для хранения промежуточных результатов. Мы строим таблицу итеративно, избегая повторяющихся вычислений. Давайте посмотрим, как это работает:

def levenshtein_distance_dp(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):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j])

    return dp[m][n]

Метод 3: динамическое программирование (мемоизация)
Другой подход к динамическому программированию — использование мемоизации. Этот метод предполагает кэширование результатов ранее вычисленных подзадач, чтобы избежать избыточных вычислений. Вот пример реализации расстояния Левенштейна с помощью мемоизации:

def levenshtein_distance_memo(s1, s2, memo={}):
    if (s1, s2) in memo:
        return memo[(s1, s2)]

    if len(s1) == 0:
        return len(s2)
    if len(s2) == 0:
        return len(s1)

    if s1[0] == s2[0]:
        result = levenshtein_distance_memo(s1[1:], s2[1:], memo)
    else:
        substitute = levenshtein_distance_memo(s1[1:], s2[1:], memo)
        delete = levenshtein_distance_memo(s1[1:], s2, memo)
        insert = levenshtein_distance_memo(s1, s2[1:], memo)
        result = 1 + min(substitute, delete, insert)

    memo[(s1, s2)] = result
    return result