minimum edit distance 最小编辑距离 相关介绍

编辑距离的定义：
   The edit distance between two strings of characters is the number of operations required to transform one of them into the other。

    编辑距离有很多种不同的定义方法，我们可以用多种不同的distance来反映edit distance.

比如 Hamming distance、 Levenshtein distance、 Longest common subsequence等等。

1.若使用Longest common subsequence来度量edit distance，则允许的操作有addition和deletion。

2.若使用Damerau-Levenshtein distance来度量edit distance，则允许的操作有addition、
  deletion、substitution和transposition of two adjacent characters。

3.若使用Hamming distance，则允许的操作只有substitution。（这也就要求比较的两个字符串是等长的）

4.若使用Levenshtein distance，则允许的操作有addition、deletion和substitution。

这里所说的操作的具体含义，解释如下：
比如计算字符串S1="ki" 和 字符串S2="si" 的编辑距离，若使用substitution操作，则距离为1，即把S1中的k替换为s，S1就可以变成S2了。 但若不允许使用substitution操作，只能使用add和delete操作，则距离为2，因为需要一次delete和一次add才能把S1转换成S2。

采用动态规划方法计算Levenshtein distance的代码如下：

 int LevenshteinDistance(char s[1..m], char t[1..n])
 {
   // d is a table with m+1 rows and n+1 columns
   declare int d[0..m, 0..n]
  
   for i from 0 to m
     d[i, 0] := i // deletion
   for j from 0 to n
     d[0, j] := j // insertion
  
   for j from 1 to n
   {
     for i from 1 to m
     {
       if s[i] = t[j] then 
         d[i, j] := d[i-1, j-1]
       else
         d[i, j] := minimum
                    (
                      d[i-1, j] + 1,  // deletion
                      d[i, j-1] + 1,  // insertion
                      d[i-1, j-1] + 1 // substitution
                    )
     }
   }
  
   return d[m,n]
 }

比较"ketten"和"sitting"的过程和产生的矩阵如下：