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

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

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

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

<関数名>
  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法による文字列照合アルゴリズム に比べると、実用上の性能で劣る。

Comments are closed.

Post Navigation