编辑距离

1.Levenshtein distance(以下简称L氏距离)。 此距离由Levenshtein 于1965年定义，在这个定义体系中有三种原子操作：insertion,deletion,substitution（出处见论文《BINARY CODES CAPABLE OF CORRECTING,DELETIONS,INSERTIONS AND REVERSALS》）；

2.Damerau,F,J distance（以下简称D氏距离）。此距离有Damerau于1964年定义，在这个定义体系中有四种原子操作:insertion,deletion,substitution,以及transpositionof ajacent symbols（出处见论文《A Technique for Computer Detection and Correction of Spelling Errors》）；

两种定义的区别：

1.L氏距离的原子操作集中不包括相邻交换这个操作；

2.根据wiki上介绍：L氏距离可以处理多重编辑错误，而D式距离只能处理单一的编辑错误。

 

综上：

如果利用L氏编辑距离计算abc与ca之间的编辑距离，结果应该是3（删除b->原字符串开头的a被替换为c->原字符串结尾的c被替换为a），这个是没有任何异议的；如果根据D氏距离计算abc与ca之间的编辑距离应该为2（删除b->原字符串首尾的字符a与c交换位置），现在问题就出来了：很多书籍和论文（例如 Kemal Oflazor 的《Error-tolerant Finite-state Recognition with Application to Morphological Analysis and Spelling Correction》,M.W.Du and S.C.Chang的《A model and a fast algorithm for multiple errors spelliing correction》）中采用了D氏编辑距离的定义，然后又紧接着给出了如下的计算公式：

 

公式1：以上两篇论文中提供的编辑距离计算公式。

 

根据此计算公式得到的计算结果也是3。

这个时候很多会说，因为得出2的结果的时候，先删除中间的b，没有满足“顺序操作”所以得到错误的结果。对于字符串abc的正确处理顺序应该是先处理a,然后处理b,然后处理c。正确的计算应该是：删除a->b换成c->c换成a。但是编辑距离应该是满足对称性的。也就是说abc与ca的编辑距离等于ca与abc的编辑距离。ca变成abc可以经过如下步骤:ca->ac,ac中间插入b。因此这种说法是不太合理的，况且编辑距离的定义只是对现实情况的一种数学抽象，不考虑程序设计问题，和“顺序流”之间没有多大关系。

 

这个问题困扰了我很长时间，今天通过查wiki才知道了事情的来龙去脉：大体情况是这样的，L和D自己对编辑距离的定义是没有问题的，符合泛函理论中对距离定义的三个要素条件。后来一些人就想将L和D的距离定义融合在一起，成为了Damerau–Levenshtein distance（以下简称D-L距离），认为这样就既可以克服了D定义只能识别单一编辑操作引起的错误的局限，又弥补了L定义不包含相邻字符互换操作的遗憾。其实上面的公式1计算的就是D-L距离。但是这个D-L距离并不满足泛函理论中所要求的距离定义的三要素标准，它不满足三角不等式，所以这个定义是有问题的，数学上具有不严谨性。于是也就有了将abc与ca的编辑距离错算为3的情况。但是由于这个错误并不影响工程中的应用，并且这个公式能够给实际工作带来便利，就一直沿用了下来。