CS 6.006 Lecture 9 Table Doubling, Karp-Rabin を見る

表記:

n: テーブルに入っている要素のサイズ

m: テーブルのサイズ

とする。

わかったこと

Table Shrinkingでは、縮めるタイミングとサイズの係数をずらすのが良い

テーブルの要素の追加・削除を繰り返し、n = m/2となったタイミングでテーブルを縮めるとする。このとき、m = m/2になるように縮めてしまうと、n = mとなり、

テーブルのサイズ = テーブル内の要素数

となる。ここで、次に要素が追加された場合、Table Doublingが起こり、m = 2mのサイズをもう一度作る。このとき、O(2m)の計算量がかかり、非効率。

そもそも、テーブルのサイズ = テーブル内の要素数はテーブルがギリギリの状態であり、よくない。これを避けるためには、 n=m/4となったタイミングでm = m/2 になるように縮めればよい。こうすると、ギリギリの状態をさけることができる。

Karp-Rabin アルゴリズム(Rolling Hash)では、modによる比較的単純なhashを使う

文字列検索のアルゴリズム。文字列 $s$ のなかから文字列 $t$ があるかどうかを返す時、以下のようなアルゴリズムを用いる。(参考: Rabin–Karp algorithm - Wikipedia)

function RabinKarp(string s[1..n], string pattern[1..m])
  hpattern := hash(pattern[1..m]);
  for i from 1 to n-m+1
    hs := hash(s[i..i+m-1])
    if hs = hpattern
      if s[i..i+m-1] = pattern[1..m]
        return i
  return not found

hashを毎回計算するときは、sha256のような複雑なものを使うと思っていたが、実際には、それだと計算量が高いので、文字列を数字に変換したものをつなげてmod p をとることでhashを計算する。ここで、pを素数にしておくと、inverse prime numberによるテクニックが使えて、大きな数に対しても比較的高速にmodが計算できる。 (参考: Modular multiplicative inverse - Wikipedia)

注意点 1.

上にのせたコードについて