编辑距离及算法实现

简要

各位一定体验到过搜索引擎的纠错功能,当你在无意识的情况下将你搜索的内容输入错误时,搜索引擎会自动帮你纠错。如你本来想搜索happy,却不小心按到了y旁边的u,这时我们依然达到了我们想要的目的

Happy

那么这个是怎么实现的呢,先不考虑这个功能整体使用到的技术,先解决一个问题,它是怎么知道从happuhappy的,这就是我们今天要讲的编辑距离

概念

编辑距离(Edit Distance)

又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。一般来说,编辑距离越小,两个串的相似度越大。

happuhappy只是把u替换成了y,操作次数为一次,所以编辑距离为1

运用

因此,有了这个概念,当我们知道一个词是错误的时候(怎么知道它错了,后面讨论),就只需从正确的词中找出和它编辑距离最小的一个或多个,就可以帮助用户纠错了

如何计算编辑距离

比如要计算cafecoffee的编辑距离

先创建一个6x8的表(cafe长度为4,coffee长度为6,各加2),先在表中如下位置填入相应数字

0 0 c o f f e e
0 0 1 2 3 4 5 6
c 1
o 2
f 3
e 4

再从cc对应的表格,也就是表格的(3,3)位置开始,按照以下规则填充数字

  • 如果最上方的字符等于最左方的字符,则为左上方的数字。否则为左上方的数字+1。(对于3,3来说为0)
  • 左方数字+1(对于3,3格来说为2)
  • 上方数字+1(对于3,3格来说为2)

取上面得出的三个数字中最小数字填入(3,3)位置,根据上面得出的,最小为0,所以在(3,3)位置填入0,以此类推,完成所有空格的填充,如下

0 0 c o f f e e
0 0 1 2 3 4 5 6
c 1 0 1 2 3 4 5
o 2 1 1 2 3 4 5
f 3 2 2 1 2 3 4
e 4 3 3 2 2 2 3

取得表中右下角数字,既为cafecoffee的最小编辑距离,为3

LeetCode

LeetCode第72题就是一个编辑距离的题,更多LeetCode Java解法请到我的GitHub

Java代码

public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        if(m == 0)
            return n;
        if(n == 0)
            return m;
        int[][] d = new int[m + 1][n + 1]; 
        d[0][0] = 0;
        // left
        for(int i = 1; i < m + 1; i++)
            d[i][0] = i;
        // top
        for(int j = 1; j < n + 1; j++)
            d[0][j] = j;
        for(int i = 1; i < m + 1; i++){
            char l = word1.charAt(i-1);
            for(int j = 1; j < n + 1; j++){
                char u = word2.charAt(j-1);
                int v = l != u ? d[i - 1][j - 1] + 1 : d[i - 1][j - 1];
                v = Math.min(v, d[i - 1][j] + 1);
                d[i][j] = Math.min(v, d[i][j - 1] + 1);
            }
        }
        return d[m][n] ;  
    }
}
坚持原创分享,您的支持将鼓励我不断前行!