文字列探索のソースを表示

'''文字列探索''' (もじれつたんさく) とは、ある[[文字列]]の中から、別のある文字列を[[探索]]することである。[[テキストエディタ]]等で必須の機能であり、これまでさまざまな[[アルゴリズム]]が考案されている。

ここでいう文字列とは、ある定まった文字集合の要素を任意に並べた系列のことである。通常、文字は[[アルファベット]]等の言語に依拠した文字セットを指すことが多いが、[[生物情報学]]における染色体の塩基配列A, T, G, Cの4文字を対象とするもののように、特定の領域に特化した応用も行われている。

[[正規表現]]にマッチする文字列の探索、と類似した問題だが、正規表現で可能なパターンに比べ検索対象を絞ることで、より高速に探索するものとして研究されている（ユーザの使うプログラムでは、検索するパターンに応じて、アルゴリズムを切り替えるものもある）。正規表現による探索については[[正規表現]]の記事を参照のこと。

近年は、[[暗号化]]された文字列を復号せずに探索する'''秘匿検索'''、圧縮テキスト中の文字列探索の研究、多国語文字列のバイト列表現に対する探索の研究、なども行われている。

==各種アルゴリズム==
*[[クヌース-モリス-プラット法|クヌース-モリス-プラット法]]
*[[ボイヤー-ムーア文字列検索アルゴリズム|ボイヤー-ムーア法]]
*[[Quick Search法]] ボイヤー-ムーア法の亜種の一つで、さまざまな亜種のうちもっとも簡単で、かつ高速。
*[[エイホ-コラシック法]]
*[[ラビン-カープ文字列検索アルゴリズム|ラビン-カープ法]]
*[[Bitapアルゴリズム]]（shift-and, shift-orなどでも知られる）他[[並列計算#ビットレベルの並列性|Bit-parallel]]手法

==外部リンク==
*[http://www-igm.univ-mlv.fr/~lecroq/string/  EXACT STRING MATCHING ALGORITHMS]

{{DEFAULTSORT:もしれつたんさく}}
[[Category:検索]]
[[Category:検索アルゴリズム]]