一個快速、高效的Levenshtein算法實現

jopen 11年前發布 | 12K 次閱讀算法

Levenshtein算法，用于計算兩個字符串之間的Levenshtein距離。而Levenshtein距離又稱為編輯距離，是指兩個字符串之間，由一個轉換成另一個所需的最少編輯操作次數。許可的編輯操作包括將一個字符替換成另一個字符，插入一個字符，刪除一個字符。

概述

Levenshtein距離用來描述兩個字符串之間的差異。我在一個網絡爬蟲程序里面使用這個算法來比較兩個網頁之間的版本，如果網頁的內容有足夠多的變動，我便將它更新到我的數據庫。

說明

原來的算法是創建一個大小為StrLen1*StrLen2的矩陣。如果所有字符串加起來是1000個字符那么長的話，那么這個矩陣就會是1M；如果字符串是10000個字符，那么矩陣就是100M。如果元素都是整數（這里是指數字，Int32）的話，那么矩陣就會是4*100M == 400MB這么大，唉……

現在的算法版本只使用2*StrLen個元素，這使得后面給出的例子成為2*10,000*4 = 80 KB。其結果是，不但內存占用更少，而且速度也變快了！因為這使得內存分配只需要很少的時間來完成。當兩個字符串的長度都是1k左右時，新算法的效率是舊算法的兩倍！

示例

原來的版本將會創建一個矩陣[6+1, 5+1]，而我的新算法將會創建兩個向量[6+1]（黃色元素）。在這兩個算法版本中，字符串的順序是無關緊要、無所謂的，也就是說，它也可以是矩陣[5+1, 6+1]和兩個向量[5+1]。

新的算法

步驟

</tr>

</tr> </tbody> </table>

本小節將演示如何計算"GUMBO"和"GAMBOL"兩個字符串的Levenshtein距離。

步驟1、2

步驟	說明
1	設置n為字符串s的長度。("GUMBO") 設置m為字符串t的長度。("GAMBOL") 如果n等于0，返回m并退出。如果m等于0，返回n并退出。構造兩個向量v0[m+1] 和v1[m+1]，串聯0..m之間所有的元素。
2	初始化 v0 to 0..m。
3	檢查 s (i from 1 to n) 中的每個字符。
4	檢查 t (j from 1 to m) 中的每個字符
5	如果 s[i] 等于 t[j]，則編輯代價為 0；如果 s[i] 不等于 t[j]，則編輯代價為1。
6	設置單元v1[j]為下面的最小值之一： a、緊鄰該單元上方+1：v1[j-1] + 1 b、緊鄰該單元左側+1：v0[j] + 1 c、該單元對角線上方和左側+cost：v0[j-1] + cost
7	在完成迭代 (3, 4, 5, 6) 之后，v1[m]便是編輯距離的值。

</tr>

</tr> </tbody> </table>

步驟3-6，當 i = 1

	v0	v1
		G	U	M	B	O
	0	1	2	3	4	5
G	1
A	2
M	3
B	4
O	5
L	6

</tr>

</tr> </tbody> </table>

步驟3-6，當 i = 2

	v0	v1
		G	U	M	B	O
	0	1	2	3	4	5
G	1	0
A	2	1
M	3	2
B	4	3
O	5	4
L	6	5

</tr>

</tr> </tbody> </table>

步驟3-6，當 i = 3

		v0	v1
		G	U	M	B	O
	0	1	2	3	4	5
G	1	0	1
A	2	1	1
M	3	2	2
B	4	3	3
O	5	4	4
L	6	5	5

</tr>

</tr> </tbody> </table>

步驟3-6，當 i = 4

			v0	v1
		G	U	M	B	O
	0	1	2	3	4	5
G	1	0	1	2
A	2	1	1	2
M	3	2	2	1
B	4	3	3	2
O	5	4	4	3
L	6	5	5	4

</tr>

</tr> </tbody> </table>

步驟3-6，當 i = 5

				v0	v1
		G	U	M	B	O
	0	1	2	3	4	5
G	1	0	1	2	3
A	2	1	1	2	3
M	3	2	2	1	2
B	4	3	3	2	1
O	5	4	4	3	2
L	6	5	5	4	3

</tr>

</tr> </tbody> </table>

步驟7

編輯距離就是矩陣右下角的值，v1[m] == 2。由"GUMBO"變換為"GAMBOL"的過程對于我來說是很只管的，即通過將"A"替換為"U"，并在末尾追加"L"這樣子（實際上替換的過程是由移除和插入兩個操作組合而成的）。

改良

如果您確信你的字符串永遠不會超過2^16（65536）個字符，那么你可以使用ushort來表示而不是int，如果字符串少于2^8個，還可以使用byte。我覺得這個算法用非托管代碼實現的話可能會更快，但我沒有試過。

參考文獻

Levenshtein Distance, in Three Flavors

public static int levenshtein_new(String str1,String str2){
        int n = str1.length();
        int m = str2.length();
        if(n==0){
            return m;
        }
        else if(m==0){
            return n;
        }
        else{
            int v0[] = new int[m+1];
            int v1[] = new int[m+1];
            for(int i=0;i<m+1;i++){
                v0[i] = i;
            }
            for(int i=0;i<m+1;i++){
                v1[i] = 0;
            }
            int cost = 0;
            for(int i=1;i<n+1;i++){
                v1[0] = i;
                for(int j=1;j<m+1;j++){
                    if(str1.charAt(i-1) == str2.charAt(j-1)){
                        cost = 0;
                    }
                    else{
                        cost = 1;
                    }
                    int a = v0[j]+1;
                    int b = v1[j-1]+1;
                    int c = v0[j-1]+cost;
                    v1[j] = min(a,b,c);
                }
                for(int k=0;k<m+1;k++){
                    v0[k]=v1[k];
                }
            }
            return v1[m];
        }

本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1386123230001.html

算法

一個快速、高效的Levenshtein算法實現

概述

說明

示例

新的算法

步驟

步驟1、2

步驟3-6，當 i = 1

步驟3-6，當 i = 2

步驟3-6，當 i = 3

步驟3-6，當 i = 4

步驟3-6，當 i = 5

步驟7

改良

參考文獻

相關經驗

相關資訊

相關文檔

目錄