编辑距离，也称为编辑距离，是评估两个字符串之间相似性的基本指标。它计算将一个字符串转换为另一字符串所需的最少操作数。这些操作包括：

1. 插入：添加一个字符。
2. 删除：删除一个字符。
3. 替换：将一个字符替换为另一个字符。

这个概念是许多现代应用的核心，例如拼写检查、模糊搜索和 DNA 序列比较。

数学概念

长度分别为 ( n ) 和 ( m ) 的两个字符串 ( A ) 和 ( B ) 之间的编辑距离可以使用动态规划方法来计算。我们定义一个大小为 ((n 1) \times (m 1)) 的矩阵 ( D )，其中每个条目 ( D[i][j] ) 表示转换 ( A ) 的前 ( i ) 个字符的最小成本进入 ( B ) 的前 ( j ) 个字符。

递推关系如下：

Python实现

这是一个计算 Levenshtein 距离的简单 Python 实现：

def levenshtein_distance(a, b): n、m = len(a)、len(b) dp = [[0] * (m 1) for _ in range(n 1)] 对于范围 (n 1) 内的 i： 对于范围 (m 1) 内的 j： 如果我==0： dp[i][j] = j elif j == 0： dp[i][j] = i elif a[i - 1] == b[j - 1]： dp[i][j] = dp[i - 1][j - 1] 别的： dp[i][j] = 1 分钟(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) 返回 dp[n][m] # 用法示例 print(levenshtein_distance("kitten", "sitting")) # 输出：3

def levenshtein_distance(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m   1) for _ in range(n   1)]

    for i in range(n   1):
        for j in range(m   1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif 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]

# Example usage
print(levenshtein_distance("kitten", "sitting"))  # Output: 3

实际应用

1.

拼写检查

拼写检查器使用编辑距离来建议拼写错误的更正。例如，如果您输入 helo，它可能会建议 hello 或 Hero。

2.

模糊搜索

在搜索引擎中，即使用户出现拼写错误或拼写错误，Levenshtein 也能帮助返回结果。

3.

DNA比较

在生物信息学中，这个距离有助于测量两个 DNA 序列之间的相似性，其中每个操作代表一个潜在的突变。

4.

身份验证和欺诈检测

检测身份欺诈的系统可以将用户输入与现有记录进行比较，以解决微小的文本差异。

优化：减少内存的编辑距离

经典算法使用完整矩阵，这可能会占用大量内存。幸运的是，它可以优化为仅使用两行内存，因为每个 ( D[i][j] ) 仅取决于 ( D[i-1][j] ), ( D[i][j-1] ), 和 ( D[i-1][j-1] ).

defoptimized_levenshtein(a, b): n、m = len(a)、len(b) 上一个 = 列表(范围(m 1)) 当前 = [0] * (m 1) 对于范围 (1, n 1) 中的 i： 当前[0] = 我 对于范围 (1, m 1) 内的 j： 插入 = curr[j - 1] 1 删除 = 上一个[j] 1 替代 = prev[j - 1]（如果 a[i - 1] == b[j - 1] 则为 0，否则为 1） curr[j] = min(插入、删除、替换) 上一个，当前 = 当前，上一个 返回上一个[米] # 用法示例 print(optimized_levenshtein("kitten", "sitting")) # 输出：3

def levenshtein_distance(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m   1) for _ in range(n   1)]

    for i in range(n   1):
        for j in range(m   1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif 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]

# Example usage
print(levenshtein_distance("kitten", "sitting"))  # Output: 3

结论

编辑距离是一种强大的、多功能的工具，广泛应用于各个领域。虽然易于掌握，但其优化和复杂的应用凸显了其在现代系统中的价值。

为了进一步探索，请考虑诸如 Damerau-Levenshtein 距离之类的变体，它可以解释换位。您现在可以将此工具集成到您的项目中，或以您的深刻理解给您的同行留下深刻的印象！

对编辑距离有疑问或想法吗？在评论中分享它们！ ？