前言
在前面的文章中，筆者有對(duì)編輯距離以及Levenshtein距離進(jìn)行詳細(xì)的說明，其實(shí)levenshtein距離是編輯距離的其中一種定義，本文所說的Jaro距離是編輯距離的另外一種定義，它也是對(duì)兩個(gè)字符串的相似度進(jìn)行衡量，以得出兩字符串的相似程度。下面我們一起來學(xué)習(xí)這個(gè)算法的原理以及實(shí)現(xiàn)吧。
算法定義
下面先說說Jaro distance（又稱Jaro similarity）,這是由Matthew A. Jaro在1989年提出的算法，而Jaro-Winkler distance是由William E. Winkler在Jaro distance的基礎(chǔ)上進(jìn)一步改進(jìn)的算法。
1、Jaro distance/similarity
對(duì)于兩個(gè)字符串s1和s2，它們的Jaro 相似度由下面公式給出：
其中：
①|(zhì)s1|和|s2|表示字符串s1和s2的長(zhǎng)度。
②m表示兩字符串的匹配字符數(shù)。
③t表示換位數(shù)目transpositions的一半。
這里的m和t是滿足一定條件下得出來的，在理解m和t的含義之前，我們先來認(rèn)識(shí)匹配窗口(記為matching window，mw)的概念。Jaro算法的字符之間的比較是限定在一個(gè)范圍內(nèi)的，如果在這個(gè)范圍內(nèi)兩個(gè)字符相等，那么表示匹配成功，如果超出了這個(gè)范圍，表示匹配失敗。而這個(gè)范圍就是匹配窗口，在Jaro算法中，它被定義為不超過下面表達(dá)式的值：
比如說字符串A("bacde")和B("abed")，它的匹配窗口大小為1，在匹配的過程中，字符'a'、'b'、'd'都是匹配的，indexInA('d') = 3，indexInB('d') = 3，二者的距離是0，小于匹配窗口大小。但對(duì)于'e'，雖然兩字符串都有'e'這個(gè)字符，但它們卻是不匹配的，因?yàn)?e'的下標(biāo)分別為4和2，距離為2 > mw，所以'e'是不匹配的。在這個(gè)例子中，由于有3個(gè)字符匹配，因此m = 3。換位數(shù)目表示不同順序的匹配字符的個(gè)數(shù)。同樣看這個(gè)例子，'a'和'b'都是匹配的，但'a'和'b'在兩個(gè)字符串的表示為"ba.."和"ab.."，它們的順序不同，因此這里換位數(shù)目transpositions = 2，而t = transpositions / 2 = 1。
對(duì)于匹配窗口的含義，筆者的理解是：匹配窗口是一個(gè)閾值，在這個(gè)閾值之內(nèi)兩個(gè)字符相等，可以認(rèn)為是匹配的；超過了這個(gè)閾值，即使存在另一個(gè)字符與該字符相等，但由于它們的距離太遠(yuǎn)了，二者的相關(guān)性太低了，不能認(rèn)為它們是匹配的。從上面的公式可以看出，該算法強(qiáng)調(diào)的是局部相似度。
對(duì)于任意字符串A和B，能求出它們的length、m和t，這樣便能代入公式求得二者的相似度(Jaro similarity)。從剛才的例子得到，|s1|=5，|s2|=4，m=3，t=1，代入公式可得：simj = (3/5 + 3/4 + (3-1)/3)/3 = 0.672
2、Jaro-Winkler distance/similarity
Jaro-Winkler similarity是在Jaro similarity的基礎(chǔ)上，做的進(jìn)一步修改，在該算法中，更加突出了前綴相同的重要性，即如果兩個(gè)字符串在前幾個(gè)字符都相同的情況下，它們會(huì)獲得更高的相似性。該算法的公式如下：
其中：
①simj 就是剛才求得的Jaro similarity。
②l表示兩個(gè)字符串的共同前綴字符的個(gè)數(shù)，最大不超過4個(gè)。
③p是縮放因子常量，它描述的是共同前綴對(duì)于相似度的貢獻(xiàn)，p越大，表示共同前綴權(quán)重越大，最大不超過0.25。p默認(rèn)取值是0.1。
圖解Jaro-Winkler similarity求解過程
下面以字符串A("abcdefgh")和字符串B("abehc")為例來介紹整個(gè)算法的流程。這里以短字符串為行元素，長(zhǎng)字符串為列元素，建立(|s1|+1)×(|s2|+1)的矩陣，這里匹配窗口的大小為3(注意包括距離為0的匹配)，然后根據(jù)公式不斷運(yùn)算：
從上面的圖以及公式，我們可以總結(jié)出求解的過程：字符串s1作為行元素，字符串s2作為列元素，窗口大小為mw，同時(shí)建立兩個(gè)布爾型數(shù)組，大小分別為s1和s2的長(zhǎng)度，布爾型數(shù)組對(duì)應(yīng)下標(biāo)的值True表示已匹配，false表示不匹配。
對(duì)于行元素的每一個(gè)字符c1，根據(jù)c1在該字符串s1中的下標(biāo)k，定位到s2的k位置，然后在該位置往前遍歷mw個(gè)單位，往后遍歷mw個(gè)單位，如果尋找到相等的字符，記在s2中的下標(biāo)為p。經(jīng)過這樣的一次遍歷，找到了k和p，我們分別標(biāo)記布爾型數(shù)組s1的k和布爾型數(shù)組s2的p為已匹配(true)，下次遍歷時(shí)就跳過該已匹配的字符。當(dāng)對(duì)s1的所有元素都遍歷完畢時(shí)，就找到了所有已匹配的字符，我們統(tǒng)計(jì)已匹配的字符便能得到m，然后對(duì)兩個(gè)布爾型數(shù)組同時(shí)按照順序比較，如果出現(xiàn)了true，但二者對(duì)應(yīng)字符串相應(yīng)位置的字符不相等，表示這是非順序的匹配，這樣就可以得到t。這樣就能根據(jù)m和t求出Jaro similarity了。至于Jaro-Winkler similarity，需要p參數(shù)，也不難，求出倆字符串最大共同前綴的大小即可。
如果讀者對(duì)上面的過程還有疑問，筆者再提一點(diǎn)，關(guān)鍵就在于判斷來自倆字符串的相等字符的距離是不是超過了閾值(即匹配窗口長(zhǎng)度)。這里的判斷方法是在某個(gè)位置進(jìn)行前后的搜索，包括當(dāng)前位置。
代碼實(shí)現(xiàn)
根據(jù)上面的實(shí)現(xiàn)思路以及圖解過程，我們能很容易寫出下面的代碼：
public class JaroWinklerDistance {
private float p = 0.1f;
private final float MAX_P = 0.25f;
private final int MAX_L = 4;
/**
* 用戶可以修改p參數(shù)，以提高共同前綴的權(quán)重
* @param p
*/
private void setP(float p){
this.p = p;
}
public float getJaroDistance(CharSequence s1,CharSequence s2){
if (s1 == null || s2 == null) return 0f;
int result[] = matches(s1,s2);
float m = result[0];
if (m == 0f)
return 0f;
float j = ((m / s1.length() + m / s2.length() + (m - result[1]) / m)) / 3;
return j;
}
public float getJaroWinklerDistance(CharSequence s1,CharSequence s2){
if (s1 == null || s2 == null) return 0f;
int result[] = matches(s1,s2);
float m = result[0];
if (m == 0f)
return 0f;
float j = ((m / s1.length() + m / s2.length() + (m - result[1]) / m)) / 3;
float jw = j + Math.min(p,MAX_P) * result[2] * (1 - j);
return jw;
}
private int[] matches(CharSequence s1,CharSequence s2){
//用max來保存較長(zhǎng)的字符串，min保存較短的字符串
//這是為了以短字符串為行元素遍歷，長(zhǎng)字符串為列元素遍歷。
CharSequence max,min;
if (s1.length() > s2.length()){
max = s1;
min = s2;
}else{
max = s2;
min = s1;
}
//匹配窗口的大小，對(duì)于每一行i，列j只在(i-matchedwindow,i+matchedwindow)內(nèi)移動(dòng)，
//在該范圍內(nèi)遇到相等的字符，表示匹配成功
int matchedWindow = Math.max(max.length() / 2 - 1,0);
//記錄字符串的匹配狀態(tài)，true表示已經(jīng)匹配成功
boolean[] minMatchFlag = new boolean[min.length()];
boolean[] maxMatchFlag = new boolean[max.length()];
int matches = 0;
for (int i = 0;i < min.length();i++){
char minChar = min.charAt(i);
//列元素的搜索：j的變化包括i往前搜索窗口長(zhǎng)度和i往后搜索窗口長(zhǎng)度。
for (int j = Math.max(i - matchedWindow,0);
j < Math.min(i + matchedWindow + 1,max.length());j++){
if (!maxMatchFlag[j] && minChar == max.charAt(j)){
maxMatchFlag[j] = true;
minMatchFlag[i] = true;
matches++;
break;
}
}
}
//求轉(zhuǎn)換次數(shù)和相同前綴長(zhǎng)度
int transpositions = 0;
int prefix = 0;
int j = 0;
for (int i = 0;i < min.length();i++){
if (minMatchFlag[i]){
while (!maxMatchFlag[j]) j++;
if (min.charAt(i) != max.charAt(j)){
transpositions++;
}
j++;
}
}
for(int i = 0;i < min.length();i++){
if (s1.charAt(i) == s2.charAt(i)){
prefix++;
}else {
break;
}
}
return new int[]{matches,transpositions / 2,prefix > MAX_L ? MAX_L : prefix};
}
public static void main(String args[]){
String s1 = "abcdefgh";
String s2 = "abehc";
JaroWinklerDistance distance = new JaroWinklerDistance();
System.out.println("字符串A(\"" + s1 +"\")"+"和字符串B(\"" + s2 + "\")：");
System.out.println("Jaro similarity:" + distance.getJaroDistance(s1,s2));
System.out.println("Jaro-Winkler similarity:" + distance.getJaroWinklerDistance(s1,s2));
}
}
我們運(yùn)行上面的代碼，可以得到下面的輸出：
這與我們圖解過程得到的結(jié)果手工計(jì)算出來的是一致的。
進(jìn)一步探究
經(jīng)過上面的學(xué)習(xí)，我們已經(jīng)掌握了這個(gè)算法的原理以及實(shí)現(xiàn)方法，下面我們接著來探究它的特性以及適用場(chǎng)景。
我們來看下面的一組實(shí)驗(yàn)結(jié)果：
關(guān)鍵字是fox，另外的字符串是包含有fox幾個(gè)字符的字符串，可以看出最高相似度的是"fox"在開始幾位的情況下，而"afoxbcd"反而比"foaxbcd"更低，雖然前者含有完整的"fox"而后者是分開的。同時(shí)"abcdfox"的相似度為0，即使它末尾含有"fox"。上面這幾個(gè)例子說明了jaro-winkler相似度對(duì)于前綴匹配更友好，并且越往前面匹配成功帶來的權(quán)重更大。由此可以看出，該算法可以用在單詞的匹配上，比如對(duì)于一個(gè)單詞"appropriate"，找出數(shù)據(jù)庫中與它最匹配的一個(gè)詞語，可以是"appropriation"，也可以是"appropriately"等。但是，該算法不適用在句子匹配上，因?yàn)槿绻P(guān)鍵字在句子的后面部分，相似度會(huì)急劇下降，甚至為0。
好了，這篇文章到這里就結(jié)束了~喜歡的不要忘記點(diǎn)個(gè)贊喲，謝謝閱讀！
