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

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

計算量は明らかに 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