Levenshtein 距离

August 8, 2018 · View on GitHub

Levenshtein距离 是用于测量两个序列之间差异的字符串度量. 一般来说,两个单词之间的 Levenshtein距离 是将 一个单词 更改为 另一个单词 所需的单字符编辑 (插入,删除或替换) 的最小数量.

定义

数学上，我们定义两个字符串A和B间的 Levenshtein距离 为levA, B(a, b)，其中a、b分别为字符串A、B的长度， Levenshtein

Levenshtein

这个Levenshtein是Levenshtein相等时为 0,否则为1的示性行数,还有就是Levenshtein是a的前i个字符和b的前j个字符之间的距离。

注意在min大括号内的三种情况: 第一部分对应删除操作(从a到))、第二部分对应插入操作、第三部分对应替换操作,这取决于 a,b 对应的各个字符 是否相同.

例

例如,kitten和sitting的Levenshtein距离是3,因为以下三个编辑将 一个更改为另一个,并且没有办法 以少于三个编辑执行此操作:

  1. kitten → sitten (用"s"代替"k")
  2. sitten → sittin (用"i"代替"e")
  3. sittin → sitting (在末尾插入"g") .

应用

在字符串近似匹配中，目标是从很多长的的文本中发现短文本的匹配，在这种情况下，较少差别的匹配是期望得到的。例如，短文本可以来自字典，这里，通常其中一个字符串是短的，另一个字符串是任意长的。莱文斯坦距离有着广泛的应用，例如，拼写检查、光学字符的校正系统、基于翻译内存库的自然语言翻译的辅助软件。

动态规划方法解释

我们来看一个简单的例子,找出字符串ME和MY之间的最小编辑距离. 直观地说,你已经知道这里的最小编辑距离是只有1个步骤. 它就是用E取代Y. 但是,让我们尝试以算法的形式将其形式化,以便能够执行更复杂的示例,如转换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)。 我们所要做的就是找到 那三个中最小的单元格然后添加1, 如果i行和j列中的字母不同的话。

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

Levenshtein Matrix

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

Minimum Edit Distance Decision Graph

您可能会在图片上看到许多重叠的子问题 用红色。 此外，没有办法减少操作数量并使其成功,也就是 少于那三个相邻细胞的最小值。

您还可能会注意到计算矩阵中的每个单元格数字 是基于前一个。 因此制表技术（填写缓存） 自下而上的方向）正在这里应用。

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

Levenshtein distance

参考