4

我正在尝试使用 Jellyfish 来处理模糊字符串。我注意到 jaro_distance 算法的一些奇怪行为。

我之前在使用 damerau_levenshtein_distance 算法时遇到了一些问题,这似乎是代码中的一个错误,然后堆栈用户在 github 上将其作为问题提出。

我不确定我是否在考虑测量错误,或者它是否是一个真正的错误。我查看了源代码(http://goo.gl/YVMl8k),但我不熟悉 C,所以我很难知道这是一个实现问题,还是我错了。

请注意以下事项:

In [1]: S1 = Poverty
In [2]: S2 = Poervty
In [3]: jf.jaro_distance(S3, S4)
Out[3]: 0.95238095

现在,如果我对 jarrow 距离测量的理解是正确的,我相信结果应该是0.9285714285

我已经确定了计算出错的原因。要计算度量,我认为以下是正确的:

(7.0/7.0 + 7.0/7.0 + ((7.0 - (3.0/2.0))/7.0) * (1.0/3.0) = 0.9285714285

该表达式中的关键数字是 3.0。这个数字必须代表“匹配的数量(但顺序不同)”(维基百科)。在我看来,在 S1 和 S2 中,匹配但序列顺序不同的字符是“e”、“r”、“v”。

然而,JellyFish 在计算时似乎只识别出两个转置:

(7.0/7.0 + 7.0/7.0 + ((7.0 - (2.0/2.0))/7.0) * (1.0/3.0) = 0.95238095

我错了,还是功能有问题?

4

1 回答 1

3

如果您查看Jellyfish 源代码jaro.c,您会看到转置的数量存储在trans_count具有类型的变量中long。这意味着当它被二除时:

trans_count /= 2;

这使用了 C 的整数除法,它会截断结果。因此,在您的示例(POVERTY/POERVTY)中,换位次数为 3,但除以 2 时变为 1。

这是正确的吗?好吧,我尝试了以下研究途径:

  1. 维基百科的文章没有帮助,因为所有的例子都有偶数的换位。(它给出了 MARTHA-MARHTA 的 Jaro 得分为 0.944,而 Jaro-Winkler 得分为 0.961。)

  2. Jaro 1989 年的论文不是开放获取的。

  3. 温克勒 1990 年的论文模棱两可。他只说:

    不匹配字符的数量除以 2 得到转置的数量。

    没有说明是否要在除法之后进行截断。尽管 Winkler 给出了许多示例,但我发现使用他在论文中描述的算法无法重现这些值。例如,他给 MARTHA-MARHTA 的 J-W 分数为 0.9667(见表 1),我不知道如何解释文本以使其正确。所以这篇论文是没有用的。也许值得写信给温克勒解释一下?

  4. 如果您查看“在 1995 年测试普查期间用于匹配的官方字符串比较器”的代码(该代码基于“Bill Winkler、George McLaughlin 和 Matt Jaro 编写的代码,并由 Maureen Lynch 修改”),那么您会看到它计算变量 中的转置,该变量N_trans具有 type long,因此截断了除法,与 Jellyfish 一致。

    (由于额外的“长字符串调整”,此代码给出的 MARTHA–MARHTA 分数为 0.9708。)

所以在我看来,水母的行为至少在历史资料的基础上是合理的。但这似乎确实是一个错误,因为它无缘无故地丢失了有关换位次数的信息。

于 2013-12-12T17:35:57.313 回答