Python 中的编辑距离

两个字符串之间的“编辑距离”是指将一个字符串转换为另一个字符串所需的最小操作次数（插入、删除和替换）。这个概念用于各种应用，例如拼写纠正、DNA序列比对等。

例如，“kitten”和“sitting”之间的编辑距离是3，因为需要3个操作才能将“kitten”转换为“sitting”（将“k”改为“s”，将“e”改为“i”，并在末尾添加“g”）。

在 Python 中，我们可以使用 Pylev 库 的 distance 模块来计算两个字符串之间的编辑距离。实现方法如下：

输出

The edit distance between 'kitten' and 'sitting' is: 3

或者，您可以使用动态规划方法自己实现编辑距离算法，实现方法如下：

示例

输出

This code returns the edit distance between str1 and str2 as 3.

动态规划实现可以描述如下：

编辑距离可以使用动态规划方法进行计算。这涉及到创建一个具有m+1 行和n+1 列的二维表 dp，其中m和n分别是两个字符串str1和str2的长度。之后，根据str1和str2中的字符是否匹配，使用一系列规则填充该表。最终结果是存储在dp[m][n]中的str1和str2之间的编辑距离。

动态规划方法的思想是使用二维表 dp来存储中间结果并避免重复计算。dp[i][j]字段存储字符串str1的前i个字符与字符串str2的前j个字符之间的编辑距离。

第一个for 循环使用将空字符串转换为str1或str2所需的 the number of operations 来初始化dp表的第一行和第一列。这与相应字符串的长度相同。

使用第二个 for 循环可以计算两个字符串str1和str2之间的编辑距离。如果两个字符串中的当前字符匹配，则相应的dp条目等于前一个dp条目(dp[i - 1][j - 1])。这意味着将str1转换为str2不需要任何操作。

如果字符不匹配，则相应的dp条目等于三个可能操作：删除、插入和替换的最小值。dp[i][j - 1]条目对应于删除，dp[i - 1][j]条目对应于插入，dp[i - 1][j - 1]条目对应于替换。公式1 + min(...)中的1代表当前操作的成本。for 循环结束后，dp[m][n]条目将包含最终结果，即转换str1到str2所需的最少操作次数。

Levenshtein 使用类似的方法确定两个字符串之间的编辑距离。来自Pylev 包的 distance 函数。不同之处在于pylev 库是用 C 实现的，这使得它比纯 Python 实现快得多。

考虑字符串“kitten”和“sitting”。动态规划表 dp 会如下所示：

每个dp[i][j]条目代表将kitten的前i个字符转换为sitting的前j个字符所需的最小操作次数。

例如，dp[2][2] = 2表示将kitten的前2个字符（ki）转换为sitting的前2个字符（si）需要2次操作。动态规划方法通过在每一步考虑每个可能的 the operation 来逐步填充dp表。