算法笔记1 - 编辑距离及其动态规划算法(Java代码)

时间:2021-03-21 19:17:01

转载请标注原链接:http://www.cnblogs.com/xczyd/p/3808035.html

编辑距离概念描述

编辑距离,又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。一般情况下编辑操作包括:

  1. 将一个字符替换成另一个字符;
  2. 插入一个字符;
  3. 删除一个字符;

例如,将单词kitten转成单词sitting需要如下三个步骤:

  1. sitten (k→s)
  2. sittin (e→i)
  3. sitting (→g)

俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。

编辑距离的应用在信息检索、拼写纠错、机器翻译、命名实体抽取、同义词寻找等问题中有较多的应用

问题定义

求出任意两个字符串的编辑距离,即把一个字符串s1最少经过多少步操作变成编程字符串s2。其中操作有三种,添加一个字符,删除一个字符,修改一个字符

问题解析

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

可以利用如下动态规划公式来解析问题:

  1. 若 i = 0 且 j = 0,那么 edit(i, j) = 0
  2. 若 i = 0 且 j > 0,那么 edit(i, j) = j
  3. 若 i > 0 且 j = 0,那么 edit(i, j) = i
  4. 若 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。

第1,2,3个公式理解起来都比较容易,第4个公式其实列出了字符串i向字符串j转变的三种方式(自左向右依次为在字符串A的末尾删除一个字符,在字符串A的末尾添加一个与字符串B的末尾相同的字符,将字符串A末尾的字符替换为字符串B末尾的字符),然后分别计算其编辑距离,最后取其中的最小值。

Java代码

由上述动态规划公式,可以编写编辑距离的Java代码如下:

public int minDistance(String word1, String word2) {
//若两个字符串都为空时,编辑距离为0
if((word1==null||word1.length()==0)&&(word2==null||word2.length()==0)){
return 0;
}
//若其中一个字符串为空时,编辑距离为另一个字符串的长度
if(word1==null||word1.length()==0){
return word2.length();
}
if(word2==null||word2.length()==0){
return word1.length();
} //建立二维数组来保存所有的edit(i,j)
int[][] edit_distance = new int[word1.length()+1][word2.length()+1]; for(int i=0;i<word1.length()+1;i++){
edit_distance[i][0] = i;
}
for(int j=0;j<word2.length()+1;j++){
edit_distance[0][j] = j;
} //套入动态规划公式
for(int i=1;i<word1.length()+1;i++){
for(int j=1;j<word2.length()+1;j++){
int d1 = edit_distance[i-1][j]+1;
int d2 = edit_distance[i][j-1]+1;
int d3 = edit_distance[i-1][j-1]+
              (word1.charAt(i-1)==word2.charAt(j-1)?0:1);
edit_distance[i][j] = Math.min(d1,Math.min(d2,d3));
}
} return edit_distance[word1.length()][word2.length()];
}

相关博客

http://www.cnblogs.com/biyeymyhjob/archive/2012/09/28/2707343.html 有注解有图写的相当好

http://www.cnblogs.com/pandora/archive/2009/12/20/levenshtein_distance.html