文字列探索 (もじれつたんさく) とは？
状態:終了後再開
閲覧数:1,779
投稿日:2016-11-09
更新日:2018-03-11
「ある文字列」の中から、別の「ある文字列」を探索すること
・「テキスト(文字列)S」から「単語Wで指定されたパターン」が出現する場所を見つける操作
・「文字の並び」が重要
文字列とは？
・「ある定まった文字集合の要素」を任意に並べた系列のこと
パターン
・「探したい文字の並び」のこと
・単語
・W
テキスト
・「検索される文字列」のこと
・S
Morris-Pratt algorithm
クヌース–モリス–プラット法
ボイヤー-ムーア法
Quick Search法 ボイヤー-ムーア法の亜種の一つで、さまざまな亜種のうちもっとも簡単で、かつ高速。
エイホ-コラシック法
ラビン-カープ法
Bitapアルゴリズム（shift-and, shift-orなどでも知られる）
Bit-parallel手法
・終了後→探索アルゴリズム
・「テキスト(文字列)S」から「単語Wで指定されたパターン」が出現する場所を見つける操作
・「文字の並び」が重要
文字列とは？
・「ある定まった文字集合の要素」を任意に並べた系列のこと
パターン
・「探したい文字の並び」のこと
・単語
・W
テキスト
・「検索される文字列」のこと
・S
各種アルゴリズム
Morris-Pratt algorithm
クヌース–モリス–プラット法
ボイヤー-ムーア法
Quick Search法 ボイヤー-ムーア法の亜種の一つで、さまざまな亜種のうちもっとも簡単で、かつ高速。
エイホ-コラシック法
ラビン-カープ法
Bitapアルゴリズム（shift-and, shift-orなどでも知られる）
Bit-parallel手法
・終了後→探索アルゴリズム