2019年6月26日水曜日

ローリングハッシュの法と基数の選び方

ローリングハッシュの法と基数の選び方

a0a1...an1a_0a_1...a_{n-1}に対するハッシュ値をmod  M\mod M
H(a0a1...an1):=a0bn1+a1bn2+...+an2b+an1()H(a_0a_1...a_{n-1}) := a_0b^{n-1} + a_1b^{n-2} + ... + a_{n-2}b + a_{n-1} \qquad (*)

と定める。いわゆるローリングハッシュだが、MMbbをどう選べばよいかわからない。bbは原始根のほうがいいのかそれとも関係ないのかと悩んでいて、ググったら上の資料を見つけた。値の選び方やハッシュの衝突について疑問に思っていたことがだいたい書いてあって助かった。

上の資料では基数の掛け方が()(*)と逆になっているのだが、自分は()(*)で扱っているのでこちらに直して要点をメモしておく。1

MMは大きいほうが安全

ハッシュ値は0,1,...,M10, 1, ..., M-1のいずれかになるので、衝突を避けるためには可能な限り大きいほうがよい。これは当然。

M<232M < 2^{32}だと計算がしやすい

Hk:=H(a0a1...ak1)H_k := H(a_0a_1...a_{k-1})bkb^kのテーブルをそれぞれ作ってあれば、部分列alal+1...ar1a_la_{l+1}...a_{r-1}のハッシュ値は

HrHlbrlH_r-H_l \cdot b^{r-l}

で求まる。普通に計算すると、乗算してmod  \mod{}をとって可算してmod  \mod{}を取ることになるが、(M1)2+(M1)<264(M-1)^2+(M-1) < 2^{64}を満たしていれば乗算して可算しても符号無し64ビット整数の範囲に収まっているので、最後に1回だけmod  \mod{}を取ればよい。(M1)2+(M1)=M(M1)(M-1)^2+(M-1) = M(M-1)なのでこれは特殊な制約というわけではなく、単にM232M \le 2^{32}であればよい。

上の制約と併せると、MMは符号無し32ビット整数のできるだけ大きいものがよいということになる。(サイズが足りなければ複数のMMでハッシュ値を求めて組み合わせればよい。)

bb, b2b^2, b3b^3, …の周期は長いほうが安全

bibi+tb^i \equiv b^{i+t}が成立すると、与えられたn>i+tn > i+tに対して、長さnnの列で衝突するものが構成できる:
0..(t)..0a1a2...anit0..(i)..00..(t\text{個})..0a_1a_2...a_{n-i-t}0..(i\text{個})..0a1a2...anit0..(i+t)..0a_1a_2...a_{n-i-t}0..(i+t\text{個})..0

これはMMに依存しない衝突なので、そこそこ危険に見える。したがってbb, b2b^2, b3b^3, …の周期はある程度長いほうがよい。周期が最長になるのは、bbが法MMに対する原始根である場合で、このときbb, b2b^2, … , bM1b^{M-1}はすべて異なる。

上の制約と併せると、MM2322^{32}未満の素数から大きいものを選んで、bbはその原始根を選べばよさそう。2

bbはアルファベットのサイズより大きいほうが安全

bbが文字の種類数より小さいと、

H(10)=H(0b)H(10) = H(0b)

という自明な衝突が発生する。bbを大きくするぶんには問題はないはずなので、大きい原始根を選べばよさそう。

想定するアルファベットのサイズとして、競プロでよくある上限の10910^9を採用することにすると、最終的なMMbbの選び方は次のようになった:

2322^{32}未満の素数で10910^9より大きい原始根を持つものを(例えば)10001000個集める。コンパイル時または実行時にMMを無作為に選んで、法MM10910^9より大きい原始根をbbとして採用する。必要ならMMを2つ、3つ、…選んで64ビット、96ビット、…のハッシュ値として使えばよい。

というわけで、2322^{32}未満の素数と大きな原始根(generator)のリストを作った。[109+1,M)[10^9+1, M)から無作為に整数を選んで、原始根であれば採用している。

言語によっては整数の基本型が符号付き63ビットになっていて、この場合M<232M < 2^{32}の代わりにM<231M < 2^{31}から選んだほうが都合がよいかもしれない。2312^{31}未満の素数と大きな原始根のリストも作った。


  1. 自分の実装(Common Lisp)はこれで、ei1333さんのやつを参考にした。 ↩︎

  2. MMは必ずしも素数でなくても原始根を持つが、素数がいちばん考えやすいのでそうする。 ↩︎

ARC 098 E - Range Minimum Queries

ARC 098 E - Range Minimum Queries

数列A1,A2,...A_1, A_2,...を昇順に並べ替えたものをA1A2...A&#x27;_1 \le A&#x27;_2 \le ...とする。最大値-最小値をすべて試すなら、だいたい次のようになるはずだ。

  1. 数列(Ai)(A_i)の小さいほうからQQ個取り除いて最大値-最小値を求める。
  2. A1A&#x27;_1を残したままにしつつ(Ai)(A_i)からできるだけ小さい数を取り除いてゆき、QQ個取り除けたら最大値-最小値を求める。
  3. A1,A2A&#x27;_1, A&#x27;_2を残したままにしつつ(Ai)(A_i)からできるだけ小さい数を取り除いてゆき、QQ個取り除けたら最大値-最小値を求める。

これは高々O(N){\mathcal O}(N)ステップで済むので、ひとつひとつのステップがO(N){\mathcal O}(N)O(NlogN){\mathcal O}(N \log N)くらいで実行できればよい。

小さい数を取り除いていく具体的な手順を与えるために、上のステップ3について考えてみる。A1=Ap,A2=AqA&#x27;_1 = A_p, A&#x27;_2 = A_qとする。

A1,A2,...,Ap1  Ap+1,Ap+2,...,Aq1  Aq+1,Aq+2,...,ANA_1, A_2, ..., A_{p-1} \ | \ A_{p+1}, A_{p+2}, ..., A_{q-1} \ | \ A_{q+1}, A_{q+2},..., A_N

ApA_p, AqA_qを残したまま数を取り除いていくというのは、上の数列の縦線をまたがないように連続したKK個を選んで、その最小値を除いていくということにほかならない。なぜならAp,AqA_p, A_qはほかの数より小さいので、縦線をまたぐとAp,AqA_p, A_qが取り除かれてしまうからだ。つまり、(Ai)(A_i)を複数の独立した数列に分割してそれぞれの最小値を見ればよさそうだ。

さて、「複数の独立した数列」をどう管理すればよいかが問題である。上の3つの部分列をA1,A2,A3{\mathcal A_1}, {\mathcal A_2}, {\mathcal A_3}とする。これらの数列から小さい数を除いていくとき、数列の最小値と長さにしか興味がないので、A1,A2,A3{\mathcal A_1}, {\mathcal A_2}, {\mathcal A_3}はそれぞれ(昇順の)優先度付きキューで表すことができる。さらに、A1,A2,A3{\mathcal A_1}, {\mathcal A_2}, {\mathcal A_3}自身も優先度付きキューQ{\mathcal Q}にいれることにし、Q{\mathcal Q}の順序はAA:{\mathcal A} \le {\mathcal A}&#x27; : \Leftrightarrow A{\mathcal A}の最小値\leA{\mathcal A}&#x27;の最小値 とする。

一般に、ll個の部分列からQQ個の数を取り除く操作を書き下すと、次のようになる。

  • A1,A2,...,Al{\mathcal A_1}, {\mathcal A_2}, ..., {\mathcal A_l}の中で長さがKK以上であるものだけQ{\mathcal Q}に入れて、残りは捨てる。
  • 次のステップを最大QQ回繰り返す。
    1. Q{\mathcal Q}の先頭から数列A{\mathcal A}を取り出す。
    2. A{\mathcal A}の最小値を取り出す。
    3. A{\mathcal A}の長さがまだKK以上ならQ{\mathcal Q}に戻し、KK未満なら捨てる。
  • Q{\mathcal Q}が空になる前にQQ個の数を取り出せたなら、その最大値-最小値を求める。

以上で答えが求まる。全体の計算量はO(N2logN){\mathcal O}(N^2 \log N)


問題を読んだときはNNが小さいので何をやってもできそうな気がしたけど、具体的な手順を与えるのに膨大な時間をかけてしまった。