使用されるハッシュ関数
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/04/10 17:28 UTC 版)
「ラビン-カープ文字列検索アルゴリズム」の記事における「使用されるハッシュ関数」の解説
ラビン-カープ法の性能の鍵となるのは、テキストのサブ文字列の逐次的ハッシュ値計算の効率化にある。一般的な効率のよいローリングハッシュ関数は、大きな素数を基数として文字列を数値化するものである。例えば基数を 101、サブ文字列を "hi" とした場合、ハッシュ値は 104 × 1011 + 105 × 1010 = 10609 となる（ASCIIコードで 'h' は 104、'i' は 105）。 技術的には数字（例えば 0-9）未満の基数を使うこともできるので、このアルゴリズムは非十進記数法での数を求めているだけとも言える。より詳細な議論はハッシュ関数を参照されたい。そのような表現の利点は、次のサブ文字列のハッシュ値を求めるのに文字列長に依存しない固定の操作回数で済む点である。 例えば、テキストとして "abracadabra" があり、3文字のパターンを検索する場合、"bra" のハッシュ値は "abr"（ひとつ前のサブ文字列）のハッシュ値から先頭文字 'a' の値 97 × 1012 を減算し（'a' の ASCII コードは 97で、基数として 101 を使用）、基数をかけてから "bra" の最後の文字 'a' の値 97 × 1010 = 97 を加算する。サブ文字列が長ければ長いほど、このハッシュ法は他のハッシュ法よりも効果を発揮する。 理論的には他にも再計算が容易なアルゴリズムがある。例えば、各文字の ASCII コードを全てかけ合わせる。その場合、次のサブ文字列の計算をするには先頭文字のコードで割ってから最後の文字をかければよい。しかし、整数データ型のサイズは制限されているため、ハッシュ値をその範囲に収めるために合同式を使わなければならない。例えば単純に ASCII コードを加算するなどの方式では、ハッシュの衝突が頻発しアルゴリズムは低速になる。以上から、上述のハッシュ関数がラビン-カープに最も適している。
※この「使用されるハッシュ関数」の解説は、「ラビン-カープ文字列検索アルゴリズム」の解説の一部です。
「使用されるハッシュ関数」を含む「ラビン-カープ文字列検索アルゴリズム」の記事については、「ラビン-カープ文字列検索アルゴリズム」の概要を参照ください。
- 使用されるハッシュ関数のページへのリンク
