当前位置: 代码迷 >> Web前端 >> 字符串形似度Levenshtein算法
  详细解决方案

字符串形似度Levenshtein算法

热度:376   发布时间:2012-10-27 10:42:26.0
字符串相似度Levenshtein算法

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

?

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

?