自然语言处理(5)之Levenshtein最小编辑距离算法

自然语言处理(5)之Levenshtein最小编辑距离算法

题记：之前在公司使用Levenshtein最小编辑距离算法来实现相似车牌的计算的特性开发，正好本节来总结下Levenshtein最小编辑距离算法。

算法简介：

Levenshtein距离，是俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。它是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。因此可以使用Levenshtein距离算法来描述两个字符串的相似程度。

例如将kitten一字经过3步转成sitting：

1. sitten （k→s）
2. sittin （e→i）
3. sitting （→g）

算法描述：

我们定义这样一个函数——edit(i, j)，它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。

显然可以有如下动态规划公式：

• if i == 0 且 j == 0，edit(i, j) = 0
• if i == 0 且 j > 0，edit(i, j) = j
• if i > 0 且j == 0，edit(i, j) = i
• if i ≥ 1  且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) }，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，f(i, j) = 1；否则，f(i, j) = 0。
• 网上关于这部分的描述很多都存在错误。假设两个字符串分别为A和B，他们的长度分别为length(A),length(B),那么建立的矩阵的大小应该为(length(A)+1)*(length(B)+1)。其中第一行和第一列只是初始化，如下面的步骤所示。

		0	f	a	i	l	i	n	g
0
s
a
i
l
n

		0	a	i	l	i	n	g
	0	1	3	4	5	6	7	8
0	1	0	2	3	4	5	6	7
s	2	1						6
a	3	2
i	4	3
l	5	4
n	6	5

• 计算edit(1, 1)，
  • edit(0, 1) + 1 == 2，
  • edit(1, 0) + 1 == 2，
  • edit(0, 0) + f(1, 1) == 0 + 1 == 1，
  • min(edit(0, 1)，edit(1, 0)，edit(0, 0) + f(1, 1))==1，
  • 因此edit(1, 1) == 1。 依次类推：

		0	f	a	i	l	i	n	g
	0	1	2	3	4	5	6	7	8
0	1	0	1	2	3	4	5	6	7
s	2	1	1	2
a	3	2	2	1
i	4	3	3	2
l	5	4	4	3
n	6	5	5	4

• edit(2, 1) + 1 == 3，
  • edit(1, 2) + 1 == 3，
  • edit(1, 1) + f(2, 2) == 1 + 0 == 1，其中s1[2] == 'a' 而 s2[1] == 'f'‘，两者不相同，所以交换相邻字符的操作不计入比较最小数中计算。
  • 以此计算，得出最后矩阵为：

		0	f	a	i	l	i	n	g
	0	1	2	3	4	5	6	7	8
0	1	0	1	2	3	4	5	6	7
s	2	1	1	2	3	4	5	6	7
a	3	2	2	1	2	3	4	5	6
i	4	3	3	2	1	2	3	4	5
l	5	4	4	3	2	1	2	3	4
n	6	5	5	4	3	2	2	2	3

• 最后可以求出S1=osailn 和 S2=ofailin 的编辑距离为3，即由一个字符替换，有一个字符增加，S1经过两步可以转换成S2。
• 上述算法中对角线上的计算是计算字符替换操作，而横向和竖向的计算则是计算增加和删除操作，通过逐行比较且相加的方式把几个操作的结果进行汇总。

算法实现：

下面用JAVA代码来实现上述过程：

 public class LevenshteinEdit {

     public int editDistanceCompute(String strA,String strB){

         int iLengthA = strA.length()+1;
         int iLengthB = strB.length()+1;
         int maxtri[][] = new int[iLengthA][iLengthB];

         for(int i = 0 ; i < iLengthA ; i++){
             maxtri[i][0]=i;
         }

         for(int j = 1; j < iLengthB ; j++){
             maxtri[0][j]=j;
         }

         for(int j = 1 ; j < iLengthB ; j++ ){

             for(int i = 1 ; i < iLengthA ; i++ ){

                 int min = maxtri[i-1][j-1]+(strA.charAt(i-1) == strB.charAt(j-1)? 0 : 1);

                 int iUp = maxtri[i][j-1] + 1;

                 int iLeft = maxtri[i-1][j] + 1;

                 if ( min > iUp) {
                     min = iUp;
                 }

                 if ( min > iLeft ) {
                     min = iLeft;
                 }

                 maxtri[i][j] = min;
             }
         }

         return maxtri[iLengthA-1][iLengthB-1];
     }

     public static void main(String[] args) {
         String strA = "osailn";
         String strB = "ofailin";
         LevenshteinEdit le = new LevenshteinEdit();
         System.out.println(le.editDistanceCompute(strA, strB));
         System.out.println(le.editDistanceCompute("asailn", strB));
     }
 }

SOLR实现：

上述代码还是存在优化的空间的，比如实际上每次只需要存储上一行和当前行的数据就行，这样可以减少字符串长时运算所需要的内存。

Solr/Lucene当中也使用了Levenshtein距离来进行拼写检查的，同上述的代码不同之处就是Solr使用了前文讲到的存储优化。

  //*****************************
     // Compute Levenshtein distance: see org.apache.commons.lang.StringUtils#getLevenshteinDistance(String, String)
     //*****************************
     @Override
     public float getDistance (String target, String other) {
       char[] sa;
       int n;
       int p[]; //'previous' cost array, horizontally
       int d[]; // cost array, horizontally
       int _d[]; //placeholder to assist in swapping p and d

         /*
            The difference between this impl. and the previous is that, rather
            than creating and retaining a matrix of size s.length()+1 by t.length()+1,
            we maintain two single-dimensional arrays of length s.length()+1.  The first, d,
            is the 'current working' distance array that maintains the newest distance cost
            counts as we iterate through the characters of String s.  Each time we increment
            the index of String t we are comparing, d is copied to p, the second int[].  Doing so
            allows us to retain the previous cost counts as required by the algorithm (taking
            the minimum of the cost count to the left, up one, and diagonally up and to the left
            of the current cost count being calculated).  (Note that the arrays aren't really
            copied anymore, just switched...this is clearly much better than cloning an array
            or doing a System.arraycopy() each time  through the outer loop.)

            Effectively, the difference between the two implementations is this one does not
            cause an out of memory condition when calculating the LD over two very large strings.
          */

         sa = target.toCharArray();
         n = sa.length;
         p = new int[n+1];
         d = new int[n+1]; 

         final int m = other.length();
         if (n == 0 || m == 0) {
           if (n == m) {
             return 1;
           }
           else {
             return 0;
           }
         } 

         // indexes into strings s and t
         int i; // iterates through s
         int j; // iterates through t

         char t_j; // jth character of t

         int cost; // cost

         for (i = 0; i<=n; i++) {
             p[i] = i;
         }

         for (j = 1; j<=m; j++) {
             t_j = other.charAt(j-1);
             d[0] = j;

             for (i=1; i<=n; i++) {
                 cost = sa[i-1]==t_j ? 0 : 1;
                 // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
                 d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1),  p[i-1]+cost);
             }

             // copy current distance counts to 'previous row' distance counts
             _d = p;
             p = d;
             d = _d;
         }

         // our last action in the above loop was to switch d and p, so p now
         // actually has the most recent cost counts
         return 1.0f - ((float) p[n] / Math.max(other.length(), sa.length));
     }

总结

本节学习了很常用的一个字符串比较算法，Levenshtein距离，算法内容以及实现还是比较简单。Solr给我们提供了使用的很好例子。

但是上述的算法还是比较原始，还是可以有很大的改善空间，比如可以区分替换，删除，增加操作的不同权重，本人在公司相似车牌特性中就使用了不同的权重，后续会整理写出。