ラビン-カープ文字列検索アルゴリズム

ラビン-カープ文字列検索アルゴリズム（英: Rabin-Karp string search algorithm）は、マイケル・ラビンとリチャード・カープが開発した、ハッシュ関数を利用してテキストからパターン（サブ文字列）を探す文字列検索アルゴリズムの一種^[1]^[2]。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[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行目に注目し高速化している。

文字列検索のためのハッシュ関数使用

スキップの方法を洗練させるのではなく、ラビン-カープ法ではハッシュ関数を使って現在見ているテキストとパターンが同じかどうかのチェックを高速化する。ハッシュ関数は文字列を数値に変換する関数であり、その数値を「ハッシュ値」と呼ぶ。例えば、"hello" のハッシュ値は 5 などとなる。ラビン-カープ法では、文字列が等しいならハッシュ値も等しいという事実を利用する。従って、ここですべきことはサブ文字列のハッシュ値を計算し、同じハッシュ値を持つサブ文字列を見つけることである。

しかし、これには2つの問題がある。第一に文字列は様々なので、ハッシュ値を（16ビットとか32ビットとか）小さくしている限り、必ず同じハッシュ値を持つ異なった文字列が出現する。これはつまり、ハッシュ値が一致しても文字列が一致しない可能性があることを意味する。従って、文字列そのものの比較もしなければならず、文字列が長くなればなるほど時間がかかることになる。幸いハッシュ関数が妥当であれば通常の入力に対してこのような状況は滅多に発生せず、平均検索時間は小さく保たれる。

アルゴリズムは以下のようになる:

 1 function RabinKarp(string s[1..n], string sub[1..m])
 2     hsub := hash(sub[1..m])
 3     hs := hash(s[1..m])
 4     for i from 1 to n
 5         if hs = hsub
 6             if s[i..i+m-1] = sub
 7                 return i
 8         hs := hash(s[i+1..i+m])
 9     return not found

2行目、3行目、6行目、8行目は、Ω(m)の時間がかかる。しかし、2行目と3行目は1度しか実行されず、6行目はハッシュ値が一致したときだけ実行され何度も実行される性質のものではない。5行目は n 回実行されるが、定数時間しか要しない。従って問題となるのは8行目のみである。

もし単純にハッシュ値をサブ文字列 s[i+1..i+m] から計算したら、Ω(m)の時間を要し、これはループの繰り返しのたびに実行されるので、このアルゴリズムは Ω(mn) を要することになり、単純な検索アルゴリズムと何ら変わりない。これを解決する技法は、変数 hs が既に s[i..i+m-1] のハッシュ値を保持しているという点にある。これを使って次のハッシュ値を定数時間で計算できれば問題は解決する。

ここでは、いわゆる「ローリングハッシュ」を使用する。ローリングハッシュはこのような場合のために設計された特殊なハッシュ関数である。単純な例として、文字列を構成する全文字の値を加算するなどが考えられる。その場合、次のハッシュ値を計算する計算式は以下のようになり、定数時間で実行可能である:

 s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]

この単純な関数でも十分使えるが、6行目の実行回数が増える可能性がある。それを低減させるには次節で解説する洗練されたローリングハッシュ関数を利用しなければならない。

運が悪い場合やハッシュ関数が不適切な場合、6行目はほとんど n回実行されることもある。6行目の実行には Ω(m) の時間がかかるので、アルゴリズム全体として最悪の場合で Ω(mn) の時間を要することになる。

使用されるハッシュ関数

ラビン-カープ法の性能の鍵となるのは、テキストのサブ文字列の逐次的ハッシュ値計算の効率化にある。一般的な効率のよいローリングハッシュ関数は、大きな素数を基数として文字列を数値化するものである。例えば基数を 101、サブ文字列を "hi" とした場合、ハッシュ値は 104 × 101¹ + 105 × 101⁰ = 10609 となる（ASCIIコードで 'h' は 104、'i' は 105）。

技術的には数字（例えば 0-9）未満の基数を使うこともできるので、このアルゴリズムは非十進記数法での数を求めているだけとも言える。より詳細な議論はハッシュ関数を参照されたい。そのような表現の利点は、次のサブ文字列のハッシュ値を求めるのに文字列長に依存しない固定の操作回数で済む点である。

例えば、テキストとして "abracadabra" があり、3文字のパターンを検索する場合、"bra" のハッシュ値は "abr"（ひとつ前のサブ文字列）のハッシュ値から先頭文字 'a' の値 97 × 101² を減算し（'a' の ASCII コードは 97で、基数として 101 を使用）、基数をかけてから "bra" の最後の文字 'a' の値 97 × 101⁰ = 97 を加算する。サブ文字列が長ければ長いほど、このハッシュ法は他のハッシュ法よりも効果を発揮する。

理論的には他にも再計算が容易なアルゴリズムがある。例えば、各文字の ASCII コードを全てかけ合わせる。その場合、次のサブ文字列の計算をするには先頭文字のコードで割ってから最後の文字をかければよい。しかし、整数データ型のサイズは制限されているため、ハッシュ値をその範囲に収めるために合同式を使わなければならない。例えば単純に ASCII コードを加算するなどの方式では、ハッシュの衝突が頻発しアルゴリズムは低速になる。以上から、上述のハッシュ関数がラビン-カープに最も適している。

ラビン-カープと複数パターン検索

ラビン-カープは最悪の場合に非常に低速であるため、単一の文字列検索ではクヌース-モリス-プラット法やボイヤー-ムーア文字列検索アルゴリズムよりも劣っている。しかし、ラビン-カープは複数パターン検索の場合に使われることが多い。

すなわち、テキストから k 種類の固定長パターンのいずれかと一致する部分を検索する場合、ブルームフィルタや集合を使ってラビン-カープを修正し、ある文字列がパターンの集合のいずれかと一致するかどうかを調べるようにすることができる。

 function RabinKarpSet(string s[1..n], set of string subs, m) {
     set hsubs := emptySet
     for each sub in subs
         insert hash(sub[1..m]) into hsubs
     hs := hash(s[1..m])
     for i from 1 to n
         if hs ∈ hsubs
             if s[i..i+m-1] = a substring with hash hs
                 return i
         hs := hash(s[i+1..i+m])
     return not found
 }

全てのサブ文字列は固定長 m であるとする。

他のアルゴリズムは単一のパターンの検索を O(n) の時間で行うので、k 個のパターンの検索には O(n k) の時間がかかる。一方、修正したラビン-カープでは k 個のパターンの検索を O(n+k) の時間で実行することが期待できる。というのもサブ文字列のハッシュ値と全パターンのいずれかのハッシュ値との一致の検出は O(1) の時間で可能だからである。

参照

^ 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] 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.

[2] 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]

[2]