水母的Damerau-Levenshtein距离计算车？

Question

我正在尝试使用Jellyfish来处理模糊字符串。我注意到Damerau–Levenshtein distance算法的一些奇怪行为。例如：

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 

这是特别奇怪，因为编辑的数量不应仅仅是两个在这两个例子，但它们是完全相同的编辑次数：

在第三示例：

1. jellyifhs→jellyfihs（转置相邻的字符if）
2. jellyfihs→jellyfish（转置相邻的字符hs）

在第四示例：

1. ifhs→fihs（转置相邻字符if ）
2. fihs→fish（转置相邻的字符hs）

Answer 1

从

wikipedia

在信息理论和计算机科学，Damerau-Levenshtein距离（弗雷德里克·J·达梅劳和Vladimir I.得名Levenshtein）[引用需要]是两个字符串之间的“距离”（字符串度量），即有限的符号序列，通过计算将一个字符串转换为另一个字符串所需的最小操作次数给出，其中操作被定义为插入，删除或替换单个字符，或转换两个相邻字符。

但是，如果你继续读下去，

就拿CA和ABC之间的编辑距离。因为CA→AC→ABC，所以Damerau-Levenshtein距离LD（CA，ABC）= 2，但是因为如果使用操作CA→AC，所以不是最佳的字符串对准距离OSA（CA，ABC）= 3可能使用AC - > ABC，因为这会要求子字符串被多次编辑，这在OSA中是不允许的，因此最短的操作顺序是CA-> A-> AB-> ABC。请注意，对于最佳字符串对齐距离，三角形不等式不成立：OSA（CA，AC）+ OSA（AC，ABC）< OSA（CA，ABC），因此它不是一个真正的度量标准。

编辑：

在source服用后一看，很明显，该函数计算OSA，而不是Damerau–Levenshtein distance。