各種文字列検索アルゴリズムを実装したStringSearch
Johann Burkard氏が公開しているStringSearchは、高速な文字列検索アルゴリズムを実装したJava用ライブラリである。BNDM法や、BMH法とその派生、Bit-parallel手法といった複数のアルゴリズムをサポートしている点が特徴。いずれのアルゴリズムを利用する場合でも基本的な使い方は共通しているため、用途によって簡単に使い分けることができる。
Burkard氏によれば、StringSearchを利用すればjava.lang.Stringクラスによる文字列検索に比べて5倍から10倍程度の高速化が可能とのことである。ただし、この主張には異論も出ている。また、String.indexOf()メソッドなどで採用されているというnaiveアルゴリズム(シンプルだが低速)にしても、短い文字列を対象とした検索であれば十分に高速であることが知られているため、Stringクラスでも実用に足るとの指摘もある。
一方で、StringSearchでは一部でC++による実装を用いているため、純粋なJava実装よりも高速な動作が期待できるというメリットも存在する。いずれにしても、文字列検索では対象とする文字列やパターン文字列の特性によってアルゴリズムごとの性能が異なるため、選択肢が多いに越したことはない。StringSearchはJavaプログラムの文字列検索の可能性を広げてくれるライブラリと言うことができるだろう。大きな文字列を対象とした検索においては特に威力を発揮するはずだ。
StringSearchでサポートされるクラスとアルゴリズム
StringSearchはBurkard氏のサイトにて公開されている。ダウンロードしたファイルを解凍し、「stringsearch.jar」をクラスパスに含めて使用すればよい。「stringsearch-mini.jar」は機能を限定する代わりにファイルサイズを10KBに抑えた縮小版で、後述するBNDM、BNDMWildcards、BoyerMooreHorspoolRaitaのみ利用できるようになっている。また、stringsearch-mini.jarにはネイティブメソッドは使われない。
StringSearchでは、実装するアルゴリズムごとにそれぞれ次のようなクラスが用意されている。
BNDMクラス
- BNDM(Backward Nondeterministic Dawg Matching)アルゴリズムの実装
- もっとも高速なアルゴリズムのひとつだが、BoyerMooreHorspoolRaitaクラスやBoyerMooreHorspoolクラスよりも速くはならない
- 現状、サポートされるパターン文字列は32文字まで
BoyerMooreHorspoolクラス
- BM(Boyer-Moore)法の派生であるBMH(Boyer-Moore-Horspool)アルゴリズムの実装
- searchChars()メソッドおよびsearchString()メソッドがBoyerMooreHorspoolRaitaクラスに次いで高速
- ただし、パターン文字列が5文字未満の場合を除く
- パターン文字列が24文字以上の場合、String.indexOf()メソッドよりも5倍程度高速
- searchBytes()はBoyerMooreHorspoolRaitaクラスよりもわずかに高速
BoyerMooreHorspoolRaitaクラス
- BM法の派生であるBoyer-Moore-Horspool-Raitaアルゴリズムの実装
- searchChars()メソッドおよびsearchString()メソッドにおいてBoyerMooreHorspoolクラスよりもわずかに高速
BoyerMooreSundayクラス
- BM法の派生であるBoyer-Moore-Sundayアルゴリズムの実装
- 他のBM法派生アルゴリズムと同等の性能(アルゴリズム的には、BMHよりも検索効率はいいがメモリ消費量が多い)
ShiftOrクラス
- Bit-parallel手法の一種であるShift-Orアルゴリズムの実装
- String.indexOf()メソッドよりも遅い
- 文字クラスを使う場合(後述)に有用(それ以外の場合は他のクラスを使った方が速い)
- searchChars()メソッドはJVM上では非常に遅いので、できる限りsearchBytes()メソッドを使うべき
- 31文字以下の文字列のみサポート
BNDMWildcardsクラス
- ワイルドカードをサポートしたBNDMアルゴリズムの実装
- ShiftOrWildcardsクラスと比べて5倍程度高速
- 現状、サポートされるパターン文字列は32文字まで
ShiftOrWildcardsクラス
- ワイルドカードをサポートしたShift-Orアルゴリズムの実装
ShiftOrClassesクラス
- 文字クラスをサポートしたShift-Orアルゴリズムの実装
- 高度なパターンを使った検索が可能
ShiftOrMismatchesクラス
- ミスマッチ文字をサポートしたShift-Orアルゴリズムの実装
- 指定文字数まではパターンと一致しなくてもマッチ対象とする(この指定文字数を編集距離と呼ぶ)
- ShiftOrよりも遅い(将来のバージョンで改善予定)
- パターン文字列の長さは 31/(log2(k+1)) までとする(kは編集距離)
各クラスはcom.eaio.stringsearch.StringSearchを継承したもので、文字列検索のためのメソッドとしてsearchBytes()、searchChars()、searchString()を実装している。それぞれ、対象文字列およびパターン文字列をbyte配列、char配列、Stringオブジェクトとして指定するためのものである。
また各アルゴリズムは検索のための前処理を必要とするが、この前処理を行うためのメソッドとしてprocessBytes()、processChars()、processString()がある。1度きりの文字列検索であればこれらのメソッドを明示的に呼び出す必要はない。しかし同じパターン文字列で複数回の検索を実行する場合には、事前に実行し、結果を再利用した方が効率がいい。 次回は、StringSearchの具体的な使い方とコード例を紹介する。
Rustで有名アルゴリズムに挑戦 第17回 RustでHTTPサーバを実装してみよう