4

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

1 回答 1

3

来自维基百科

在信息论和计算机科学中，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)，因此它不是真正的度量。

编辑：

看了源码后，很明显是函数计算OSA而不是Damerau–Levenshtein distance.

于 2013-11-28T06:22:05.070 回答