Category Archives: C言語・文字列照合

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

「文字列間の距離 (String Distance) とは、２つの文字列間の違いを測る尺度。文字を挿入したり、削除したり、置き換えたりして、２つの文字列を等しくするまでの最小の操作の数でもある。」

例えば、computer と commuter。 pをmに置き換える（あるいは逆、mをpにする）だけで、全く同じ文字列になるので、二つの文字列間の距離は１となる。操作なしでは同等にならないので、１が最小操作数でもあるわけだ。

例えば、sport と sort。　左のsportから s を削除すれば、右のsortになるし、右のsortにpを挿入すると左になる。したがって、文字列間の距離は１となる。

＜文字列間距離ｄ の再帰的定義＞
　　　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 との距離は、個々の文字を、等しい場合はそのまま、異なる場合は文字置換・挿入・削除（それぞれで距離を１つ縮める）操作の最小回数によって算出できる。

以下はそのC言語プログラム。作業用配列の大きさは動的に書いてあるが、古いCコンパイラだと十分大きなサイズに直して下さい。

計算量は明らかに O(|s1|*|s2|)。 s1とs2の長さが等しく N と考えるなら、 O(N²) となる。

この文字列間距離はかならず実現できる操作（文字の挿入・削除・置換のみ）を表すもの。実際の操作では、以下のようなアルゴリズムを考えることもできる（最終結果と最小手間数が判っているので、意味のない操作だが、プログラムをつくる練習材料にはなる）。ほかには、再帰的プログラムによる方法もある。

　　基準・比較対象（target）　　　viagra　　　← s1
　　操作したい文字列　　　　　　v1a_gra　　　← s2

先頭からの各文字 s1[i] と s2[i] に対し、
　　s1[i] と s2[i] が等しい場合、操作しない
　　　　　　　　　　　　 異なる場合、挿入・削除・置換の操作で得られた３つの文字列について、それぞれのs1との文字列間距離を計算し、最小なる操作を選べばよい。

s1、s2 文字列の長さをNとすると、それぞれの文字について、文字列間距離を計算する手間がかかるので、全体的に計算量はO（N³） である。

＜練習問題＞
　164 String Computer
　526 String Distance and Transform Process

正規表現 (regular expression)、表現自体はあれに想像してしまうが、情報科学の分野では古くから確立した数少ない学問のひとつ。大学にその専攻分野では必ずオートマトンとかいう授業がある。しかし、理解した学生はどれぐらいいるんだろう。複雑な証明に圧倒されてしまうかもしれないし、教える側の先生だって完全に理解してないかもしれない。

Unix のコマンドに古くから実装されてきたが、世間に広く知らしめたのはPerl のお陰だろう。いまでは正規表現が至る所に活用されている。

正規表現といっても、いろいろな定義があって、本アルゴリズムでは、照合パターンとしてつぎのようなものを受けつける。

より形式的に説明すると以下のようになる。ただし、PとQはいずれも正規表現とする。

連結と選択では、連結の方が優先度が高く、閉包はさらにそれよりも高い。

正規表現が与えられると、本アルゴリズムではそれをε遷移を含む非決定性オートマトン（NonDeterministic Automaton）に変換した上で、その非決定性オートマトンをシミュレートしながらテキストとの照合を行う。

より高速に照合を行いたいときは、非決定性オートマトンをさらにそれと等価な決定性オートマトンに変換することが考えられる。

＜関数名＞
　　regMatch　正規表現による文字列照合アルゴリズム
　　regNew　　文字列照合のための非決定性オートマトンの作成

＜形式＞
　　文字列照合
　　　　char *regMatch(char *text, int len, PAIR *nda);

　　非決定性オートマトンの作成
　　　　PAIR *regNew(char *pattern, int patlen);

＜引数＞
　　文字列照合関数において
　　　　text　　（入力）テキスト
　　　　len　　（入力）テキストの長さ
　　　　nda　　（入力）照合パターンに対応した非決定性オートマトン

　　非決定性オートマトンの作成関数において
　　　　pattern　（入力）照合パターン
　　　　patlen　（入力）照合パターンの長さ

＜関数値＞
　　文字列照合関数について
　　　　照合パターンがテキストから見つかった場合はそのポインタ、
　　　　見つからなかった場合は 0 (NULL)。

　　非決定性オートマトンの作成関数について
　　　　作成した非決定性オートマトン。作成できなかったときは 0 (NULL)。

＜注意事項＞
　　regNew() を呼び出して非決定性オートマトンを作成した後、regMatch() を利用して文字列照合を行う。

＜用例＞

＜ヘッダファイル＞
　　regMatch.h

＜関数本体＞
　　regMatch.c

＜説明＞

Boyer-Mooreのアルゴリズム、略してBMアルゴリズムは、 KMPアルゴリズムよりもさらに高速。照合パターンがある程度以上（普通５文字以上くらい）の長さをもつ場合には、最も速い文字列照合アルゴリズムだと言われている。KMPアルゴリズムと同様、計算量は最悪の場合でも O(n) 。

BMアルゴリズムの長所は、テキスト中の文字の大部分を調べずにすむ可能性があること。素朴なアルゴリズムやKMPアルゴリズムでは、テキストの中の文字をそれぞれ１回は調べなければならない。比較は最低でも n 回になる。これに対して、BMアルゴリズムでは n/m 個（nはテキストの長さ、mは照合パターンの長さ）の文字とだけ比較すればよい。これによって、特に照合パターンが長いときに、計算時間の大幅な短縮が期待できる。

この特徴から、BMアルゴリズムは、実用上きわめて重要なアルゴリズムと見なされている。テキスト探索の使用頻度が高いだけにその価値は大きい。

BMアルゴリズムも、素朴なアルゴリズムと同様、テキストを左から順に調べていく。しかし、いったんテキスト上の位置がきまったら、照合パターンについては、逆に右から左に向かって調べる。照合パターンを逆向きに調べることがBMアルゴリズムの要点なのだ。もちろん、照合を進めるにあたっては、それ以前に行った比較の結果として得られた情報をできるだけ活用して、比較の回数を減らすように努める。これはKMPアルゴリズムと同様。

＜関数名＞
　　bmMatch Boyer-Mooreによる文字列照合アルゴリズム
　　bmSkip シフト表１の作成
　　bmNext シフト表２の作成

＜形式＞
　　文字列照合
　　　　char *bmMatch(char *text, int len, char *pattern,
　　　　　　　　　　　int patlen, int *skip, int *next);

　　シフト表１の作成
　　　　int bmSkip(int *skip, int slen, char *pattern, int patlen);

　　シフト表２の作成
　　　　int bmNext(int *next, int nlen, char *pattern, int patlen);

＜引数＞
　　文字列照合関数において
　　　　text　　　（入力）テキスト
　　　　len　　　（入力）テキストの長さ
　　　　pattern　（入力）照合パターン
　　　　patlen　　（入力）照合パターンの長さ
　　　　skip　　　（入力）シフト表１
　　　　next　　　（入力）シフト表２

　　シフト表１の作成関数において
　　　　skip　　　（入出力）シフト表１
　　　　slen　　　（入力）　skip配列の長さ
　　　　pattern　（入力）　照合パターン
　　　　patlen　　（入力）　照合パターンの長さ

　　シフト表２の作成関数において
　　　　next　　　（入出力）シフト表２
　　　　nlen　　　（入力）　next配列の長さ
　　　　pattern　（入力）　照合パターン
　　　　patlen　　（入力）　照合パターンの長さ

＜関数値＞
　　文字列照合関数について
　　　　照合パターンがテキストから見つかった場合はそのポインタ、
　　　　見つからなかった場合は 0 (NULL)。

　　シフト表１の作成関数について
　　　　シフト表１を正常に作成できた場合は 0、失敗した場合は -1。

　　シフト表２の作成関数について
　　　　シフト表２を正常に作成できた場合は 0、失敗した場合は -1。

＜注意事項＞
　　bmSkip()とbmNext() を呼び出してシフト表を作成した後、文字列照合関数 bmMatch() を利用すること。
　　なお、漢字かな交じりの文字列照合にはこの関数では未対応。ご自分で修正すること。

＜用例＞

＜関数本体＞
　　bmMatch.c

＜説明＞

テキストに現れる、長さ m （mは照合パターンの長さ）の文字列すべてに対してハッシュ関数の値を計算し、その値が照合パターンのそれと一致するかどうかを調べることで文字列照合を行う方法。ラビンとカープ氏による。ハッシュ関数に h(k) = k mod q を使う。ここに、 q（ハッシュ表の大きさ）は大きな素数。ハッシュ表は実際に用意する必要がないことから q として非常に大きな素数を選ぶことができる。

この方法ではまず照合パターンのハッシュ関数値 h1 を、つぎにテキスト最初の m 文字分のハッシュ関数値 h2 を計算する。そのあとテキスト上の照合開始位置を右にずらしながら、ハッシュ関数値を漸化式によって計算し、その値と h1 との比較を繰り返す。

＜関数名＞
　　rkMatch ラビン-カープによる文字列照合アルゴリズム
　　rkHash 照合パターンのハッシュ関数値

＜形式＞
　　文字列照合
　　　　char *rkMatch(char *text, int len, int patlen,
　　　　　　　　unsigned long patHash, unsigned long dm);

　　照合パターンのハッシュ関数値
　　　　unsigned long rkHash(unsigned long *dm, char *pattern, int patlen);

＜引数＞
　　文字列照合関数において
　　　　text　　　（入力） テキスト
　　　　len　　　　（入力） テキストの長さ
　　　　patlen　　（入力） 照合パターンの長さ
　　　　patHash　（入力） 照合パターンのハッシュ関数値
　　　　dm　　　　（入力） 256m-1 % の値

　　照合パターンのハッシュ関数値の関数において
　　　　dm　　　　（入出力） 256m-1 % の値
　　　　pattern　（入力） 照合パターン
　　　　patlen　　（入力） 照合パターンの長さ

＜関数値＞
　　文字列照合関数について
　　　　照合パターンがテキストから見つかった場合はそのポインタ、
　　　　見つからなかった場合は 0 (NULL)。

　　照合パターンのハッシュ関数値の関数において
　　　　照合パターンのハッシュ関数値

＜注意事項＞
　　rkPattern() を呼び出して照合パターンのハッシュ関数値を算出した後、
　　文字列照合関数 rkMatch() を利用すること。

＜用例＞

＜関数本体＞
　　rkMatch.c

＜説明＞
　　この方法の計算量 O(m+n) 。違う文字列が同じハッシュ関数値をもつことは理論的には否定できないが、大きな素数 q を選べば実用上その問題を無視してよい。

前回の素朴なアルゴリズムでも、実用的に見てそれほどの問題点はないが、最悪の場合の計算量はmnに比例するところに改良の余地が残っている。計算量がこれほどになるのは、ある位置にパターンをおいて比較した際に得られる情報を十分活用していないためだ。

文字列照合の速度を上げるには、一致する、または一致しないことが既にわかっている場合には、無駄な比較をできるだけ避けないといけない。

そのために、照合を始める前に準備をしておくことが必要。すなわち、k 文字だけ一致した後で不一致が見つかったときに、テキストのどの文字とパターンのどの文字の比較から照合を続ければよいかをあらかじめ調べておく。不一致となった位置から左側 k文字がわかっていることを利用して、無駄な比較を避けるように設定するのだ。これを表の形で記録する。

なお、KMPは考案者 Knuth、Morris、Pratt ３氏の頭文字を表す。

＜関数名＞
　　kmpMatch Knuth-Morris-Prattによる文字列照合アルゴリズム
　　kmpNext 文字列照合のためのシフト表の作成

＜形式＞
　　文字列照合
　　char *kmpMatch(char *text, int len, char *pattern,
int patlen, int *next);
　　シフト表の作成
　　int kmpNext(int *next, int nlen, char *pattern, int patlen);

＜引数＞
　　文字列照合関数において
　　　　text　　　（入力） テキスト
　　　　len　　　　（入力） テキストの長さ
　　　　pattern　（入力） 照合パターン
　　　　patlen　　（入力） 照合パターンの長さ
　　　　next　　　（入力） シフト表

　　シフト表の作成関数において
　　　　next　　　（入出力） シフト表
　　　　nlen　　　（入力）　next配列の長さ
　　　　pattern　（入力）　照合パターン
　　　　patlen　　（入力）　照合パターンの長さ

＜関数値＞
　　文字列照合関数について
　　　　照合パターンがテキストから見つかった場合はそのポインタ、
　　　　見つからなかった場合は 0 (NULL)。

　　シフト表の作成関数について
　　　　シフト表を正常に作成できた場合は 0、失敗した場合は -1。

＜用例＞

＜関数本体＞
　　kmpMatch-test.c

＜説明＞
　　KMPアルゴリズムの比較回数は、最大 2n 回。つまり計算量は O(n) 。n はテキストの長さ。
　　しかし、つぎのBM法による文字列照合アルゴリズム に比べると、実用上の性能で劣る。

文字列の照合は、文字列の探索ともいう。「テキスト」と呼ばれる文字列の中に、「パターン」と呼ばれる文字列に一致する部分があるかどうかを調べる問題。そのような部分が見つかった場合には、さらにその場所を答える。

テキスト・エディタにおける探索コマンドやデータベースにおける検索などに使われ、使用頻度の多い操作だろう。いまの時代になって、WWWページの全文検索にも利用される。

ここで紹介する素朴法とは、テキストの先頭に、ます照合パターンを重ね、一致するかどうかを比較していく。一致しなければ重ねる位置を後一文字にずらしてまた比較、テキストの最後になるまで繰り返す、というもっとも基本的な方法。

なお、照合対象は漢字でも構わないが、漢字の場合、2文字（＝全角1文字）分ずらすほうが意味的に正しいので、多少の修正を加えるといいかもしれない。

＜関数名＞
　　naiveMatch 　素朴法による文字列照合

＜形式＞
　　char *naiveMatch(char *text, int len, char *pattern, int patlen);

＜引数＞
　　text　　　（入力） テキスト
　　len　　　 （入力） テキストの長さ
　　pattern　（入力） 照合パターン
　　patlen　　（入力） 照合パターンの長さ

＜関数値＞
　　照合パターンがテキストから見つかった場合はそのポインタ、
　　見つからなかった場合は 0 (NULL)。

＜用例＞

＜関数本体＞
　　naiveMatch.c

＜説明＞
　　判りやすい照合方法ではあるが、計算時間は、最悪 O(mn) になる。 m、nはそれぞれテキスト、照合パターンの長さ。
　　より速い照合アルゴリズムについてはこれから紹介する。