萊文斯坦距離

shtein shtein cost=1。

萊文斯坦距離(LD)用於衡量兩個字元串之間的相似度。以下我們稱這兩個字元串分別為 s (原字元串) 和 t(目標字元串)。萊文斯坦距離被定義為''將字元串 s變換為字元串 t 所需的刪除、插入、替換操作的次數''。

例如：

• s="test", t="test", 那么 LD(s,t)=0，因為不需要做任何變換兩者已相等；
• s="test", t="tent", 那么 LD(s,t)=1，因為s變換為t只需做一次替換(將"s"替換為"n")。

萊文斯坦距離越大，字元串的相似程度越低。

萊文斯坦距離以俄國科學家Vladimir levenshtein命名，他於1965年發明了這個算法。如果你對Levenshtein這個詞的發音有問題，也可以稱這個距離為編輯距離。

萊文斯坦距離被套用於以下領域：

• 拼寫檢查
• 語音識別
• DNA分析
• 剽竊檢測

算法

設 s 的長度為 n，t 的長度為 m。如果 n = 0，則返回 m 並退出；如果 m=0，則返回 n 並退出。否則構建一個數組 d[0..m, 0..n]。

將第0行初始化為 0..n，第0列初始化為0..m。

依次檢查 s 的每個字母(i=1..n)。

依次檢查 t 的每個字母(j=1..m)。

如果 s[i]=t[j]，則 cost=0；如果 s[i]!=t[j]，則 cost=1。

將 d[i,j] 設定為以下三個值中的最小值：

緊鄰當前格上方的格的值加一，即 d[i-1,j]+1

緊鄰當前格左方的格的值加一，即 d[i,j-1]+1

當前格左上方的格的值加cost，即 d[i-1,j-1]+cost

重複3-6步直到循環結束。d[n,m]即為萊茵斯坦距離。

代碼

代碼請參考原文網站。該網站給出了 Java、C++、Visual Basic三種語言的實現，又在頁面最下方的連結中給出了Perl、PL/SQL、TSQL、C#、Delphi、PHP等數十種語言的實現方式。