编辑距离算法的java实现 zz

[singba]

编辑距离算法的java实现
编辑距离就是用来计算从原串（s）转换到目标串（t）所需要的最少的插入，删除和替换的数目，在NLP中应用比较广泛。以下是一个java实现的版
本：
public class EditDistance {
/**
* 求三个数中的最小数Mar 1, 2007
*
* @param a
* @param b
* @param c
* @return
*/
private static int Minimum(int a, int b, int c) {
int mi;

mi = a;
if (b < mi) {
mi = b;
}
if (c < mi) {
mi = c;
}
return mi;
}

/**
* 计算两个字符串间的编辑距离Mar 1, 2007
* @param s
* @param t
* @return
*/
public static int getEditDistance(String s, String t) {
int d[][]; // matrix
int n; // length of s
int m; // length of t
int i; // iterates through s
int j; // iterates through t
char s_i; // ith character of s
char t_j; // jth character of t
int cost; // cost

// Step 1

n = s.length();
m = t.length();
if (n == 0) {
return m;
}
if (m == 0) {
return n;
}
d = new int[n + 1][m + 1];

// Step 2

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

for (j = 0; j <= m; j++) {
d[0][j] = j;
}

// Step 3

for (i = 1; i <= n; i++) {
s_i = s.charAt(i - 1);
// Step 4
for (j = 1; j <= m; j++) {
t_j = t.charAt(j - 1);
// Step 5
if (s_i == t_j) {
cost = 0;
} else {
cost = 1;
}
// Step 6
d[i][j] = Minimum(d[i - 1][j] + 1, d[i][j - 1] + 1,
d[i - 1][j - 1] + cost);
}
}
// Step 7
return d[n][m];

}
}

Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1518567