admin 管理员组文章数量: 1087139
2024年4月14日发(作者：android系统镜像)
一直让我困惑的问题是：abc与ca之间的编辑距离究竟等于几？
问了很多同学和网友：大家的普遍观点是：如果在编辑距离定义中指明相邻交换操作
为原子操作，那么应该等于2；反之，如果在编辑距离定义中为定义相邻交换操作为原子
操作那么应该等于3。
为了更好地阐明这个问题，先给出编辑距离的两种定义形式
htein distance(以下简称L氏距离)。 此距离由Levenshtein 于1965年定
义，在这个定义体系中有三种原子操作：insertion,deletion,substitution（出处见论文
《BINARY CODES CAPABLE OF CORRECTING,DELETIONS,INSERTIONS AND
REVERSALS》）；
u,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》, and 的《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。因此这种说法是不太合理的，况且编辑距离的定义
只是对现实情况的一种数学抽象，不考虑程序设计问题，和“顺序流”之间没有多大关系。
版权声明：本文标题：有关编辑距离计算的一点整理 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/p/1713101838a619940.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论