水母的Damerau-Levenshtein距离计算有问题吗？

Question

我正在尝试使用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

这很奇怪，因为两个示例中的编辑次数不仅应该都是两次，而且它们的编辑内容完全相同：

在第三个示例中：

1. jellyifhs → jellyfihs（交换相邻字符if）
2. jellyfihs → jellyfish（交换相邻字符hs）

在第四个示例中：

1. ifhs → fihs（交换相邻字符if）
2. fihs → fish（交换相邻字符hs）

- Woody Pride

---

我认为转置算作两个步骤。 - aIKid

@aIKid：相邻两个字符的转置是一次操作/步骤。 - 0xc0de

+1，看起来他们实现了OSA而不是Damerau-Levenshtein距离。 - 0xc0de

这正是我所想的...实际上，我也发现了jaro_distance的错误。我在github上，但从未使用过它，直接给他们发送电子邮件是否更好，还是在github上做些什么？我想我会在这里更新我的问题，以提出那个问题。 - Woody Pride

Answer 1

来自wikipedia。

在信息论和计算机科学中，Damerau-Levenshtein距离（以Frederick J. Damerau和Vladimir I. Levenshtein的名字命名）[需要引证]是两个字符串之间的“距离”（字符串度量），即通过计算将一个字符串转换为另一个字符串所需的最小操作次数，其中一次操作被定义为插入、删除或替换单个字符，或交换两个相邻字符。

但如果您继续阅读，

以 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)，因此它不是真正的度量标准。 编辑后：查看 source 后，很明显该函数计算的是 OSA 而不是 Damerau-Levenshtein 距离。

- 0xc0de

---

这似乎非常明确地说明了“Damerau-Levenshtein距离LD（CA，ABC）= 2”，这就是为什么当在jellyfish中实现相同的问题时返回3而感到惊讶的原因。 - Woody Pride

是的，我的错，看起来实现计算OSA。已经在GitHub上提交了一个问题 https://github.com/sunlightlabs/jellyfish/issues/13。 - 0xc0de

那正是我所想的... 实际上，我也在发现jaro_distance存在错误。我有Github账号，但从未使用过，直接给他们发送邮件是否更好，还是在Github上进行某些操作？ - Woody Pride

在 Github 上提出问题总是更好的选择，这样其他人（比如其他用户）也会了解到这个问题，而且一些人（可能不是存储库所有者）可以提交修复该问题的代码。 - 0xc0de

很酷，我想我会在这里提出另一个问题。问题是我不确定是我弄错了，还是代码有问题。我对这些措施不是很熟悉... - Woody Pride