[Notes] Jaro Distance / Jaro-Winkler Distance

(image source: https://unsplash.com/photos/oHoBIbDj7lo)

在 Document level 中，我們常用 Cosine Similarity 或是 Euclidean Distance 來衡量兩個 doc 的相似度。但如果我現在想要在 Word level 上，比較兩個詞的相似度，該怎麼做呢？以下介紹 Jora Based Similarity，算法有兩種/兩階段：(1) Jaro Distance (2) Jaro-Winkler Distance。

Jaro Distance / Similarity

在上方的算式中：
(1) m = 兩個字串相匹配的字元個數（受到max_window限制）
(2)|s1|與|s2|表示兩個字串的長度
(3) t = 0.5 * Transposition

其中，max_window 的設定如下：

Transposition 代表的意思是，在匹配的字元中，有幾個是位置/Index不同的。

E.g. s1 = “abcdefgh”，s2 = “abehc”，計算兩者的 Jora Similarity Score。

[Step1] 首先我們先定義出 max_window 為多少，方便計算 m。max_window = 1/2(max(8,5))-1 = 3。

[Step2] 計算 m。兩個字串中，abehc 都相匹配，但是 h 在 s1 index = 7在 s2 index = 3，兩者的差超過 max_window 可以忍受的範圍，所以 m = 4 而不是 5。

[Step3] 計算 Transposition。在上一步被納入 m 的計算的三個字母中，只有 ce 的位置是相反的，所以 Transposition = 2。

[Step4] 計算 t。t = 0.5 * Transposition = 1。

Get Haren Lin’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

[Step5] 計算 Similarity Score = (1/3)*[(4/8)+(4/5)+((4–1)/4)] = 0.683。

Jaro-Winkler Distance / Similarity

Jaro-Winkler similarity 是建立於 Jaro similarity 之基礎上做進ㄧ步的調整。

上式中：
(1) simj = Jora Similarity Score。
(2) l = length of the matching prefix up to a maximum of 4 characters。
(3) p = scaling factor，代表 matching prefix 對相似度的貢獻。(0.1 by default, maximum value = 0.25)

E.g. s1 = “abcdefgh”，s2 = “abehc”，計算兩者的 Jora-Winkler Similarity Score。

[Step1] 算出 simj = 0.683。

[Step2] 計算 l。因為前四個 prefix 中，只有 ab 匹配故 l = 2。

[Step3] 計算 simw = 0.683 + 2*0.1*(1–0.683)= 0.7464。

Python Related Toolkit

nap/jaro-winkler-distance

Reference

Jaro-Winkler distance - Wikipedia

This article will be updated at any time! Thanks for your reading. If you like the content, please click the “clap” button. You can also press the follow button to track new articles at any time. Feel free to contact me via LinkedIn or email.