最小编辑距离

在计算机科学和文本处理领域中，“最小编辑距离”（Levenshtein Distance）是一种衡量两个字符串之间差异度量的方法。它定义为将一个字符串转换成另一个字符串所需的最少单字符编辑操作次数，这些编辑操作包括插入、删除或替换单个字符。

定义与背景

假设我们有两个字符串 s1 和 s2，s1 = "kitten" 而 s2 = "sitting"。我们的目标是找到将 s1 变成 s2 所需的最少编辑次数。在这个例子中，最小编辑距离为 3，可以通过以下方式实现：

• 将 “k” 替换为 “s”
• 插入 “i”
• 插入 “t”

计算方法

计算两个字符串间的最小编辑距离可以使用动态规划来解决。基本思想是构建一个二维矩阵 dp，其中 dp[i][j] 表示将 s1 的前 i 个字符转换成 s2 的前 j 个字符所需的最少编辑次数。

动态规划表初始化

• 当 i = 0 时（即空字符串转为 s2），所需的操作次数等于 s2 的长度，因此 dp[0][j] = j
• 同样地，当 j = 0 时（即 s1 转为空字符串），所需的操作次数等于 s1 的长度，因此 dp[i][0] = i

动态规划方程

对于其他情况：

if s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = min(dp[i-1][j],      # 删除
                   dp[i][j-1],      # 插入
                   dp[i-1][j-1]) + 1 # 替换

实例

考虑 s1 = "kitten" 和 s2 = "sitting" 的例子：

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

从上图可以看出，将 "kitten" 转换为 "sitting" 的最少编辑距离是 3。

应用场景

最小编辑距离广泛应用于自然语言处理、拼写检查、DNA序列比对等领域。例如，在拼写纠错中，可以通过计算输入的拼写和正确单词之间的最小编辑距离来找到最接近的匹配；在文本编辑软件中，则可以用于自动建议更正。

通过理解和应用最小编辑距离算法，我们能够高效地解决许多与字符串相似性有关的实际问题。