文字列検索アルゴリズムの比較

ウィキペディア小見出し辞書

文字列検索アルゴリズムの比較

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/04/10 17:28 UTC 版)

「ラビン-カープ文字列検索アルゴリズム」の記事における「文字列検索アルゴリズムの比較」の解説

このアルゴリズムの対応する基本的問題は、m 文字の固定のサブ文字列（パターン）を n 文字のテキスト内から検索することである。例えば "Hello sunshine in this vale of tears." という文から "sun" という文字列を探す。最も単純なアルゴリズムは全ての可能な位置からサブ文字列と比較するものである。 1 function NaiveSearch(string s[1..n], string sub[1..m]) 2 for i from 1 to n 3 for j from 1 to m 4 if s[i+j-1] ≠ sub[j] 5 jump to next iteration of outer loop 6 return i 7 return not found このアルゴリズムは多くの場合十分にうまく動作するが、場合によっては時間がかかりすぎる。例えばそれは、1000万個の "a" から構成されるテキストについて、10,000個の "a" に 1個の "b" が続いている文字列を検索する場合などで、最悪の場合O(mn)の時間がかかる。 クヌース-モリス-プラット法では、各文字を一度だけ調べるよう事前の計算を1回行うことで、Θ(n) の時間を実現している。ボイヤー-ムーア法では可能な限りスキップすることで繰り返し回数を減らし、文字列を調べる回数は最良の場合 n/m 回になる。ラビン-カープ法では、上記擬似コードの3行目から6行目に注目し高速化している。