匹配算法JaroWinkler

1、常用數(shù)據(jù)匹配算法簡介系-Jaro-Winklerdistance算法數(shù)據(jù)是組織最具價值a勺資產(chǎn)之一。企業(yè)的數(shù)據(jù)質(zhì)量與業(yè)務績效之間存在著直接聯(lián)系，高質(zhì)量a勺數(shù)據(jù)可以使公司保持競爭力并在經(jīng)濟動蕩時期立于不敗之地。本文介紹在數(shù)據(jù)匹配算法Jaro-Winklerdistancewanghetommy2011-6-8Aboutthisdocument4Jaro-WinklerDistance41) Introduction42) Definition4a) TheJarodistance算法最后得分公式:4b) MatchWindow(睡己窗口)計算俎4c)解心面兩組俎5d)Jaro-Winklerdi

2、stance算法53)引用資源8教程版本說明作者0.9總結常用ETL數(shù)據(jù)匹配算法理論wangheAboutthisdocument數(shù)據(jù)是組織最具價值的資產(chǎn)之一。企業(yè)的數(shù)據(jù)質(zhì)量與業(yè)務績效之間存在看直接聯(lián)系,高質(zhì)量的數(shù)據(jù)可以使公司保持競爭力并金豆?jié)鷦邮帟r期立于不敗之地。有了普遍深入的數(shù)據(jù)質(zhì)量，企業(yè)在任何時候都可以信任滿足所有需求的所有數(shù)據(jù)。然而大多數(shù)情況下、我們的數(shù)據(jù)源來自企業(yè)中各個系統(tǒng)、并不是所有的數(shù)據(jù)都有統(tǒng)一的標準、這樣在我們做ETL過程的時候就需要X帝們需要的數(shù)據(jù)清洗出來、而清洗的過程中主要是對數(shù)據(jù)進行操作、因此采用一個高效的合理的算法必不可少。此文檔簡單對數(shù)據(jù)匹配的幾種經(jīng)典進行闡述與分析。

3、以供參考，此文檔介紹Jaro-Winklerdistance。Jaro-WinklerDistance1) IntroductionTheJaro-Winklerdistance(Winkler,1990)是計算2個字符串之間相彳唾的一種算法。它是Jarodistance算法的變種。主要用于recordlinkage/數(shù)據(jù)連接(duplicatedetection/重復記錄)方面的領域，JarsWinklerdistance最后得分越高說明相越大。JarsWinklerdistance是適合于串比如名字這樣加的字符之間計算相0分表示沒有任何相彳以度，1分則像完全匹配。2) Definition

4、a) TheJarodistance算法最后得分公式:A_1/ininui-l4=共商+商+；公式一其中: si、s2是要比對的兩個字符 4是最后得分 m是匹配的字符數(shù) t是換位的數(shù)目b) MatchWindow(匹配窗口)計算公式MW=_1,公佇其中： si、s2是要比對的兩個字符 MW是匹配窗口值C)解程上面兩組公式1 .字符串si與字符串S2在做匹配計算時，當兩個字符的距離不大于公式二的最后結果(匹配窗口)即認為是匹配的。2 .當si、s2中字符相匹配但是字符位置不一樣時發(fā)生換位操作、而公式一中換位的數(shù)目t為不同I廁？的匹配字符的數(shù)目的一半。比如:兩個字符串CRATEfTRACE做匹酉醵

5、作，字符串中僅有R'AE三個字符是匹配的,即m=3。為什么'C,T不算做是匹配的呢。因為雖然。T都出現(xiàn)在兩個字符串中，但是通過公式二得出匹配窗口值為(5/2)-l=1.5o而兩個字符串中，C','T字符的距離均大于1.5。所以不算做匹配。因此匕0。在另一組字符串DwAyNE與DuANE。匹國的字符D-A-N-E在兩個字符串中有相同的字符JII頁序，所以不需要進行換位操作，因此t=0,m=4。d)Jaro-Winklerdistance算法公式Jaro-Winkler算法給予了起始部分就相同的字符串更高的分數(shù)，它定義了一個前綴范圍p,對于要匹配的兩個字符串,如果前

6、綴部分有長度為L的部分字符串相同,則Jaro-WinklerDistance為:dw=dj+L*P(1-dj)；公式三其中： 斗是Jar。distance最后得分 L是前綴部分匹配的長度 P是一個范圍因子常量，用來調(diào)整前綴匹配的權值，但是P的值不能超過025,因為這樣最后得分可能超過1分.Winkler的標準默認設置值P=0.1oAlthoughoftenreferredtoasadistancemetric,theJaro-Winklerdistanceisactuallynotametricinthemathematicalsenseofthatterm.3)Example(a)例子1給出

7、兩個字符串siMARTHA和s2MARHTA我們可以得出： 777=6 |51I=6 I<2I=6 兩組字符T/H和H/T要進行換位操作，因此t=2/2=l;我們可以根據(jù)公式一得出Jaro得分:1/666-14=向+向+=0.944如果使用Jar所Winkler,并且取范圍因子P=0L我們會得出:P=0.1L=3dw=0.944+(3*0.1(1-0.944)=0.961假使串si勿VF并且比。必/VF我們發(fā)現(xiàn): 777=4 |Si|=6 |災|二5 t=0我們發(fā)現(xiàn)一個Jar。比分：使用標準祛碼發(fā)現(xiàn)Jaro-Winkler比分d=0.1我們繼續(xù)發(fā)現(xiàn)：因而：dw=0.822+(1*0.1(

8、1-0.822)=0.84(b)例子2給出兩個字符串siDWAYNEands2DUANE.我們可以得出： m=4 1$11=6 121=5 t=0我們可以根據(jù)公式一得出Jar。得分：如果使用Jaro-Winkler,并且取范圍因子P=01,我們會得出:P=0.1L=1dw=0.822+(1*0.1(1-0.822)=0.84(C)例子3在這個例子中我們利用圖形來說明匹配過程，給出兩個字符串siDIXONands2DICKSONX得出下面圖表：根據(jù)圖標我們得出：=4雖然兩個字符串都含有字符X但是距離已經(jīng)超過匹配窗口值,所以忽略 /$1/=5 Is2l=8我們可以根據(jù)公式一得出Jar。得分：1/44