字符串相似度Levenshtein算法

?????编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein Distance。一个字符串可以通过增加一个字符，删除一个字符，替换一个字符得到另外一个字符串，假设，我们把从字符串A转换成字符串B，前面3种操作所执行的最少次数称为AB相似度
如??abc adc??度为 1
? ?? ?ababababa babababab 度为 2
? ?? ?abcd acdb 度为2

?

StepDescription1Set 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.2Initialize the first row to 0..n.
Initialize the first column to 0..m.3Examine each character of s (i from 1 to n).4Examine each character of t (j from 1 to m).5If s[i] equals t[j], the cost is 0.
If s[i] doesn't equal t[j], the cost is 1.6Set 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.7After 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".

?

??GUMBO?012345G1?????A2?????M3?????B4?????O5?????L6?????

?

?

??GUMBO?012345G10????A21????M32????B43????O54????L65????

?

?

??GUMBO?012345G101???A211???M322???B433???O544???L655???

?

?

??GUMBO?012345G1012??A2112??M3221??B4332??O5443??L6554??

?

?

??GUMBO?012345G10123?A21123?M32212?B43321?O54432?L65543?

?

?

??GUMBO?012345G101234A211234M322123B433212O544321L655432

?

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];}

?