从编辑距离聊开去

有这样一个问题：我们有两个字符串，前一个是 bears ，后一个是  barss ，问，在只允许 插入 字符、 删除 字符、 改变 字符三种操作方式的前提下，从后一个(字符)串变成前一个串， 最少 需要几步？

• 两者第一个字符都是 b ，后者不需要修改

• 前一个串的第二个字符是 e ，第三个字符是  a ，而后一个串的第二个字符是  a ，只需要在后一个串的第二个位置 插入 e ，后一个串和前一个串的前两位就都一样了

• 两个串接下来的部分， ars 是一致的，不需要修改

• 后一个串最后还多一个 s ，进行 删除 操作

这样，两个字符串就一样了，在这个问题中，我们一共进行了两步操作，一步是 插入 ，一步是 删除 。这里的两步，2，称为编辑距离（Edit Distance），它最先是由前苏联科学家 Vladimir Levenshtein 在1965年发明，又称 莱温斯坦距离（Levenshtein distance）。它称为编辑距离其实有点不太严谨 --- 凭什么这里只能包括  插入 、 删除 和  改变 这三种操作呢？事实上，的确还有其他类型的 编辑 操作，比如有的 编辑 就只限定在 插入 和 删除 两项、有的 编辑 只能用 改变 这一项操作、有的 编辑 只能用 交换 操作等等。但在一般情况下，我们在说编辑距离时，指的是莱温斯坦距离，但在特定的上下文中，它也有可能指其他距离。

等等，我们之前不是在说一个字符串变换成另外一个字符串最少需要的操作吗？为什么这里变成了距离？事实上，我们在这里用操作步骤定义了编辑距离，这也是两个串相似程度的一种度量。两个字符串当然还有其他距离度量，不叫 编辑 距离而已，我们可以另外定义两个字符串的相似程度，比如两个字符串的长度差值，也可以称之为一种距离，只不过和上述说的编辑距离度量单位、度量精度、用途不一样而已。

上面这个看似有点奇怪的问题以及编辑距离定义有不少的应用场景，比如：

• 拼写建议。我们如果写了一个错误的词，那么编辑器有可能会在我们错误的词下面划出波浪线，提示我们这个词有可能写错了，当我们点击错误提示时，弹出的几个备选词，就是编辑距离相对较近的词。

• 地址建议。当我们在购物APP中填写地址后，有的APP会提示生成一个更加详细或更加明确的地址，这种情形也可以采用编辑距离进行地址建议。

• 抄袭检测。

• 语音识别。将人类的语音中的词汇内容转换字符序列，然后用字符序列和语料库进行对比，用最小编辑距离来匹配识别。当然，现在深度学习一般会进行端到端的语音识别，就不需要这个了。

• DNA分析。提取蛋白基因中的不变量，然后进行相似度计算，判定物种中情缘关系的远近。

• 语言学家研究语言距离。不同的语言之间有一些融合变化有时比较难以考察，我们就可以使用这个距离去研究英语中有些词汇和拉丁语中的词汇的关系(比如词根词缀等等)。

说完场景我们简单说一下这个距离是怎么计算的，上述过程描述的看上去比较复杂，但用数学归纳法来描述就比较简单了。我们先考虑一个比较简单的问题，字符串 ab 变成 字符串 xy 需要多少个编辑步骤?

1。比如我们可能很容易得到 由字符 `a` 变成字符 `x` 的编辑步骤(要么两者一样，不用操作，要么两者不一样，替换 `a` 为 `x` 即可);

2。在第 1 步的基础上，我们如果想要得到 字符串 `a` 变成 字符串 `xy` 的编辑步骤也是容易计算的。分别分成，当 `y` 等于或不等于 `a` 两种情况计算;

2.5。由 x 变成  a 的步骤和由  a 变成  x 的步骤一样;

3。由 `x` 变成 `ab` 和步骤2类似;

4。那么由字符串 `ab` 变成 `xy` 的问题就变得很简单了，只需要取上述步骤中的最小值，`+1` 就可以了。

计算示意图

事实上，这就是莱温斯坦距离（Levenshtein distance）定义的大致解释了(缺少一点点细节)。对于两个字符串，只需要按照上述步骤，填好对应表格(矩阵)就可以得到最后结果了。

对于两个字符串，要生成上面这样一个矩阵，空间复杂度为 O(M*N) (M和N分别是两个字符串的长度)。这个在两个字符串都比较短小的情况下，能获得不错的性能，当字符串比较长的时候，这种方法需要较大的空间存放矩阵，需要评估场景是否适合(或使用一些计算莱温斯坦距离的变体进行优化)。在一般情况下，编辑距离适用在字符较短的情况。

在 KNIME 中，有一些相关节点的配置选项中会出现 莱温斯坦距离（Levenshtein distance）。

比如 KNIME Textprocessing 扩展中的  String Matcher 节点，能够将匹配表中的数据和字典表中的数据通过 莱温斯坦距离（Levenshtein distance）给匹配出来。配置中可以选择去匹配字典中 前N个相近的数据。也可以给予删除、插入、更改、交换(aabca => aacba)四种编辑操作不同的权重。莱温斯坦距离（Levenshtein distance）认为每一个操作步骤的权重都是1，我们可以假设插入这种操作在我们的具体问题中出现的可能性很低，那么可以设置一个很大的权重，这样，如果有插入操作，最后的距离就会是一个比较大的数，进而就会判定这两个字符串相似程度是较低的。一个简单的例子，有三个字符串， aaa，aab，aaaa ，在如前所述设置之后，我们会认为相比于  aaa 与  aaaa ， aaa 与  aab 更相似，如果认为几个操作是等权重的，那么，  aaa 与  aaaa ， aaa 与  aab ，这两组的相似程度是一致的。

还有在 KNIME Distance Matrix Extension 扩展中的  Similarity Search ，可以在众多的相似性指标中选择莱温斯坦距离（Levenshtein distance）进行字符串的比较，不仅可以比较出最相似的，甚至还可以配置比较出最不相似的，功能比上面介绍的节点更为强大。

Palladian 扩展中也有类似的节点，不再赘述，有兴趣可以自行查看。

作业比较简单，可以根据下图自行寻找、配置节点进行练习。也可以进入最下面购买链接付费下载导入进行练习。

字典表 中有几个拼写正确的单词，而  乱七八糟的数据表 中是一些拼写错误的单词，我们的目的是要根据编辑距离，把  乱七八糟的数据表 中的单词对应到它最有可能的正确拼写的单词上

。

整体 workflow

其中，各个节点的数据如图所示：

字典表

数据表

string matcher 节点结果

similarity search节点结果

string distances 节点结果

面包多付费下载，编辑距离 workflow 练习（五毛 XD）