Help us understand the problem. What is going on with this article?

安全で爆速なRollingHashの話

要約

ロリハ(RollingHash)のModを$2^{61}-1$にすると安全で爆速になってむちゃくちゃ幸せになれます。

前提知識

bit演算に関する基礎的な知識を要求します。
また、RollingHashについては以下で解説しますが、分からない場合は別の記事を読んだほうがいいかもしれません。

RollingHashとは?

開く

「文字列を一つの大きな整数として見る」というのがRollingHashのアイデアです。
まず、0-9のみの数字を含んだ文字列s = "1234567890"を考えてみます。

ここで、この文字列のHash値文字列を10進数と解釈したときの数値と定義します。
また、$s$の$a$文字目から$b$文字目の前までの部分文字列を$s[a..b]$と書くことにします。
例えば、s = "1234567890"について、$s[1..3]$は1文字目から3文字目の前までの部分文字列なので、"23"となります。
よって、$hash(s[0..10])$(文字列全体のHash)は$1234567890$、$hash(s[3..7])$は$4567$となります。

また、$hash(s[0..7])=1234567$、$hash(s[0..3])=123$なので、$hash(s[3..7])=hash(s[0..7])-hash(s[0..3])\cdot 10^4$として計算できることが分かります。一般に、$hash(s[a..b])=hash(s[0..b])-hash(s[0..a])\cdot base^{b-a}$となります。ここで、$base$はHashの法、つまり10進法の10です。(証明はしませんが、$hash(s)=\sum_{i=0}^{n-1} s_i\cdot base^{n-i-1}$という式から容易に導出することができます。)
そのため、$base^0$から$base^n$、$hash(s[0..0])$から$hash(s[0..n])$を前計算しておけば、任意の$a$,$b$($a \le b$)について$hash(s[a..b])$を(演算を定数時間として)$O(1)$で求めることができます。

これを一般の文字列について拡張してみます。例えば、小文字アルファベットのみを含んだ文字列の場合はbaseを27とし、a=1,b=2,c=3...y=25,z=26とすることによって上記のような操作が可能になります。

また、Hashが大きくなりすぎる問題を解決するため、Hashは特定の素数でModを取った状態で保存します。Modを取った整数同士では、整数と同じように定数時間で加算/乗算ができるためです。

安全にRollingHashを使うために~衝突の回避~

RollingHashで最も気をつけるべきこととして、2つの異なる文字列が同じHashを取ることがあります。(これをHashの衝突と呼びます。)
基本的なこととして、数字への割当が0となる文字を作ってはいけません。例えば、a=0とした場合にbbaaa等の文字列のHashが全て衝突します。
また、全てのHashはModを取られるため、Mod未満となります。そのため、Mod以上の個数のHashを生成した場合、必ずどこかのペアがHashの衝突を起こします。そのため、できる限り大きいModを取ることが求められます。
また、Hashの衝突がどこか一回でも起こる確率は想像以上に高いです(誕生日のパラドックス)。Hashがランダムに分布すると仮定した場合、衝突がp%の確率で発生する試行回数は以下の表のようになります。(Wikipediaより)
image.png
これを見ると、32bitのMod一つでRollingHashを行った場合、$10^5$個程度のHashを生成するだけでも半分以上の確率でどこかのHashが衝突していることが分かります。怖いですね。
また、Hackで撃墜される可能性があるCodeForces等のコンテストでは、十分に大きなModを取っても故意にぶつけられる可能性があります。これを回避するには、$base$を実行時にランダムに決定すると良いです。(Modをランダムにしても良いですが、定数での除算はコンパイラによって最適化が掛けられて早くなるため、実行時依存のModはできる限り避けたいです。)
また、$2^{64}$等の2の冪乗をModとすることは避けるべきです。その場合、$base$がランダムであっても衝突するケースを作成することが可能なためです。
詳しくはEtoNagisaさんのスライド(Rolling Hashを殺す話)を参照してください。

まとめ:
空間は大きく取ろう(64bitのModを使うか、32bitの互いに素なModを2個使えば十分)
$base$はランダムに取ろう

高速なロリハを求めて~メルセンヌ素数mod~

Modを取る演算は最適化を鑑みても高速ではないため、できるならばMod2つは避けたいです。しかし、32bitより大きいModを使用した場合、2つの数の乗算後に64bitでもオーバーフローしてしまう可能性があります。

a・b mod 2^61-1をオーバーフローなしで計算する

ここで、Modに$2^{61}-1$を採用することを考えます。この数は素数であり、十分に大きいため安全性は十分です。
また、$2^{61} \equiv 1 \pmod{2^{61}-1}$なため、$a\cdot 2^{61} \equiv a \pmod{2^{61}-1}$です。これを利用すると、$a \cdot b \bmod 2^{61}-1$を64bitの範囲内で求めることができます。

まず、a,bをそれぞれ$a=au\cdot 2^{31}+ad,b=bu\cdot 2^{31}+bd (ad,bd \lt 2^{31})$のように分割します。すると、以下の図のように64bit以内で計算を行うことができます。

Untitled Diagram (3).png

正確には、$a\cdot b=au\cdot bu\cdot 2^{62}+(au\cdot bd+ad\cdot bu)\cdot 2^{31}+ad\cdot bd$の各項について、以下のように処理すれば良いです。

  • $au\cdot bu$

$au\cdot bu\cdot 2^{62} \equiv au\cdot bu\cdot 2 \pmod{2^{61}-1}$なため、$au\cdot bu\cdot 2$を足せば良いです。

  • $au\cdot bd+ad\cdot bu$

簡略化のために$mid = au\cdot bd+ad\cdot bu$とします。
$mid = midu\cdot 2^{30}+midd(midd \lt 2^{30})$と分割することにより、$mid\cdot 2^{31} = midu\cdot 2^{61}+midd\cdot 2^{31} \equiv midu+midd\cdot 2^{31} \pmod{2^{61}-1}$となります。これを足せば良いです。

  • $ad\cdot bd$

$ad\cdot bd$はそのまま足せば良いです。

これをまとめると、$au\cdot bu\cdot 2+midu+midd\cdot 2^{31}+ad\cdot bd$となります。最大ケースを考えてみると分かりますが、これは$2^{64}$以上になることはありません。最後に、この値についても$2^{61}-1$でModを取れば良いです。

a,bからau,bu,ad,bdを求めることを考えます。au,buを求めるには$2^{31}$で切り捨て除算をすれば良く、これは31bit右シフトをするのと等価です。ad,bdを求めるためには$2^{31}$で割ったあまりを求めれば良く、これは$2 ^ {31} - 1$($0b\underbrace{111\cdots 111}_{30個}$)とand演算をすることと等しいです。これらは高速な演算なので、au,bu,ad,bdは高速に求めることができます。
以下に実装を示します。

const ulong MASK30 = (1UL << 30) - 1;
const ulong MASK31 = (1UL << 31) - 1;
const ulong MOD = (1UL << 61) - 1;

//a*b mod 2^61-1返す関数(最後にModを取る)
ulong Mul(ulong a, ulong b)
{
    ulong au = a >> 31;
    ulong ad = a & MASK31;
    ulong bu = b >> 31;
    ulong bd = b & MASK31;
    ulong mid = ad * bu + au * bd;
    ulong midu = mid >> 30;
    ulong midd = mid & MASK30;
    return CalcMod(au * bu * 2 + midu + (midd << 31) + ad * bd);
}

//mod 2^61-1を計算する関数
ulong CalcMod(ulong val)
{
    val = (val & MOD) + (val >> 61);
    if (val > MOD) val -= MOD;
    return val;
}

RollingHashに組み込む際に工夫すると良いこと

この項では、解説の項に出てきた記法と同じ記法を用います。
具体的には、$s$の$a$文字目から$b$文字目の前までの部分文字列を$s[a..b]$と書き、文字列$s$のHashを$hash(s)$と書くことにします。

以下に示すような工夫をすると、より高速に$\bmod{2^{61}-1}$でのRollingHashの実装を行うことができます。
まず、上の実装例で示した関数Mulについて、最後にModを取らないように書き換えます。(return前のCalcModを省略するだけで良いです。)

//au*bu*2+midu+midd*2^31+ad*bdそのものを返す関数(最後にModを取らない)
ulong Mul(ulong a, ulong b) { /*実装略*/ }
//mod 2^61-1を計算する関数
ulong CalcMod(ulong val) { /*実装略*/ }

ここで、RollingHashの配列を計算する処理について考えてみます。$hash(s[0..n+1])=hash(s[0..n]) \cdot base + s[n]$となるため、ソースコードでは以下の通りとなります。

ulong[] hash = new ulong[n + 1]; //要素数n+1の配列を初期化
for (int i = 0; i < n; i++) hash[i + 1] = CalcMod(Mul(hash[i], Base) + s[i]);

Mul(a, b)の最大値は、$a,b \lt mod$であった場合は$mod \cdot 3$未満です。そのため、各文字の最大値(asciiの場合は127、32bitだとしても$2^{32}-1$)を足したところでオーバーフローすることはありません。そのため、各計算につき最後に一度だけModを計算するだけで十分であることが分かります。

また、部分文字列についてのHashを求める処理については少し注意が必要です。部分文字列のHashは$hash(s[a..b])=hash(s[0..b])-hash(s[0..a])\cdot base^{b-a}$として求められますが、減算が出てくるために負のオーバーフローが発生する可能性があります。
ここで、Mul(a, b)の最大値が$mod \cdot 3$未満であったことを思い出します。つまり、$hash(s[0..b])$にあらかじめ$mod \cdot 3$以上で$n \equiv 0 \pmod{2^{61}-1}$となるような整数$n$を足しておくことで、演算結果を変えずに負方向へのオーバーフローを免れることができます。
これを実装すると以下のようになります。

const ulong POSITIVIZER = MOD * 3;
ulong hash = CalcMod(hash[end] + POSITIVIZER - Mul(hash[begin], powMemo[end - begin]))

実装のサンプルはこちらにあります。(C#です。)

速度

ABC141-Eを用いて計測を行いました。

2^61-1 32bit 1つ 32bit 2つ
最大実行時間 298ms 370ms 656ms
合計実行時間 8906ms 11123ms 18695ms

C#で実装したため、速度はC++などの言語とは違うと思います。実際に、C++だと32bit 1つの方が早かったというケースもありました。しかし、安全でかつ早いRollingHashを作るのであれば$2^{61}-1$をModとすることをお勧めします。

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away