文字列探索
出典: フリー百科事典『ウィキペディア(Wikipedia)』
文字列探索 (もじれつたんさく) とは、ある文字列の中から、別のある文字列を探索することである。テキストエディタ等で必須の機能であり、これまでさまざまなアルゴリズムが考案されている。
ここでいう文字列とは、ある定まった文字集合の要素を任意に並べた系列のことである。通常、文字はアルファベット等の言語に依拠した文字セットを指すことが多いが、生物情報学における染色体の塩基配列A, T, G, Cの4文字を対象とするもののように、特定の領域に特化した応用も行われている。
近年は、圧縮テキスト中の文字列探索の研究も行われている。
[編集] 各種アルゴリズム
- ボイヤー-ムーア法
- クヌース-モリス-プラット法
- Quick Search法 ボイヤー-ムーア法の亜種の一つで、さまざまな亜種のうちもっとも簡単で、かつ高速。
- ラビン-カープ法
- Shift-Or法
- エイホ-コラシック法
- Bit-parallel手法