コンテンツにスキップ

ローリングハッシュ

タグ「ローリングハッシュ」の記事 1 件

ローリングハッシュのリンク集

ローリングハッシュについて、参考になる記事や資料をまとめました。

ローリングハッシュは、文字列 S=s0s1…sn−1S = s_0 s_1 \dots s_{n-1} を基数 BB の多項式 s0Bn−1+s1Bn−2+⋯+sn−1s_0 B^{n-1} + s_1 B^{n-2} + \dots + s_{n-1} とみなし、素数 pp で割った余りをハッシュ値とする方法です。接頭辞のハッシュ hih_i と BiB^i を O(n)O(n) で前計算しておくと、部分文字列 S[l,r)S[l, r) のハッシュは hr−hlBr−lh_r - h_l B^{r-l} で O(1)O(1) で求まります(累積和と同じ考え方です)。ハッシュが違えば文字列は必ず違い、同じなら高い確率で同じなので、部分文字列どうしの一致判定が O(1)O(1) でできます。二分探索と組み合わせると、2 つの部分文字列の最長共通接頭辞(LCP)の長さが O(log⁡n)O(\log n) で求まり、辞書順の比較もできます。文字を 00 に対応させると、b と ab のように長さの違う文字列が同じハッシュになるので、文字は 11 以上の値に対応させます。

ハッシュは衝突する(違う文字列が同じハッシュになる)ことがあるので、mod と基数の選び方に注意が必要です。

  • mod と基数を固定すると、それに対して衝突する入力を作れます。Codeforces のように撃墜(Hack)のあるコンテストでは実際に狙われるので、基数は実行時に乱数で選びます。
  • mod を 2642^{64} にして符号なし 64 bit 整数のオーバーフローに任せる方法は、基数を乱数で選んでも、Thue–Morse 列から作った長さ 2102^{10}〜2122^{12} 程度の 2 つの文字列で衝突します。mod は素数にしてください。
  • mod 261−12^{61}-1 はメルセンヌ素数で、十分大きく、積の余りをビット演算で速く計算できるので、よく使われます。10910^9 程度の素数を使う場合は、mod を 2 つ以上組み合わせます。
  • mod が素数 pp で基数を一様ランダムに選ぶと、長さ nn の異なる 2 つの文字列が衝突する確率は (n−1)/p(n-1)/p 以下です(差を基数の n−1n-1 次以下の多項式とみると、その根は n−1n-1 個以下だからです)。比較の回数が多いと、確率はその回数倍まで増えます。
  • たくさんのハッシュ値を集めてその中に同じものがあるかを調べるときは、誕生日のパラドックスにより、ハッシュ値がおよそ p\sqrt{p} 個あると衝突しやすくなります。p≈109p \approx 10^9 の mod 1 つでは 10510^5 個程度でもほぼ確実に衝突します。

Python では整数の大きさに上限がないので、mod 261−12^{61}-1 の積もそのまま計算して % で余りを取れます。ただし、処理系によっては 64 bit を超える整数の計算がかなり遅くなるので、積を分割して 64 bit 以内に収める実装もあります。

  • ABC274 Ex - XOR Sum of Arrays の解説(Nyaan、AtCoder 公式解説)
    • 前半の「Rolling Hash とは?」の節が、ローリングハッシュの解説になっています。任意の部分列のハッシュを O(1)O(1) で求める方法と、基数を実行時にランダムに選べば、どんな入力でも衝突する確率が (N−1)/p(N-1)/p 以下になることの証明を説明しています。後半は、この問題のために XOR を加法とする体(Nimber)でローリングハッシュを作る話です。
    • 衝突耐性の説明の「A,BA, B であって H(A)≠H(B)H(A) \neq H(B) を満たすような」は、「A≠BA \neq B かつ H(A)=H(B)H(A) = H(B) を満たすような」の誤りです。
  • 安全で爆速なRollingHashの話(keymoon、Qiita)
    • 文字を 00 に対応させない、mod を大きくする、基数を実行時にランダムに選ぶ、2642^{64} などの 2 の累乗を mod にしない、という注意点をまとめたうえで、mod 261−12^{61}-1 の積を 64 bit 整数の範囲で計算する方法を図つきで説明しています。最後に __int128 を使う簡単な書き方にも触れています。コードは C# です。
    • 記事末尾の「実装のサンプル」へのリンクは、URL が壊れていて開けません。
  • 競プロ典型 90 問 047 の解説(E869120、画像)
    • 部分文字列の一致判定にローリングハッシュを使う解説の 2 枚目です。接頭辞のハッシュから部分文字列のハッシュを求める式を図で示し、mod を 2642^{64} にするとどんな基数でも WA になるケースが作れることにも触れています。
  • ハッシュを衝突させる話(hos)
    • mod が素数で基数を一様ランダムに選べば衝突する確率が (長さ −1-1)/mod 以下になる理由と、mod 2k2^k だと任意の奇数の基数で衝突する多項式が作れることを説明しています。後者から、長さ 4096 の 2 つの 01 文字列が mod 2642^{64} で衝突する例を作っています。
  • Rolling Hashを殺す話(EtoNagisa、スライド)
    • mod と基数を固定したローリングハッシュに対して、格子基底簡約(LLL)で衝突する文字列を作る方法と、mod と基数の組を 2 つにしても衝突させられる方法を紹介しています。結論は「mod を十分大きな素数にし、基数を実行時に乱数で選ぶ」です。最後に、mod 2642^{64} が基数によらず Thue–Morse 列で衝突する理由も説明しています。
  • Anti-hash test.(Zlobober、Codeforces、英語)
    • mod 2642^{64} のハッシュが、基数によらず Thue–Morse 列('A' + __builtin_popcount(i) % 2 で作る文字列)で衝突することを示した、この話の元になった記事です。
  • On the mathematics behind rolling hashes and anti-hash tests(dacin21、Codeforces、英語)
    • 基数をランダムにする方法と mod をランダムにする方法の衝突確率、乱数の種の取り方、ハッシュを複数使う場合や比較の回数が多い場合の見積もり、mod 261−12^{61}-1 の積の計算を説明しています。後半では、Thue–Morse 列、誕生日攻撃、木を使う攻撃、格子基底簡約など、衝突する入力の作り方を表にまとめて説明しています。固定の基数なら mod 261−12^{61}-1 でも衝突を作れることがわかります。
  • Hashing and Probability of Collision(rng_58、英語)
    • ローリングハッシュの衝突確率が Schwartz–Zippel の補題から N/MODN/\mathrm{MOD} 以下になることを説明し、同じ考え方で多重集合や根付き木の良いハッシュを作っています。グラフの同型判定を例に、理論的な保証のない「悪いハッシュ」についても書いています。
    • 根付き木の多項式の定義で、子の部分木を G1,…,GdG_1, \dots, G_d としているのは G1,…,GkG_1, \dots, G_k の誤記です。
  • AtCoder ABC 141 E - Who Says a Pun?(けんちょんの競プロ精進記録)
    • 下の練習問題の解説で、Suffix Array、Z algorithm、ローリングハッシュと二分探索による LCP、の 3 通りの解法を比べています。各組の LCP を二分探索で求める方法は遅く、長さを決め打ちして二分探索する方法にすると 1735 ms から 13 ms に速くなった、という話もあります。
    • ローリングハッシュのコードは mod 109+710^9+7・109+910^9+9 と基数を固定しています。
  • ABC331 F - Palindrome Query の解説(Nyaan、AtCoder 公式解説)
    • 左から計算したハッシュと右から計算したハッシュが一致するかで回文を判定し、連結したときのハッシュの式を使ってセグメント木に載せることで、1 文字の更新にも対応しています。mod 10910^9 程度で何組使えば失敗確率が十分小さくなるかの見積もりもあります。
  • ラビンカープ法のおはなし+二次元のロリハいいぞ(traP)
    • 後半の「二次元ローリングハッシュ」の節で、行列の (i,j)(i, j) 成分に Bn−i−1Cm−j−1B^{n-i-1} C^{m-j-1} を掛けて足す 2 次元のハッシュと、2 次元の累積和で部分行列のハッシュを求める方法を説明しています。前半は 1 次元の説明と、mod 109+710^9+7 1 つでは衝突して WA になった例です。
    • 基数と mod を固定していて、部分行列のハッシュを逆元を使って O(log⁡)O(\log) で求めています。冪を掛けて比べるようにすれば逆元はいりません。コードについては、筆者自身が「バグ消しきれてるか怪しい」と書いています。

ローリングハッシュを扱う講座はまだありませんが、衝突確率の根拠になる講座があります。

  • Fp\mathbb{F}_p 係数の多項式
    • 【定理 5】で Fp\mathbb{F}_p 係数の nn 次方程式の解が nn 個以下であることを示し、4 章で多変数に一般化した Schwartz–Zippel の補題を証明しています。基数をランダムに選んだローリングハッシュが衝突する確率の評価は、この定理からすぐ出ます。【問題 6】では、mod が素数でないと解の個数の評価が成り立たない例(mod 88 で x2−1x^2-1 の根が 4 個など)を扱っていて、mod 2642^{64} が危ない理由とつながります。
  • 文字列アルゴリズム(いかたこのたこつぼ)
    • 「Rabin-Karp法(ローリングハッシュ)」の節で、ハッシュの列で文字列を検索する考え方を図で説明しています。Python の実装例は mod 261−12^{61}-1 で、基数を乱数で 3 つ選び、Python の多倍長整数でそのまま計算しています。
  • RollingHashクラスをPythonでつくったよ。(hyouchun、Qiita)
    • 上の keymoon の記事の、積を分割して mod 261−12^{61}-1 を 64 bit 以内で計算する方法を、そのまま Python に移したクラスです。基数は乱数で選び、複数の文字列で同じ基数を共有します。説明はほとんどなく、コードと使い方だけです。
  • ローリングハッシュ (Rabin-Karp)(Competitive programming notebook)
    • 部分文字列のハッシュ、連結したハッシュ、二分探索による LCP の 3 つの機能を持つ Python のクラスと、mod を 2 つ使う例があります。
    • 「性質」の節の式 H(Cl,r)≡H(C1,r)−H(C1,l−1)H(C_{l,r}) \equiv H(C_{1,r}) - H(C_{1,l-1}) は、右辺の第 2 項に br−l+1b^{r-l+1} を掛けるのが正しいです。コードは正しく power[r-l] を掛けています。また、クラスの既定値は基数 34913491・mod 999999937999999937 の固定です。

AtCoder Library(ACL)にローリングハッシュはありません(文字列については z_algorithm や suffix_array があります)。

  • Rolling Hash (ローリングハッシュ)(Luzhiled’s Library)
    • mod 261−12^{61}-1 で基数を実行時に乱数で選ぶ C++ の実装です。部分文字列のハッシュ、LCP、ハッシュの連結のほか、先頭と末尾への文字の追加もできます。
  • Rolling Hash(Nyaan’s Library)
    • mod 261−12^{61}-1 で、基数を乱数で 2 つ(テンプレート引数で変更可)選ぶ C++ の実装です。部分文字列のハッシュ、文字列検索、LCP、部分文字列どうしの辞書順の比較があります。
  • ラビン-カープ文字列検索アルゴリズム(日本語版 Wikipedia)
    • ハッシュ値が一致したときだけ文字列そのものを比べる、という本来のラビン-カープ法を擬似コードで説明し、ローリングハッシュで次のハッシュ値を定数時間で求める例や、複数パターンの検索も扱っています。日本語版 Wikipedia には「ローリングハッシュ」の記事はありません。
    • 擬似コードのループが for i from 1 to n になっていますが、パターンの長さを mm とすると n−m+1n-m+1 までが正しいです。
  • Rabin–Karp algorithm(英語版 Wikipedia)
    • 内容は日本語版とほぼ同じで、擬似コードのループの範囲は正しく n-m+1 までです。ハッシュ関数をランダムに選ぶべきことにも触れています。競プロでよく使う「ハッシュが一致したら同じとみなす」使い方と違い、一致したら文字列を比べて確かめる方法です。
  • Rolling hash(英語版 Wikipedia)
    • 多項式によるローリングハッシュのほか、Rabin fingerprint、Buzhash、Gear hashing、rsync などで使う content-defined chunking まで扱っています。競プロとの関係は薄めです。
  • String Hashing(cp-algorithms)
    • 多項式ハッシュの定義、部分文字列のハッシュを逆元なしで比べる方法、異なる部分文字列の個数を O(n2)O(n^2) で数える例、ハッシュを 2 つ使って衝突確率を下げる話があります。mod 2642^{64} は基数によらず衝突する文字列が作れるので勧めない、とも書かれています。
    • コードは基数 3131・mod 109+910^9+9 の固定で、基数をランダムに選ぶ話はありません。異なる部分文字列の個数を数えるコードは、mod 109+910^9+9 1 つで多数のハッシュを unordered_set に入れるので、nn が大きいと誕生日のパラドックスにより衝突しやすいです。
  • String Hashing(USACO Guide)
    • Python のテンプレート、Schwartz–Zippel の補題による衝突確率、誕生日のパラドックスの警告、例題の解説と問題の一覧があります。後半は集合を XOR で表す Zobrist hashing です。
    • テンプレートは基数 99739973・mod 109+910^9+9 の固定です。本文の警告にある通り、多数の文字列を扱うときは mod 261−12^{61}-1 にし、撃墜のあるコンテストでは基数を乱数で選んでください。
  • AOJ ALDS1_14_B - 文字列検索:文字列 TT の中で文字列 PP が現れる位置をすべて出力します。ローリングハッシュの基本の確認に使えます。
  • ABC141 E - Who Says a Pun?:重ならずに 2 回以上現れる部分文字列の最長の長さを、長さを二分探索してハッシュの重複で判定します。公式解説の本筋は Z algorithm で、ローリングハッシュは別解です。
  • 競プロ典型 90 問 047 - Monochromatic Diagonal(★7):TT の文字をうまく置き換えると、斜めの列が一色かどうかは、SS と TT の接頭辞と接尾辞の一致判定になります。
  • ABC150 F - Xor Shift:隣どうしの XOR の列に直すと、巡回シフトした列との一致判定になります。公式解説は KMP 法で、典型 90 問 047 の解説で類題として挙げられています。
  • ABC135 F - Strings of Eternity:ss をつなげた文字列の各位置で tt と一致するかを求めて、グラフの最長パスを考えます。公式解説に、mod 2642^{64} で衝突する入力を用意してあると書かれています。
  • ABC284 F - ABCBAC:TT の前半と、後半を反転した文字列の一致判定を、各 ii について O(1)O(1) で行います。公式解説は Z algorithm ですが、ローリングハッシュでも解けると書かれています。
  • ABC331 F - Palindrome Query:1 文字の更新と回文判定のクエリを、両向きのハッシュを載せたセグメント木で処理します。
  • ABC312 Ex - snukesnuke:文字列を何回か繰り返した文字列がすでに使われているかを判定します。公式解説の本筋は Z algorithm で周期を求める方法ですが、ローリングハッシュを使う解法も載っています。
  • AOJ ALDS1_14_C - パターン検索:H×WH \times W の文字の盤面から R×CR \times C のパターンを探します。2 次元のローリングハッシュの練習になります。
  • ABC274 Ex - XOR Sum of Arrays:2 つの区間の XOR をとった列と別の区間の辞書順の比較を、XOR と相性のよい体の上のローリングハッシュと LCP の二分探索で行います。