?????编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein Distance。一个字符串可以通过增加一个字符，删除一个字符，替换一个字符得到另外一个字符串，假设，我们把从字符串A转换成字符串B，前面3种操作所执行的最少次数称为AB相似度
如??abc adc??度为 1
? ?? ?ababababa babababab 度为 2
? ?? ?abcd acdb 度为2
?
| 1 | Set n to be the length of s. Set m to be the length of t. If n = 0, return m and exit. If m = 0, return n and exit. Construct a matrix containing 0..m rows and 0..n columns. |
| 2 | Initialize the first row to 0..n. Initialize the first column to 0..m. |
| 3 | Examine each character of s (i from 1 to n). |
| 4 | Examine each character of t (j from 1 to m). |
| 5 | If s[i] equals t[j], the cost is 0. If s[i] doesn't equal t[j], the cost is 1. |
| 6 | Set cell d[i,j] of the matrix equal to the minimum of: a. The cell immediately above plus 1: d[i-1,j] + 1. b. The cell immediately to the left plus 1: d[i,j-1] + 1. c. The cell diagonally above and to the left plus the cost: d[i-1,j-1] + cost. |
| 7 | After the iteration steps (3, 4, 5, 6) are complete, the distance is found in cell d[n,m]. |
?
Example
This section shows how the Levenshtein distance is computed when the source string is "GUMBO" and the target string is "GAMBOL".
?
| ? | ? | G | U | M | B | O |
| ? | 0 | 1 | 2 | 3 | 4 | 5 |
| G | 1 | ? | ? | ? | ? | ? |
| A | 2 | ? | ? | ? | ? | ? |
| M | 3 | ? | ? | ? | ? | ? |
| B | 4 | ? | ? | ? | ? | ? |
| O | 5 | ? | ? | ? | ? | ? |
| L | 6 | ? | ? | ? | ? | ? |
?
?
| ? | ? | 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 | ? | ? | ? | ? |
?
?
| ? | ? | 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 | ? | ? | ? |
?
?
| ? | ? | 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 | ? | ? |
?
?
| ? | ? | 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 | ? |
?
?
| ? | ? | G | U | M | B | O |
| ? | 0 | 1 | 2 | 3 | 4 | 5 |
| G | 1 | 0 | 1 | 2 | 3 | 4 |
| A | 2 | 1 | 1 | 2 | 3 | 4 |
| M | 3 | 2 | 2 | 1 | 2 | 3 |
| B | 4 | 3 | 3 | 2 | 1 | 2 |
| O | 5 | 4 | 4 | 3 | 2 | 1 |
| L | 6 | 5 | 5 | 4 | 3 | 2 |
?
Levenshtein distance可以用来：
Spell checking(拼写检查)
Speech recognition(语句识别)
DNA analysis(DNA分析)
Plagiarism detection(抄袭检测)
LD用m*n的矩阵存储距离值。算法大概过程：
str1或str2的长度为0返回另一个字符串的长度。
初始化(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-它们的距离/字符串长度最大值。
?
private int ComputeDistance (string s, string t)
{
int n=s.Length;
int m=t.Length;
int[,] distance=new int[n + 1, m + 1]; // matrix
int cost=0;
if(n == 0) return m;
if(m == 0) return n;
//init1
for(int i=0; i <= n; distance[i, 0]=i++);
for(int j=0; j <= m; distance[0, j]=j++);
//find min distance
for(int i=1; i <= n; i++)
{
for(int j=1; j <= m;j++)
{
cost=(t.Substring(j - 1, 1) ==
s.Substring(i - 1, 1) ? 0 : 1);
distance[i,j]=Min3(distance[i - 1, j] + 1,
distance[i, j - 1] + 1,
distance[i - 1, j - 1] + cost);
}
}
return distance[n, m];
}
?