我正在尝试使用 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 distance measure 的理解是正确的,我相信结果应该是
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
我错了,还是函数中有什么不好的地方?
最佳答案
如果您查看 Jellyfish source code jaro.c
,您会看到换位次数存储在变量 trans_count
中,该变量的类型为 long
。这意味着当它除以二时:
trans_count /= 2;
这使用 C 的整数除法,它会截断结果。因此,在您的示例 (POVERTY/POERVTY) 中,换位次数为 3,但除以 2 时变为 1。
这是正确的吗?好吧,我尝试了以下研究途径:
The number of mismatched characters is divided by two to yield the number of transpositions.
没有指示除法之后是否要截断。尽管 Winkler 给出了许多示例,但我发现使用他在论文中描述的算法无法重现这些值。例如,他给出了 MARTHA-MARHTA 的 J-W 分数为 0.9667(见表 1),我不知道如何解释文本以使其正确。所以这篇论文是没有帮助的。也许值得写信给温克勒解释一下?
N_trans
中的换位,其类型为 long
,因此截断了除法,与 Jellyfish 一致。(由于额外的“长字符串调整”,此代码将 MARTHA-MARHTA 分数设为 0.9708。)
所以在我看来,水母的行为至少在历史资料的基础上是合理的。但这似乎是一个错误,因为它无缘无故地丢失了有关换位次数的信息。
关于string - 海蜇中Jaro距离的特殊行为,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20278373/