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

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

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

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

「ラビン-カープ文字列検索アルゴリズム」の記事における「文字列検索のためのハッシュ関数使用」の解説

スキップの方法を洗練させるのではなく、ラビン-カープ法ではハッシュ関数を使って現在見ているテキストとパターンが同じかどうかのチェックを高速化する。ハッシュ関数は文字列を数値に変換する関数であり、その数値を「ハッシュ値」と呼ぶ。例えば、"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) の時間を要することになる。