距離の計算とプロセス印刷の編集
16773 ワード
転載は出典を明記してください.http://www.cnblogs.com/fangpei/p/3570512.html.
前学期は王先生の『現代情報検索』の授業を選び、「辞書とフォールトトレランス検索」で編集距離について話し、編集距離を計算するにはダイナミックプランニングの方法を使っていて、面白いと感じて実現しました.
距離の定義を編集するには:
は、2つの文字列の間で、1つから別の文字列に移動するために必要な最小限の編集操作回数を指します.許可された編集操作には、1つの文字を別の文字に置き換え、1つの文字を挿入し、1つの文字を削除することが含まれます.
たとえばakittenをsittingに変換します.
kitten (a→ )
sitten (k→s)
sittin (e→i )
sitting (→g)
編集距離は4です.
次のコードを書きます.
上のダイナミックプランニングアルゴリズムのステッププロセスはマトリクスで表現され,対応する文字を比較する.
最初の行と最初の列:
等差数列で増加します.(以下の例を参照)
残りの要素:
内部左上隅:
行列に対応する2文字が等しい場合は、左上隅要素の内部右下隅の数値の値を割り当てます.
行列に対応する2文字が等しくない場合は、左上隅要素の内部右下隅の値に1を加算します.
内部右上隅の数値:
上の要素の内部右下隅の数値に1を加算します.
内部左下の数値:
左方要素の内部右下隅の数値に1を加算します.
内部右下の数値:
内部の他の3つの数字の最小値を指定します.
最後に求めた行列の最右下の数字は2文字列の編集距離である.
詳しくは『情報検索ガイド』(5回目印刷)40ページを参考に.
王先生の例です.
距離変換を編集するには、次の手順に従います.
私のプログラムが実行した結果(上記の変換ステップの逆順序):
前学期は王先生の『現代情報検索』の授業を選び、「辞書とフォールトトレランス検索」で編集距離について話し、編集距離を計算するにはダイナミックプランニングの方法を使っていて、面白いと感じて実現しました.
距離の定義を編集するには:
は、2つの文字列の間で、1つから別の文字列に移動するために必要な最小限の編集操作回数を指します.許可された編集操作には、1つの文字を別の文字に置き換え、1つの文字を挿入し、1つの文字を削除することが含まれます.
たとえばakittenをsittingに変換します.
kitten (a→ )
sitten (k→s)
sittin (e→i )
sitting (→g)
編集距離は4です.
次のコードを書きます.
1 //Written by fangpei
2 //Find the editdistance between two strings, and print the steps of change
3 #include<iostream>
4 #include<string>
5 using namespace std;
6
7 int Min_m(int m0, int m1, int m2);
8 void Print_step(int m[][40][4], string s1, string s2, int len1, int len2);
9
10 int main()
11 {
12 string s1, s2;
13 cin >> s1 >> s2;
14 int i, j;
15 int len1 = s1.length();
16 int len2 = s2.length();
17 int m[40][40][4] = {0};
18 for (i = 1; i <= len1; ++i) {
19 m[i][0][1] = i;
20 m[i][0][3] = i;
21 }
22 for (j = 1; j <= len2; ++j) {
23 m[0][j][2] = j;
24 m[0][j][3] = j;
25 }
26 for (i = 1; i <= len1; ++i) {
27 for (j = 1; j <= len2; ++j) {
28 if (s1[i-1] == s2[j-1])
29 m[i][j][0] = m[i-1][j-1][3]; //copy(cost 0)
30 else
31 m[i][j][0] = m[i-1][j-1][3] + 1; //replace(cost 1)
32 m[i][j][1] = m[i-1][j][3] + 1; //delete(cost 1)
33 m[i][j][2] = m[i][j-1][3] + 1; //insert(cost 1)
34 // the least cost until this step
35 m[i][j][3] = Min_m(m[i][j][0], m[i][j][1], m[i][j][2]);
36 }
37 }
38 cout << m[len1][len2][3] << endl;
39 Print_step(m, s1, s2, len1, len2);
40 return 0;
41 }
42
43 int Min_m(int m0, int m1, int m2) //find the min of m[i][j][*]
44 {
45 if (m0 > m1)
46 m0 = m1;
47 if (m0 > m2)
48 return m2;
49 return m0;
50 }
51
52 //print the change step in detail
53 void Print_step(int m[][40][4], string s1, string s2, int len1, int len2)
54 {
55 while (len1 !=0 || len2 != 0) {
56 //copy(cost 0)
57 if (m[len1][len2][3] == m[len1][len2][0] &&
58 m[len1][len2][0] == m[len1-1][len2-1][3]) {
59 cout << "copy '" << s1[len1-1] << "' to '" <<
60 s2[len2-1] << "', cost 0" << endl;
61 --len1;
62 --len2;
63 }
64 //replace(cost 1)
65 else if (m[len1][len2][3] == m[len1][len2][0] &&
66 m[len1][len2][0] == m[len1-1][len2-1][3] + 1) {
67 cout << "replace '" << s1[len1-1] << "' to '" <<
68 s2[len2-1] << "', cost 1" << endl;
69 --len1;
70 --len2;
71 }
72 //delete(cost 1)
73 else if (m[len1][len2][3] == m[len1][len2][1] && m[len1][len2][1] != 0) {
74 cout << "delete '" << s1[len1-1] << "' to " << " * , cost 1" << endl;
75 --len1;
76 }
77 //insert(cost 1)
78 else if (m[len1][len2][3] == m[len1][len2][2] && m[len1][len2][2] != 0) {
79 cout << "insert * to '" << s2[len2-1] << "', cost 1" << endl;
80 --len2;
81 }
82 }
83 }上のダイナミックプランニングアルゴリズムのステッププロセスはマトリクスで表現され,対応する文字を比較する.
最初の行と最初の列:
等差数列で増加します.(以下の例を参照)
残りの要素:
内部左上隅:
行列に対応する2文字が等しい場合は、左上隅要素の内部右下隅の数値の値を割り当てます.
行列に対応する2文字が等しくない場合は、左上隅要素の内部右下隅の値に1を加算します.
内部右上隅の数値:
上の要素の内部右下隅の数値に1を加算します.
内部左下の数値:
左方要素の内部右下隅の数値に1を加算します.
内部右下の数値:
内部の他の3つの数字の最小値を指定します.
最後に求めた行列の最右下の数字は2文字列の編集距離である.
詳しくは『情報検索ガイド』(5回目印刷)40ページを参考に.
王先生の例です.
距離変換を編集するには、次の手順に従います.
私のプログラムが実行した結果(上記の変換ステップの逆順序):