文字列探索
 |
文字列探索 (もじれつたんさく) とは、ある文字列の中から、別の文字列（単一の文字列である場合もあれば、数千語から数万語以上の辞書の語彙である場合もある）を探索することである。前者の単一の文字列の探索は英文のテキストエディタ等で必須の機能であり（いわゆるスペルチェックと関連する）、後者は「かな漢字変換」等で必須の機能であるため、これまでさまざまなアルゴリズムが考案されている。
ここでいう文字列とは、ある定まった文字集合の要素を任意に並べた系列のことである。通常、文字はアルファベット等の言語に依拠した文字セットを指すことが多いが、生物情報学における染色体の塩基配列A, T, G, Cの4文字を対象とするもののように、特定の領域に特化した応用も行われている。
正規表現にマッチする文字列の探索、と類似した問題だが、正規表現で可能なパターンに比べ検索対象を絞ることで、より高速に探索するものとして研究されている（ユーザの使うプログラムでは、検索するパターンに応じて、アルゴリズムを切り替えるものもある）。正規表現による探索については正規表現の記事を参照のこと。
近年は、暗号化された文字列を復号せずに探索する秘匿検索、圧縮テキスト中の文字列探索の研究、多国語文字列のバイト列表現に対する探索の研究、なども行われている。
探索効率
[編集]欧米語のような、空白文字列で区切られている言語のテキストに関しては、効率のよいアルゴリズムが知られている。ところが日本語のように「どこからどこまでに対して辞書引きをするか」が不明確な場合、「あるバイト列に対し、不定長のバイト列に対して検索を行う」という作業が必要となる。
こうした要求に応えるものとしてトリプル配列法（および、トリプル配列法のスペースファクターを改善する目的で開発されたダブル配列法）があるが、ジップの法則によって、「頻出するバイト列にのみ対処すれば、出現頻度の少ないものに対しては、他の（実行効率の低い）アルゴリズムを用いても、システム全体のスループットには、ほとんど影響しない」という経験則があるため、トリプル配列法はあまり知られていない。
各種アルゴリズム
[編集]- クヌース-モリス-プラット法
- ボイヤー-ムーア法
- Quick Search法 ボイヤー-ムーア法の亜種の一つで、さまざまな亜種のうちもっとも簡単で、かつ高速。
- エイホ-コラシック法
- ラビン-カープ法
- Bitapアルゴリズム（shift-and, shift-orなどでも知られる）他Bit-parallel手法