萊文斯坦距離,又稱Levenshtein距離，編輯距離，俄羅斯科學家弗拉基米爾·萊文斯坦（畢業(yè)于莫斯科國立大學數(shù)學和力學系）在1965年提出，他因?qū)m錯碼理論和信息理論的貢獻，于2006年獲得IEEE Richard W. Hamming獎章。
定義：萊文斯坦距離也稱編輯距離，指的是將文本 A 編輯成文本 B 需要的最少變動次數(shù)（每次只能增加、刪除或修改一個字）。
用途：可以用來計算字符串的相似度，文本相似度, 拼寫糾錯和抄襲偵測等等
優(yōu)點：準確率很高，編輯距離算出來很小，文本相似度肯定很高。
缺點：召回率不高，由于編輯距離與文本的順序有關(guān)。在文字相同，文字順序變化很大的情況下，相似度會變得很低。比如“正大光明”和“光明正大”其實是一個意思。但編輯距離是4，完全不匹配
計算解析：
首先定義的單字符編輯操作有且僅有三種：
插入（Insertion）
刪除（Deletion）
替換（Substitution）
我們可以給不同的操作賦予不同代價值，萊溫斯坦（Levenshtein）定義該編輯距離最簡單的方式是給每種操作賦予相同的代價值1。萊溫斯坦另外一種定義只允許插入和刪除操作，不允許替換操作。這樣相當于替換用插入和刪除兩種操作實現(xiàn)，替換的代價值相當于變成2。
我們這里先用第一種定義將插入，刪除，替換的三種操作代價都定為值1
假設(shè)我們把要比較相似度的兩個字符串做成一個二維數(shù)組
假如兩個字符串分別是String A="xyz"和String B="xymn"做成一個二維數(shù)組 i代表B的序號[行]，j代表A的序號[列]，i或者j等于0的時候代表大家都是空字符串, 我們用lev(i,j)來代表截止到指定坐標點，字符串要變成一樣所需的編輯距離。因此，如下圖，這里我們要求的值就是右下角(最終編輯距離)位置的值。
1.如果i=0或者j=0，lev(i,j)=j或者i，這里我們用0代表最前面的空串，這個位置的空串要編輯成一樣則不需要操作，lev(i,j) = 0，也就是下面這個情況
2.繼續(xù)用上面的公式（如果i=0或者j=0，lev(i,j)=j或者i），比如"0”編輯成”0x”只需要增加x一個操作。"0”編輯成”0xy”需要增加x和增加y一共兩個操作。推導出如下圖：
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ù)用來取三個編輯距離的最小值。我們先由此推導出i=1,j=1位置的值，lev(1,1) = min(lev(0,1)+1, lev(1,0)+1, lev(0,0)+h); 由于這個位置B[i]=A[j]相等, 所以h=0，那么lev(1,1) = min(2, 2, 0) = 0; 也就是”0x”編輯成”0x”的編輯距離為0。
4.依上公式繼續(xù)推導
由此可以得出”xyz”和“xymn”的編輯距離為2，那么兩個文本的相似度為（1 - （2/max(”xyz”字符串的長度，“xymn”字符串的長度)），（1 - (2/4)） = 0.50, 則相似度為50%.
Java版
public static float levenshtein(String msg, String msg2) {
//計算兩個字符串的長度。
int len1 = msg.length();
int len2 = msg2.length();
//建立文中說的數(shù)組，比字符長度大一個空間
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;
}
//計算兩個字符是否一樣，計算左上的值
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;
}
//取三個值中最小的
dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1,
dif[i - 1][j] + 1);
}
}
//取數(shù)組右下角的值，不同位置代表不同字符串的比較
//計算相似度
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);
是的，你沒看錯，php為了提高代碼執(zhí)行效率和你的編碼效率把算法封裝到C里面了。
┑(￣▽ ￣)┍
