文字列検索アルゴリズムの覚え書き

Programming

マイコミジャーナルの連載記事で、「StringSearch」という文字列検索のためのJavaライブラリを紹介しました。
攻略! ツール・ド・プログラミング (44) 高速な文字列検索を実現するJavaライブラリ「StringSearch」 | マイナビニュース

その補足も兼ねて、記事中に出てくる文字列検索アルゴリズムについて少しまとめてみました。細部を省略した大雑把な説明なので厳密な解説ではありませんが、参考までに。

naiveアルゴリズム
対象の文字列とパターン文字列を先頭から順番に比べていき、マッチしなかったら1文字進めてまた最初から比べるという手法です。
java.lang.StringのindexOf()メソッドなどはこの実装だそうです。

Knuth Morris Pattアルゴリズム（KMPアルゴリズム）
マッチに失敗した場合に、比較するスタート位置を1文字ずつ進めるではなく、何文字かまとめて進めることで比較回数を減らす手法です。
対象の文字列とパターン文字列を先頭から順番に比べていき、マッチしなかった文字が何文字目かによって進める文字数を決定します。何文字目で失敗したときに何文字先まで進められるかは、あらかじめ計算して求めておきます。

Boyer-Mooreアルゴリズム（BMアルゴリズム）
まとめて読み飛ばすという点ではKMP法と同じ発想ですが、比較をパターン文字列の後ろから行うという点が大きく異なります。
「後ろから何文字目でマッチに失敗したか」を調べ、対象文字列のその位置にある文字と、パターン文字列中の文字が一致するように、比較のスタート地点を進めます。下図の1回目の比較では後ろから3文字目が一致していないので、その位置の'd'を基準とします。パターン中に'd'がある場合には、その'd'が重なる位置まで進めます。'd'が複数ある場合には、一番後ろのものを合わせます。'd'がひとつも無い場合には、比較済みの文字をすべて飛ばし、次の文字まで進めます。
厳密には進める幅の計算に2通りのやり方があり、それを比較して進める量の大きい方を採用します。この部分の関数は、単純に実装すると遅いため工夫が必要です。


Boyer-Moore-Horspoolアルゴリズム（BMH法）
BMアルゴリズムの派生版で、マッチに失敗した文字が何文字目であろうとも、進める幅の計算はパターン文字列の一番最後の位置を基準に行います。
下図の例では、1回目で5文字目までの比較が終わっており、対象文字列のその位置にある文字は'd'なので、パターン文字列中の'd'が一致する位置までスタート地点を進めます。2つ以上ある場合や、存在しない場合の処理はBMアルゴリズムと同様です。
進める幅がBMアルゴリズムよりも大きいため、比較回数を少なくすることができます。


Boyer-Moore-Horspool-Raitaアルゴリズム
すみません、このアルゴリズムは知りませんでした。
BMHアルゴリズムをチューニングして速度を向上させたもののようで、以下の論文を元に実装されているようです。
http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol22/issue10/spe787tr.pdf

Boyer-Moore-Sundayアルゴリズム（Sunday法）
BMアルゴリズムの派生版ですが、文字列の後ろから比較するのではなく、任意の順番で比較するというものです。出現頻度が高い文字などから優先して比較することで比較回数を抑えることができます。
進める幅は、パターン文字列の最後の位置ではなく、そのさらに次の位置を基準にして決定します。下図の例では、1回目で5文字目までの比較が終わっており、対象文字列のその位置にある文字は'c'なので、パターン文字列中の'd'が一致する位置までスタート地点を進めます。
この方法は、統計的にBMH法よりも進める幅が大きくなる傾向があるそうです。ただし、BMH法よりもメモリ消費量が多く、進める幅を計算する手間も増えます。


Backward Dawg Matchingアルゴリズム（BDMアルゴリズム）
基本はBMアルゴリズムと同様ですが、部分文字列（ファクター）が一致しているかどうかを調べることで、パターンとの一致を検出します。
下図の例では、1回目の比較で末尾の'ab'が一致しているため、パターン文字列中の'ab'が合う位置までスタート位置を進めます。2回目の比較では末尾の1文字目からすでに一致していないません。この場合は、最後の2文字がパターンの部分文字列と一致するかどうかを調べます。一致するものが無い場合は、その次の位置である9文字目まで進めます。3回目の比較のように一致する部分文字列がある場合には、その位置が合うように進めます。
部分文字列であるかどうかの判定にはSuffix Automatonと呼ばれるオートマトンを使用します。また、本当は最後の文字がプレフィックスであるかどうかも調べなければならないのですが、これもSuffix Automatonによってわかります。

Backward Nondeterministic Dawg Matchingアルゴリズム（BNDMアルゴリズム）
BDMアルゴリズムと同様ですが、非決定性（Nondeterministic）のSuffix Automatonを利用します。

Shift-Or法は非決定性有限オートマトンを利用した手法ですが、解説が大変なので省略します。