我正在尝试使用Jellyfish处理模糊字符串。我注意到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分。
在第一个例子中:
1. ZX → XZ (转置相邻字符) 2. XZ → XYZ (插入 Y)
在第二个例子中:
1. BACD → ABDC (相邻的 BA 字符进行转置) 2. 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
)