萊文斯坦距離,又稱Levenshtein距離蛙粘，編輯距離，俄羅斯科學(xué)家弗拉基米爾·萊文斯坦（畢業(yè)于莫斯科國(guó)立大學(xué)數(shù)學(xué)和力學(xué)系）在1965年提出璃岳，他因?qū)m錯(cuò)碼理論和信息理論的貢獻(xiàn)洁墙，于2006年獲得IEEE Richard W. Hamming獎(jiǎng)?wù)隆?/strong>
定義：萊文斯坦距離也稱編輯距離剿配，指的是將文本 A 編輯成文本 B 需要的最少變動(dòng)次數(shù)（每次只能增加、刪除或修改一個(gè)字）咽斧。
用途：可以用來(lái)計(jì)算字符串的相似度堪置，文本相似度, 拼寫(xiě)糾錯(cuò)和抄襲偵測(cè)等等
優(yōu)點(diǎn)：準(zhǔn)確率很高贷洲，編輯距離算出來(lái)很小，文本相似度肯定很高晋柱。
缺點(diǎn)：召回率不高优构，由于編輯距離與文本的順序有關(guān)。在文字相同雁竞，文字順序變化很大的情況下钦椭，相似度會(huì)變得很低。比如“正大光明”和“光明正大”其實(shí)是一個(gè)意思碑诉。但編輯距離是4彪腔，完全不匹配
計(jì)算解析：
首先定義的單字符編輯操作有且僅有三種：
插入（Insertion）
刪除（Deletion）
替換（Substitution）
我們可以給不同的操作賦予不同代價(jià)值，萊溫斯坦（Levenshtein）定義該編輯距離最簡(jiǎn)單的方式是給每種操作賦予相同的代價(jià)值1进栽。萊溫斯坦另外一種定義只允許插入和刪除操作德挣，不允許替換操作。這樣相當(dāng)于替換用插入和刪除兩種操作實(shí)現(xiàn)快毛，替換的代價(jià)值相當(dāng)于變成2格嗅。
我們這里先用第一種定義將插入，刪除唠帝，替換的三種操作代價(jià)都定為值1
假設(shè)我們把要比較相似度的兩個(gè)字符串做成一個(gè)二維數(shù)組
假如兩個(gè)字符串分別是String A="xyz"和String B="xymn"做成一個(gè)二維數(shù)組 i代表B的序號(hào)[行]屯掖，j代表A的序號(hào)[列]，i或者j等于0的時(shí)候代表大家都是空字符串, 我們用lev(i,j)來(lái)代表截止到指定坐標(biāo)點(diǎn)襟衰，字符串要變成一樣所需的編輯距離贴铜。因此，如下圖瀑晒，這里我們要求的值就是右下角(最終編輯距離)位置的值绍坝。
1.如果i=0或者j=0，lev(i,j)=j或者i苔悦，這里我們用0代表最前面的空串轩褐，這個(gè)位置的空串要編輯成一樣則不需要操作，lev(i,j) = 0间坐，也就是下面這個(gè)情況
2.繼續(xù)用上面的公式（如果i=0或者j=0灾挨，lev(i,j)=j或者i），比如"0”編輯成”0x”只需要增加x一個(gè)操作竹宋。"0”編輯成”0xy”需要增加x和增加y一共兩個(gè)操作劳澄。推導(dǎo)出如下圖：
3.如果i&&j>=1 則lev(i,j)=min{lev(i-1,j)+1,lev(i,j-1)+1,lev(i-1,j-1)+h} 如果B[i]=A[j]相等，則h=0蜈七，否則h=1秒拔； min函數(shù)用來(lái)取三個(gè)編輯距離的最小值。我們先由此推導(dǎo)出i=1,j=1位置的值飒硅，lev(1,1) = min(lev(0,1)+1, lev(1,0)+1, lev(0,0)+h); 由于這個(gè)位置B[i]=A[j]相等, 所以h=0砂缩，那么lev(1,1) = min(2, 2, 0) = 0; 也就是”0x”編輯成”0x”的編輯距離為0作谚。
4.依上公式繼續(xù)推導(dǎo)
由此可以得出”xyz”和“xymn”的編輯距離為2，那么兩個(gè)文本的相似度為（1 - （2/max(”xyz”字符串的長(zhǎng)度庵芭，“xymn”字符串的長(zhǎng)度)）妹懒，（1 - (2/4)） = 0.50, 則相似度為50%.
Java版
public static float levenshtein(String msg, String msg2) {
//計(jì)算兩個(gè)字符串的長(zhǎng)度。
int len1 = msg.length();
int len2 = msg2.length();
//建立文中說(shuō)的數(shù)組双吆，比字符長(zhǎng)度大一個(gè)空間
int[][] dif = new int[len1 + 1][len2 + 1];
//賦初值
for (int a = 0; a <= len1; a++) {
dif[a][0] = a;
}
for (int a = 0; a <= len2; a++) {
dif[0][a] = a;
}
//計(jì)算兩個(gè)字符是否一樣眨唬，計(jì)算左上的值
int temp;
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (msg.charAt(i - 1) == msg2.charAt(j - 1)) {
temp = 0;
} else {
temp = 1;
}
//取三個(gè)值中最小的
dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1,
dif[i - 1][j] + 1);
}
}
//取數(shù)組右下角的值，不同位置代表不同字符串的比較
//計(jì)算相似度
float similarity = 1 - (float) dif[len1][len2] / Math.max(len1, len2);
return similarity * 100.0f;
}
//得到最小值
public static int min(int... is) {
int min = Integer.MAX_VALUE;
for (int i : is) {
if (min > i) {
min = i;
}
}
return min;
}
php版
<?php
$str1 = "正大光明";
$str2 = "正光大";
echo sprintf("%.2f",(1.0 - (levenshtein($str1,$str2) / max(strlen($str1), strlen($str2)))) * 100.0);
是的好乐，你沒(méi)看錯(cuò)匾竿，php為了提高代碼執(zhí)行效率和你的編碼效率把算法封裝到C里面了。
┑(￣▽ ￣)┍
