パターン照合アルゴリズム

2004/05/01

東海大学理学部情報数理学科 松本哲志

現在私はプログラミングIの授業を受け持っています。 来週には文字列について講義を行う予定です。 そのとき、よく用いる例題としてパターン照合問題があります。 これは、長さNのテキストと長さMのパターンが与えられたとき、 テキストの中でそのパターンの現れる箇所があればその1つを示し、 もしなければないと答えるという問題です。
例えば、テキストとパターンをいかのように文字列とします。

テキスト:01011001011101010001010100010111010001010101001101010101000
パターン:010100010

このとき、パターンはテキスト中に現れているでしょうか?

まず、誰もが思いつくやり方は次のような力まかせだと思います。 テキストとパターンを以下のように並べます。

01011001011101010001010100010111010001010101001101010101000 
010100010

パターンの先頭から順番におなじ文字かどうかを判別します。 この場合4文字目までは おなじ文字ですが5文字目で異なっています。 そこで、次にパターンを1文字分だけずらします。

01011001011101010001010100010111010001010101001101010101000 
 010100010

また、パターンの先頭から順番におなじ文字かどうかを判別します。 今回は、1文字目から異なっています。 そこで、またパターンを1文字分だけずらします。 このような作業を繰り返すことによって、 パターンがテキスト中に存在する場合はその位置を見つけ出すことができます。

ですが、上述の方法では最悪の場合、約M×N回の文字比較が必要になります。 しかし、Boyer-Moore法と呼ばれる効率のよいパターン照合アルゴリズムでは、 M+Nの数倍程度の文字比較しか必要としません。 例えば、N=1000000、M=100とすると、 Boyer-Moore法の効率のよさがわかると思います。

情報数理学科の学生さんは是非ともBoyer-Moore法を調べて、 実際にプログラムを作ってみてください。