《編程之美》中有計算字符串的相似度，采用動態(tài)規(guī)劃自頂向下的解決方法，但是這樣造成子問題的多次求解，如何用備忘錄來保存子問題的結(jié)果來避免多次求解呢，其實計算字符串的相似度就是編輯距離的問題。
轉(zhuǎn)自： http://www.cnblogs.com/biyeymyhjob/archive/2012/09/28/2707343.html

編輯距離概念描述：

編輯距離，又稱Levenshtein距離，是指兩個字串之間，由一個轉(zhuǎn)成另一個所需的最少編輯操作次數(shù)。許可的編輯操作包括將一個字符替換成另一個字符，插入一個字符，刪除一個字符。

例如將kitten一字轉(zhuǎn)成sitting：

sitten （k→s）

sittin （e→i）

sitting （→g）

俄羅斯科學家Vladimir Levenshtein在1965年提出這個概念。

?

問題：找出字符串的編輯距離，即把一個字符串s1最少經(jīng)過多少步操作變成編程字符串s2，操作有三種，添加一個字符，刪除一個字符，修改一個字符

?

解析：

首先定義這樣一個函數(shù)——edit(i, j)，它表示第一個字符串的長度為i的子串到第二個字符串的長度為j的子串的編輯距離。

顯然可以有如下動態(tài)規(guī)劃公式：

• 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) }，當?shù)谝粋€字符串的第i個字符不等于第二個字符串的第j個字符時，f(i, j) = 1；否則，f(i, j) = 0。

?

?

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

?

?

?	0	f	a	i	l	i	n	g
0	0	1	2	3	4	5	6	7
s	1	?	?	?	?	?	?	?
a	2	?	?	?	?	?	?	?
i	3	?	?	?	?	?	?	?
l	4	?	?	?	?	?	?	?
n	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	0	1	2	3	4	5	6	7
s	1	1	2	3	4	5	6	7
a	2	2	?	?	?	?	?	?
i	3	?	?	?	?	?	?	?
l	4	?	?	?	?	?	?	?
n	5	?	?	?	?	?	?	?

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'‘，兩者不相同，所以交換相鄰字符的操作不計入比較最小數(shù)中計算。以此計算，得出最后矩陣為：

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

?

程序（C++）：注意二維數(shù)組動態(tài)分配和釋放的方法！！

#include <iostream> #include <string>using namespace std;int min(int a, int b) {return a < b ? a : b; }int edit(string str1, string str2) {int max1 = str1.size();int max2 = str2.size();int **ptr = new int*[max1 + 1];for(int i = 0; i < max1 + 1 ;i++){ptr[i] = new int[max2 + 1];}for(int i = 0 ;i < max1 + 1 ;i++){ptr[i][0] = i;}for(int i = 0 ;i < max2 + 1;i++){ptr[0][i] = i;}for(int i = 1 ;i < max1 + 1 ;i++){for(int j = 1 ;j< max2 + 1; j++){int d;int temp = min(ptr[i-1][j] + 1, ptr[i][j-1] + 1);if(str1[i-1] == str2[j-1]){d = 0 ;}else{d = 1 ;}ptr[i][j] = min(temp, ptr[i-1][j-1] + d);}}cout << "**************************" << endl;for(int i = 0 ;i < max1 + 1 ;i++){for(int j = 0; j< max2 + 1; j++){cout << ptr[i][j] << " " ;}cout << endl;}cout << "**************************" << endl;int dis = ptr[max1][max2];for(int i = 0; i < max1 + 1; i++){delete[] ptr[i];ptr[i] = NULL;}delete[] ptr;ptr = NULL;return dis; }int main(void) {string str1 = "sailn";string str2 = "failing";int r = edit(str1, str2);cout << "the dis is : " << r << endl;return 0; }

執(zhí)行效果：

?

總結(jié)

以上是生活随笔為你收集整理的最小编辑距离的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。