SubPixel 亚像素
ThinkPad R61 Trackpoint and Touchpad on
Jan
9
这是今天算法考试的最后一题，设计一个动态规划的算法来求两个字符串的编辑距离。
以为自己做对了，很happy —— 其实错了，好笨，sigh.
--
Levenshtein Distance (LD, 来文史特距离)也叫edit distance(编辑距离)，它用来表示2个字符串的相似度，LD定义为需要最少多少步基本操作才能让2个字符串相等，基本操作包含3个：插入, 删除, 替换；比如，kiteen和sitting之间的距离可以这么计算：
1，kitten -- > sitten, 替换k为s；
2，sitten -- > sittin, 替换e为i;
3，sittin -- > sitting, 增加g；
所以，其LD为3。
设计状态d[m][n] = d(A[1..m], B[1..n])，易知：
d[0][0] = 0;
d[i][0] = i;
d[0][j] = j;
d[i][j] = min( d[i-1][j-1] + (If A[i]=B[j] Then 0 Else 1 End If), //修改一个字符
d[i-1][j] + 1, //插入一个字符
d[i][j-1] + 1 //删除一个字符
于是可以递推地填满一个 m * n 的矩阵，即得答案。
计算LD的算法表示为(C++代码)：
这个算法其实就是一个矩阵的计算：
最后的d[m][n]就是求得的答案。
@ 2009-06-14
贴一个优化空间复杂度为O(n)的代码(滚动数组)：
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
以为自己做对了，很happy —— 其实错了，好笨，sigh.
--
Levenshtein Distance (LD, 来文史特距离)也叫edit distance(编辑距离)，它用来表示2个字符串的相似度，LD定义为需要最少多少步基本操作才能让2个字符串相等，基本操作包含3个：插入, 删除, 替换；比如，kiteen和sitting之间的距离可以这么计算：
1，kitten -- > sitten, 替换k为s；
2，sitten -- > sittin, 替换e为i;
3，sittin -- > sitting, 增加g；
所以，其LD为3。
设计状态d[m][n] = d(A[1..m], B[1..n])，易知：
d[0][0] = 0;
d[i][0] = i;
d[0][j] = j;
d[i][j] = min( d[i-1][j-1] + (If A[i]=B[j] Then 0 Else 1 End If), //修改一个字符
d[i-1][j] + 1, //插入一个字符
d[i][j-1] + 1 //删除一个字符
于是可以递推地填满一个 m * n 的矩阵，即得答案。
计算LD的算法表示为(C++代码)：
int d[1010][1010];
int dist(string a, string b){
int m = a.size(), n = b.size(), i, j;
for(i = 0; i <= m; ++i) d[i][0] = i;
for(j = 0; j <= n; ++j) d[0][j] = j;
for (i = 1; i <= m; ++i){
for(j = 1; j <= n; ++j){
// -------------- a, b是从0开始计数的
d[i][j] = d[i-1][j-1] + (a[i-1]==b[j-1]?0:1); //修改一个字符
d[i][j] = min(d[i][j], d[i-1][j] + 1); //插入一个字符
d[i][j] = min(d[i][j], d[i][j-1] + 1); //删除一个字符
}
}
for (i = 0; i <= m; ++i){ //打印矩阵
for(j = 0; j <= n; ++j)
printf("%5d ", d[i][j]);
printf("\n");
}
return d[m][n];
}
int dist(string a, string b){
int m = a.size(), n = b.size(), i, j;
for(i = 0; i <= m; ++i) d[i][0] = i;
for(j = 0; j <= n; ++j) d[0][j] = j;
for (i = 1; i <= m; ++i){
for(j = 1; j <= n; ++j){
// -------------- a, b是从0开始计数的
d[i][j] = d[i-1][j-1] + (a[i-1]==b[j-1]?0:1); //修改一个字符
d[i][j] = min(d[i][j], d[i-1][j] + 1); //插入一个字符
d[i][j] = min(d[i][j], d[i][j-1] + 1); //删除一个字符
}
}
for (i = 0; i <= m; ++i){ //打印矩阵
for(j = 0; j <= n; ++j)
printf("%5d ", d[i][j]);
printf("\n");
}
return d[m][n];
}
这个算法其实就是一个矩阵的计算：
引用
调用dist("abcdef", "acddaf")可以得到输出为:
0 1 2 3 4 5 6
1 0 1 2 3 4 5
2 1 1 2 3 4 5
3 2 1 2 3 4 5
4 3 2 1 2 3 4
5 4 3 2 2 3 4
6 5 4 3 3 3 3
0 1 2 3 4 5 6
1 0 1 2 3 4 5
2 1 1 2 3 4 5
3 2 1 2 3 4 5
4 3 2 1 2 3 4
5 4 3 2 2 3 4
6 5 4 3 3 3 3
最后的d[m][n]就是求得的答案。
@ 2009-06-14
贴一个优化空间复杂度为O(n)的代码(滚动数组)：
int diff(char *a, char *b){
int *d[2], i, j;
int m = strlen(a), n = strlen(b);
d[0] = new int[n + 1];
d[1] = new int[n + 1];
int turn = 0, pre, t;
for (i = 0; i <= n; ++i) d[turn][i] = i;
for (i = 1; i <= m; ++i){
pre = turn;
turn = (turn + 1) % 2;
d[turn][0] = i;
for(int p=0;p<=n;p++)printf("%d ",d[pre][p]);printf("\n");
for(j = 1; j <= n; ++j){
t = d[pre][j-1] + (a[i-1] == b[j-1] ? 0 : 1);
t = min(t, d[pre][j] + 1);
d[turn][j] = min(t, d[turn][j-1] + 1);
}
}
for(int p=0;p<=n;p++)printf("%d ",d[turn][p]);printf("\n");
t = d[turn][n];
delete[] d[0];
delete[] d[1];
return t;
}
int *d[2], i, j;
int m = strlen(a), n = strlen(b);
d[0] = new int[n + 1];
d[1] = new int[n + 1];
int turn = 0, pre, t;
for (i = 0; i <= n; ++i) d[turn][i] = i;
for (i = 1; i <= m; ++i){
pre = turn;
turn = (turn + 1) % 2;
d[turn][0] = i;
for(int p=0;p<=n;p++)printf("%d ",d[pre][p]);printf("\n");
for(j = 1; j <= n; ++j){
t = d[pre][j-1] + (a[i-1] == b[j-1] ? 0 : 1);
t = min(t, d[pre][j] + 1);
d[turn][j] = min(t, d[turn][j-1] + 1);
}
}
for(int p=0;p<=n;p++)printf("%d ",d[turn][p]);printf("\n");
t = d[turn][n];
delete[] d[0];
delete[] d[1];
return t;
}
欢迎扫码关注：
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
0 1 2 3 4 5 6
1 0 1 2 3 4 5
2 1 1 2 3 4 5
3 2 1 2 3 4 5
4 3 2 1 2 3 4
5 4 3 2 2 3 4
6 5 4 3 3 3 3
如何通过以上知道LD
这个编辑距离就是矩阵的最后一个元素啊，就是3咯
0 1 2 3 4 5 6
1 0 1 2 3 4 5
2 1 1 2 3 4 5
3 2 1 2 3 4 5
4 3 2 1 2 3 4
5 4 3 2 2 3 4
6 5 4 3 3 3 3
如何通过以上知道LD