算法簡介
The Jaro–Winkler distance (Winkler, 1990)是計(jì)算2個(gè)字符串之間相似度的一種算法。它是Jaro distance算法的變種。主要用于record linkage/數(shù)據(jù)連接（duplicate detection/重復(fù)記錄）方面的領(lǐng)域，Jaro–Winkler distance最后得分越高說明相似度越大。Jaro–Winkler distance 是適合于串比如名字這樣較短的字符之間計(jì)算相似度。0分表示沒有任何相似度，1分則代表完全匹配。
算法定義
- The Jaro distance算法最后得分公式：
d_j = \frac{1}{3}\left(\frac{m}{|s1|} + \frac{m}{|s2|} + \frac{m-t}{m} \right)
其中:
- s1、s2 是要比對(duì)的兩個(gè)字符
- d_j是最后得分
- m是匹配的字符數(shù)
- t 是換位的數(shù)目
- Match Window(匹配窗口)計(jì)算公式
MW=\left(\frac{MAX(|s1|,|s2|)}{2}\right) - 1
其中：
- s1、s2 是要比對(duì)的兩個(gè)字符
- MW是匹配窗口值
- 上述公式解釋
- 字符串s1與字符串s2在做匹配計(jì)算時(shí)，當(dāng)兩個(gè)字符的距離不大于公式二的最后結(jié)果(匹配窗口)即認(rèn)為是匹配的。
- 當(dāng)s1、s2中字符相匹配但是字符位置不一樣時(shí)發(fā)生換位操作、而公式一中換位的數(shù)目t為不同順序的匹配字符的數(shù)目的一半。比如:兩個(gè)字符串CRATE和TRACE做匹配操作，字符串中僅有'R' 'A' 'E'三個(gè)字符是匹配的，即m=3。為什么'C', 'T'不算做是匹配的呢。因?yàn)殡m然'C', 'T'都出現(xiàn)在兩個(gè)字符串中，但是通過公式二得出匹配窗口值為 (5/2)-1=1.5。而兩個(gè)字符串中'C', 'T'字符的距離均大于1.5。所以不算做匹配。因此t=0。在另一組字符串DwAyNE 與 DuANE 。匹配的字符D-A-N-E 在兩個(gè)字符串中有相同的字符順序，所以不需要進(jìn)行換位操作，因此t=0,m=4。
- Jaro–Winkler distance算法公式
Jaro-Winkler算法給予了起始部分就相同的字符串更高的分?jǐn)?shù)，它定義了一個(gè)前綴范圍p，對(duì)于要匹配的兩個(gè)字符串，如果前綴部分有長度為L的部分字符串相同，則Jaro-Winkler Distance為:
d_w = d_j + L * P(1 - d_J)
其中:
- d_j是Jaro distance最后得分
- L是前綴部分匹配的長度
- P是一個(gè)范圍因子常量，用來調(diào)整前綴匹配的權(quán)值，但是P的值不能超過0.25，因?yàn)檫@樣最后得分可能超過1分.Winkler的標(biāo)準(zhǔn)默認(rèn)設(shè)置值P=0.1。
例子
給出兩個(gè)字符串 s1 MARTHA 和 s2 MARHTA、我們可以得出：
- m = 6
- |s1| = 6
- |s2| = 6
- 兩組字符T/H和H/T要進(jìn)行換位操作，因此t=2/2=1;
我們可以根據(jù)公式一得出Jaro得分：
d_j = \frac{1}{3}\left(\frac{6}{|6|} + \frac{6}{|6|} + \frac{6-1}{6}\right)
如果使用Jaro–Winkler，并且取范圍因子P=0.1,我們會(huì)得出:
P=0.1
L=3
d_w = 0.944 + (3 * 0.1(1 - 0.944))=0.961
python 運(yùn)行
- 安裝lib
pip install jaro_winkler
- 程序運(yùn)行
print(jaro.jaro_metric("MARTHA".decode("utf-8"),"MARHTA".decode("utf-8")))
優(yōu)化
- 多進(jìn)程
- pandas
