Jaro的特殊行爲距離在JellyFish

Question

我想用水母來處理模糊的字符串。我注意到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 

現在，如果我的賈羅距離測量的理解是正確的，我相信結果應該是0.9285714285

我已經確定爲什麼calcualtion是怎麼了。爲了計算量度相信followig是正確的：

(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'。

然而，水母似乎只能識別兩個換位，因爲它是計算：

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

我錯了這一點，或者是有什麼不好的作用？

Answer 1

如果您查看Jellyfish source code jaro.c，您會看到轉座的數量存儲在變量trans_count中，該變量的類型爲long。這意味着，當這是由兩個分開的：

trans_count /= 2; 

此採用C的整數除法，其截斷的結果。所以在你的例子（POVERTY/POERVTY）中，換位次數是3，但是除以2後，這個數字變爲1.

是這樣嗎？好吧，我想研究以下途徑：

1. 的Wikipedia article是沒有幫助的，因爲所有的例子都有偶數換位。 （它給出了MARTHA-MARHTA的Jaro評分爲0.944，Jaro-Winkler評分爲0.961。）

2. Jaro的1989年論文未公開訪問。

3. Winkler's 1990 paper含糊不清。他所說的全部是：

   不匹配字符的數量除以2得到換位次數。

   沒有指示該分部是否被截斷。儘管溫克勒給出了許多例子，但我發現使用他在論文中描述的算法重現這些值是不可能的。例如，他將MARTHA-MARHTA的J-W分數設置爲0.9667（見表1），我不知道如何解釋文本才能做到這一點。所以這篇文章是無益的。也許值得寫給溫克勒解釋一下？

4. 如果你看一下，爲「official string comparator to be used for matching during the 1995 Test Census」（這是基於「與莫琳·林奇修改比爾克勒，喬治·麥克勞克林和馬特·哈羅」寫碼）的代碼，那麼你會看到，它在計算換位變量N_trans，其型號爲long，因此截斷了該部門，同意水母。

   （此代碼給瑪莎MARHTA得分爲0.9708，由於額外的「長串的調整」。）

所以看起來我好像水母的行爲至少是合理的歷史淵源的基礎。但它確實看起來像一個錯誤，因爲它沒有原則性原因就會丟失有關換位次數的信息。