在搞驗證碼識别的時候需要比較字元代碼的相似度用到“編輯距離算法”，關于原理和C#實作做個記錄。
據百度百科介紹：
編輯距離，又稱Levenshtein距離（也叫做Edit Distance），是指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數，如果它們的距離越大，說明它們越是不同。許可的編輯操作包括将一個字元替換成另一個字元，插入一個字元，删除一個字元。
例如将kitten一字轉成sitting：
sitten （k→s）
sittin （e→i）
sitting （→g）
俄羅斯科學家Vladimir Levenshtein在1965年提出這個概念。是以也叫Levenshtein Distance。
例如
如果str1="ivan"，str2="ivan"，那麼經過計算後等于 0。沒有經過轉換。相似度=1-0/Math.Max(str1.length,str2.length)=1
如果str1="ivan1"，str2="ivan2"，那麼經過計算後等于1。str1的"1"轉換"2"，轉換了一個字元，是以距離是1，相似度=1-1/Math.Max(str1.length,str2.length)=0.8
DNA分析
拼字檢查
語音辨識
抄襲偵測
算法過程
str1或str2的長度為0傳回另一個字元串的長度。 if(str1.length==0) return str2.length; if(str2.length==0) return str1.length;
初始化(n+1)*(m+1)的矩陣d，并讓第一行和列的值從0開始增長。
掃描兩字元串（n*m級的），如果：str1[i] == str2[j]，用temp記錄它，為0。否則temp記為1。然後在矩陣d[i,j]賦于d[i-1,j]+1 、d[i,j-1]+1、d[i-1,j-1]+temp三者的最小值。
掃描完後，傳回矩陣的最後一個值d[n][m]即是它們的距離。
計算相似度公式：1-它們的距離/兩個字元串長度的最大值。
為了直覺表現，我将兩個字元串分别寫到行和列中，實際計算中不需要。我們用字元串“ivan1”和“ivan2”舉例來看看矩陣中值的狀況：
1、第一行和第一列的值從0開始增長
i
v
a
n
1
2
3
4
5
2、i列值的産生 Matrix[i - 1, j] + 1 ; Matrix[i, j - 1] + 1 ; Matrix[i - 1, j - 1] + t
0+t=0
1+1=2
取三者最小值=0
依次類推：1
3、V列值的産生
依次類推直到矩陣全部生成
最後得到它們的距離=1
相似度：1-1/Math.Max(“ivan1”.length,“ivan2”.length) =0.8
算法用C#實作
<code><strong>調用</strong></code>
<code><strong>結果</strong></code>
http://www.cnblogs.com/ivanyb/archive/2011/11/25/2263356.html
本文轉自左正部落格園部落格，原文連結：http://www.cnblogs.com/soundcode/p/4511064.html，如需轉載請自行聯系原作者