水母的Damerau-Levenshtein距离计算是小车吗？
我试图使用水母来处理模糊字符串。我注意到Damerau-Levenshtein距离算法的一些奇怪行为。例如：
import jellyfish as jf
In [0]: jf.damerau_levenshtein_distance('ZX', 'XYZ')
Out[0]: 3
In [1]: jf.damerau_levenshtein_distance('BADC', 'ABCD')
Out[1]: 3在我看来，两人都应该得分2分。
在第一个示例中
ZX→XZ(转置相邻字符)XZ→XYZ(插入Y)
在第二个示例中
BACD→ABDC(转置相邻BA字符)ABDC→ABCD(转置相邻DC字符)
这是算法出了什么问题，还是我误解了度量？如有任何指导，将不胜感激。
编辑
为了使事情更加奇特，我还观察到以下几点：
In [3]: jf.damerau_levenshtein_distance('jellyifhs', 'jellyfish')
Out[3]: 2
In [4]: jf.damerau_levenshtein_distance('ifhs', 'fish')
Out[4]L 3这特别奇怪，因为编辑的数量不仅应该是两个示例中的两个，而且它们是完全相同的编辑：
在第三个示例中
jellyifhs→jellyfihs(转置相邻字符if)jellyfihs→jellyfish(转置相邻字符hs)
在第四个示例中
ifhs→fihs(转置相邻字符if)fihs→fish(转置相邻字符hs)
回答 1
Stack Overflow用户
发布于 2013-11-28 06:22:05
来自维基百科
在信息论和计算机科学中，所需的Damerau -Levenshtein距离(以弗雷德里克·J·达梅罗和弗拉基米尔·L·莱文的名字命名)是两个字符串之间的“距离”(字符串度量)，即符号的有限序列，通过计算将一个字符串转换成另一个字符串所需的最小运算数，其中一个操作被定义为单个字符的插入、删除或替换，或两个相邻字符的换位。
但如果你再读下去，
例如，CA和ABC之间的编辑距离。Damerau-Levenshtein距离LD( CA，ABC )=2，因为CA -> AC -> ABC，但是最优的字符串对齐距离OSA( CA，ABC) =3，因为如果使用CA -> AC操作，就不可能使用AC -> ABC，因为这需要对子字符串进行多次编辑，这在OSA中是不允许的，因此操作的最短序列是CA -> A -> AB -> ABC。注意，对于最优的字符串对齐距离，三角不等式不成立: OSA(CA，AC) + OSA(AC，ABC) < OSA(CA，ABC)，因此它不是真正的度量。
编辑：
在查看了来源之后，很明显，该函数计算的是OSA而不是Damerau–Levenshtein distance。
https://stackoverflow.com/questions/20258800
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号