距离度量

Levenshtein距离是一种用于衡量两个序列之间差异的字符串度量方法。非正式地讲，两个单词之间的Levenshtein距离是改变一个单词为另一个单词所需的最少单个字符编辑次数（插入、删除或替换）。

定义

从数学上讲，两个字符串a和b（分别具有|a|和|b|长度）之间的Levenshtein距离由以下公式给出：

$Levenshtein$

其中

$Levenshtein$

当相应的符号相同时，d[i][j]等于1，否则等于0，a[i]和b[j]之间的距离表示为d[i][j]。

请注意最小值的第一项对应于从a到b的删除（kitten到sitting），第二项对应于插入，第三项对应于匹配或不匹配，这取决于各自的符号是否相同。

例如，kitten和sitting之间的Levenshtein距离是3，因为以下三个编辑可以将一个变为另一个，且没有办法用少于三个编辑来完成：

这个概念有广泛的应用，例如拼写检查器、光学字符识别的校正系统、模糊字符串搜索以及基于翻译记忆的软件来辅助自然语言翻译。

让我们以寻找字符串ME和MY之间最小编辑距离的简单示例为例。直观上你已经知道这里的最小编辑距离是1操作，即用Y替换E。但让我们尝试以算法的形式来形式化它，以便能够处理更复杂的例子，比如将Saturday转换为Sunday。

为了将上述数学公式应用于ME → MY转换，我们需要事先知道ME → M、M → MY和M → M转换的最小编辑距离。然后我们将需要选择最小的一个，并加上一个操作来转换最后一个字母E → Y。因此，ME → MY转换的最小编辑距离是基于这三个先前可能的转换计算的。

为了进一步解释，请画出以下矩阵：

Levenshtein Matrix

单元格(0:1)包含红色数字1。这意味着我们需要1个操作将M转换为空字符串。这是通过删除M来实现的。这就是为什么这个数字是红色的。
单元格(0:2)包含红色数字2。这意味着我们需要2个操作将ME转换为空字符串。这是通过删除E和M来实现的。
单元格(1:0)包含绿色数字1。这意味着我们需要1个操作将空字符串转换为M。这是通过插入M来实现的。这就是为什么这个数字是绿色的。
单元格(2:0)包含绿色数字2。这意味着我们需要2个操作将空字符串转换为MY。这是通过插入Y和M来实现的。
单元格(1:1)包含数字0。这意味着将M转换为M不需要任何操作。
单元格(1:2)包含红色数字1。这意味着我们需要1个操作将ME转换为M。这是通过删除E来实现的。
等等...

对于我们这样的小矩阵（只有3x3），这看起来很容易。但你可能会发现一些基本概念可以应用于计算更大矩阵的所有这些数字（比如说9x7矩阵用于Saturday → Sunday转换）。

根据公式，你只需要三个相邻单元格(i-1:j)、(i-1:j-1)和(i:j-1)来计算当前单元格(i:j)的数字。我们需要做的就是找到这三个单元格中的最小值，然后在i的行和j的列中有不同字母的情况下加1。

你可以清楚地看到问题的递归性质。

Levenshtein Matrix

让我们为这个问题绘制一个决策图。

最小编辑距离决策图

你可以看到图片上有许多重叠子问题，它们被标记为红色。此外，根据公式，无法减少操作数量并使其小于这三个相邻单元格中的最小值。

你可能还会注意到，矩阵中的每个单元格数字都是基于前面的单元格计算的。因此，这里应用了自底向上的填充缓存技术。

进一步应用这个原则，我们可以解决更复杂的情况，比如Saturday → Sunday转换。

Levenshtein distance