スパムメールの判定や、文字列のあいまい検索等では、文字列間の違いを効率よく判定するアルゴリズムが必要。ここではその紹介。
「文字列間の距離 (String Distance) とは、2つの文字列間の違いを測る尺度。文字を挿入したり、削除したり、置き換えたりして、2つの文字列を等しくするまでの最小の操作の数でもある。」
例えば、computer と commuter。 pをmに置き換える(あるいは逆、mをpにする)だけで、全く同じ文字列になるので、二つの文字列間の距離は1となる。操作なしでは同等にならないので、1が最小操作数でもあるわけだ。
例えば、sport と sort。 左のsportから s を削除すれば、右のsortになるし、右のsortにpを挿入すると左になる。したがって、文字列間の距離は1となる。
<文字列間距離d の再帰的定義>
d("", "") = 0 ← 空文字列間の距離
d(s, "") = d("", s) = |s| ← 文字列の長さ(文字数)
d(s1+ch1, s2+ch2) ← ch1, ch2 はそれぞれの文字列の最後の文字
= min( d(s1, s2) + (if ch1=ch2 then 0 else 1),
← そのまま、または ch1とch2との置換
d(s1+ch1, s2) + 1, ← ch1 を s1 に挿入 (あるいは s2 から ch2削除)
d(s1, s2+ch2) + 1 ) ← ch1 を s1 から削除 (あるいは s2 に ch2挿入)
つまり、文字列 s1 と s2 との距離は、個々の文字を、等しい場合はそのまま、異なる場合は文字置換・挿入・削除(それぞれで距離を1つ縮める)操作の最小回数によって算出できる。
以下はそのC言語プログラム。作業用配列の大きさは動的に書いてあるが、古いCコンパイラだと十分大きなサイズに直して下さい。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
/* 引数: str1, str2、比較したい文字列2つ 関数値: str1とstr2との文字列間の距離。0以上の整数。 */ int string_distance(char *str1, char *str2) { int i, j; int len1 = strlen(str1); int len2 = strlen(str2); char M[len1+1][len2+1];<br> if (len1 == 0) return len2; if (len2 == 0) return len1;<br> for (j = 0; j <= len1; j++) M[j][0] = j; for (i = 0; i <= len2; i++) M[0][i] = i; for (j = 1; j <= len1; j++) { for (i = 1; i <= len2; i++) { int d, min; d = (str1[j-1] != str2[i-1]); /* or d = (str1[j-1] == str2[i-1]) ? 0 : 1; */ min = M[j-1][i ] + 1; if (min > M[j ][i-1] + 1) min = M[j ][i-1] + 1; if (min > M[j-1][i-1] + d) min = M[j-1][i-1] + d; M[j][i] = min; } } return M[len1][len2]; } |
計算量は明らかに O(|s1|*|s2|)。 s1とs2の長さが等しく N と考えるなら、 O(N2) となる。
この文字列間距離はかならず実現できる操作(文字の挿入・削除・置換のみ)を表すもの。実際の操作では、以下のようなアルゴリズムを考えることもできる(最終結果と最小手間数が判っているので、意味のない操作だが、プログラムをつくる練習材料にはなる)。ほかには、再帰的プログラムによる方法もある。
基準・比較対象(target) viagra ← s1
操作したい文字列 v1a_gra ← s2
先頭からの各文字 s1[i] と s2[i] に対し、
s1[i] と s2[i] が等しい場合、操作しない
異なる場合、挿入・削除・置換の操作で得られた3つの文字列について、それぞれのs1との文字列間距離を計算し、最小なる操作を選べばよい。
s1、s2 文字列の長さをNとすると、それぞれの文字について、文字列間距離を計算する手間がかかるので、全体的に計算量はO(N3) である。
<練習問題>
164 String Computer
526 String Distance and Transform Process