|
ラビン-カープ文字列検索アルゴリズム（）は、マイケル・ラビンとリチャード・カープが開発した、ハッシュ関数を利用してテキストからパターン（サブ文字列）を探す文字列検索アルゴリズムの一種〔Karp と Rabin のオリジナル論文: Karp, Richard M.; Rabin, Michael O. (1987年3月). "Efficient randomized pattern-matching algorithms ". ''IBM Journal of Research and Development'' 31 (2), 249-260.〕〔Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ''Introduction to Algorithms'', Second Edition. MIT Press and McGraw-Hill, 2001年. ISBN 0-262-03293-7. Section 32.2: The Rabin-Karp algorithm, pp.911–916.〕。1つのパターンの検索にはあまり用いられないが、理論的には重要であり、複数パターンの検索には効果的である。テキストの文字数が ''n''、パターンの文字数が ''m'' とした場合、平均および最良の実行時間はO(''n'')だが、ごくまれに最悪性能として O(''nm'')となる（広く用いられないのはそのため）。しかし、''k''個の文字列のいずれかにマッチする部分を検索するのに要する時間は ''k'' によらず平均で O(''n'') となるという独特の利点を持つ。以下、単にラビン-カープまたはラビン-カープ法と略記することがある。 ラビン-カープの単純な応用例として、盗作の検出がある。例えば、学生が『白鯨』に関する英語の論文を書いたとしよう。賢い教授は『白鯨』に関する様々な資料を集め、それらの全文を自動的に抽出するものとする。そこで、ラビン-カープを使えば学生の論文の任意の文がそれら資料からの丸写しかどうかを判定できる。微妙な修正で盗作を判定できなくなるのを防ぐには、大文字・小文字の別を無視し、句読点を無視すればよい。この場合の検索文字列数 ''k'' は膨大なので、単一文字列検索アルゴリズムは非現実的である。 == 文字列検索アルゴリズムの比較 == このアルゴリズムの対応する基本的問題は、''m'' 文字の固定のサブ文字列（パターン）を ''n'' 文字のテキスト内から検索することである。例えば "Hello sunshine in this vale of tears." という文から "sun" という文字列を探す。最も単純なアルゴリズムは全ての可能な位置からサブ文字列と比較するものである。 1 function NaiveSearch(''string'' s, ''string'' sub) 2 for i from 1 to n 3 for j from 1 to m 4 if s ≠ sub 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行目に注目し高速化している。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ラビン-カープ文字列検索アルゴリズム」の詳細全文を読む スポンサード リンク
|