|
|
アルゴリズム ダウンロード ニュース サービス |
| KMP法（一方向逐次検索 単一パターン） |
|
KMPは考案者 Knuth、Morris、Pratt ３氏の頭文字を表す。
この方法でも、テキストを先頭から1文字づつ見ていくという点では単純な方法と変わらない。キモとなる点は、不一致が起きた時点で得ている情報によりシフト幅を変えるという点だ。単純な方法では1文字づつしかずらすことができなかったが、このKMP法では最大で不一致が起きた時点で比較した長さ分だけずらすことができる。 
具体的に図を見てみよう。テキストとパターンがある文字数だけ一致した後、不一致を検出したとしよう。単純な方法ではまさしく単純に1文字だけずらしてまた同じことを繰り返した。しかし、ここまでは一致しているという情報を持っているのだから、それを何とかうまく使って1文字より多くずらす(シフトさせる)ことができる。その方法は、一致した部分から先頭1文字を削った文字列のSuffix(接尾辞)とパターンのPrefix(接頭辞)で一致する最長のものをそろえることだ。 先頭1文字を削るのは、シフト幅を1以上にするためだ。また、検出もれをなくす為に最長のものを選んでいる。 次の表は、abbabbababに対するシフト幅を示したものだ。
|