スパムメールの判定や、文字列のあいまい検索等では、文字列間の違いを効率よく判定するアルゴリズムが必要。ここではその紹介。

「文字列間の距離 (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コンパイラだと十分大きなサイズに直して下さい。

/*
  引数: 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];
if (len1 == 0) return len2; if (len2 == 0) return len1;
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

Comments are closed.

Post Navigation