[C#] ローリングハッシュを実装する

ローリングハッシュとは

ローリングハッシュは文字列検索等に使われるアルゴリズムです。

ローリングハッシュを使うとある文字列Sのすべての部分文字列のハッシュ値を O(1) で返すことができるようになります。ローリングハッシュで得られるハッシュ値を使って文字列の比較を行うことで、通常比較する文字列の長さ分の計算量がかかる比較処理が O(1) で行えて計算量の削減につながります。

ローリングハッシュは前計算として、O(|S|) かかります。この計算をしておくとすべての部分文字列についてのハッシュが求められるようになります。

例えば、文字列Sに文字列Tが含まれるかどうかを判定するとき、先頭文字から舐めていく方法だと O(|S||T|) かかるところ、ローリングハッシュを使えばハッシュの突合せだけで済むので、O(|S|) で済むようになります。|T|文字の比較処理が無視できるようになっています。

ローリングハッシュの仕組み

文字列 C=C₁,C₂…C_m のハッシュを求めるハッシュ関数を以下のように定義します。B と MOD は互いに素な定数とします。

ハッシュ関数

H(C) = (C1\*Bm-1 + C2\*Bm-2 + ... + Cm\*Bm-m) % MOD

各文字C_iはAsciiコードの値をそのまま使い、そこに定数Bのm-i乗をかけた値を各文字ごとに足します。このままでは値が大きくて扱えないので、MODをとってこれをハッシュ値とします。

例えば “abc” のハッシュ値は以下のようになります。

H("abc") = 97*B2 + 98*B1 + 99*B0

ここで文字列に対するハッシュ関数を定義しましたが。この計算を愚直に毎度行うと、O(m) かかってしまい意味がありません。

累積和的な考え方を使う

累積和のような考え方を使って、先頭文字からk文字目までのハッシュ値を先に全て求めておきます。文字列Sの0からk+1文字目のハッシュ値は、0からk文字目までのハッシュ値を使って以下のように求められます。

H(S[0..k+1]) = (H(S[0..k]) * B + S[k+1]) % MOD

直前までのハッシュ値にBをかけて、次の文字の値を足しています。H(S[0..k]) の部分を式展開するとちゃんとハッシュ関数の式になっていることが確認できます。

あとは累積和のように H(S[l, r)) を求められます。

H(S[l, r)) = H(S[0, r)) - H(S[0, l)) * B(r-l) % MOD

こんな感じでハッシュ値が O(1) で求まります。一目なぜこうなるかわかりづらいですが、式変形すると理解できました。

C# で実装

ではローリングハッシュをC#で実装してみます。

class RollingHash
{
    public const long B = (long)1e5 + 7;
    public const long MOD = (long)1e9 + 7;
    public string S { get; set; }
    public int N { get; set; }
    public long[] Power { get; set; }
    public long[] Hash { get; set; }
    public RollingHash(string s)
    {
        this.S = s;
        this.N = s.Length;
        // B^nを計算しておく
        this.Power = new long[this.N + 1];
        this.Power[0] = 1;
        for (int i = 0; i < N; i++)
        {
            this.Power[i + 1] = (this.Power[i] * B) % MOD;
        }
        // ハッシュを前計算する
        this.Hash = new long[this.N + 1];
        for (int i = 0; i < N; i++)
        {
            this.Hash[i + 1] = (this.Hash[i] * B + S[i]) % MOD;
        }
    }
    // S[l, r) のハッシュ値を求める
    public long Get(int l, int r)
    {
        var hash = this.Hash[r] - (this.Hash[l] * this.Power[r - l] % MOD);
        if (hash < 0) hash += MOD;
        return hash;
    }
}

Bⁿ もあらかじめ計算しておかないといけません。あとはハッシュ値を上記の式通り、ハッシュを前計算し、計算すればOKです。

テスト

では実装したローリングハッシュを使って文字列検索がうまくいくか試してみます。

その前に一応うまくハッシュが求まっているか見てみます。

var s = "abab";
var rh = new RollingHash(s);
Console.WriteLine(rh.Get(0, 2)); // abのハッシュ   = 9700777
Console.WriteLine(rh.Get(2, 4)); // abのハッシュ   = 9700777
Console.WriteLine(rh.Get(1, 3)); // baのハッシュ   = 9800783
Console.WriteLine(rh.Get(0, 4)); // ababのハッシュ = 893689400

ちゃんと同じ部分文字列に対するハッシュが等しいことがわかります。

No.430 文字列検索 – yukicoder

No.430 文字列検索 – yukicoder

yukicoderの文字列検索の問題を解いてみます。

大文字のアルファベットからなる文字列Sが１つ与えられる。

次に、M個の異なる文字列Ci(i = 0, 1, … , M−1)が与えられる。

文字列Sのなかに文字列Ciが部分文字列としてそれぞれいくつ含まれるか数え合計を答えよ。

制約

• 文字列Sは大文字のアルファベットのみからなる。
• 1≤文字列Sの長さ≤50000=5×10⁴
• Mは正の整数。
• 1≤M≤5000=5×10³。
• i番目の文字列Ciは大文字のアルファベットのみからなる。
• 1≤ 文字列Ciの長さ ≤10。
• Ciは互いにすべて異なる文字列である。

Ciの文字列が10以下なので、Sの10文字以下の部分文字列のハッシュを数え上げておけばよさそうです。

// 入力省略 ...

// Sの最大10文字からなる部分文字列のハッシュの出現回数を数え上げる
var count = new Dictionary<long, long>();
var rhs = new RollingHash(S);
for (int i = 0; i < S.Length; i++)
{
    for (int d = 1; d <= 10; d++)
    {
        if (i + d > S.Length) break;
        var hash = rhs.Get(i, i + d);
        if (count.ContainsKey(hash)) count[hash]++;
        else count[hash] = 1;
    }
}
// TのハッシュがSの部分文字列のハッシュとして何度出現するか数え上げ
var ans = 0L;
foreach (var t in C)
{
    var rht = new RollingHash(t);
    var hash = rht.Get(0, t.Length);
    if (count.ContainsKey(hash)) ans += count[hash];
}
Console.WriteLine(ans);

ACしたので実装自体は間違ってなさそうです。

B と MOD の選び方、ハッシュの衝突

ハッシュ関数は一意なハッシュ値を返しますが、まれにハッシュが衝突する場合があります。ハッシュの衝突が起きると、異なる文字列であるのに同じハッシュ値を返してしまい、これを使って判定すると異なる文字列を同じ文字列であると処理してしまいます。

ハッシュの衝突が起きる可能性は B と MOD の選び方に依存するみたいです。

ハッシュの衝突を回避するために2つの B と MOD を用意しておき、ハッシュ値を2つ返して両方一致するか確かめるという方法があります。ほかの人の実装を見ているとそうしている人が多そうでした。

蟻本の実装

蟻本にもローリングハッシュの解説があるのですが、そこではMODをとるという操作を無視するために 64bit符号差し整数(C#だとulong)を使って実装する方法が解説されていました。

class RollingHash
{
    public const ulong B = (ulong)1e9 + 7;
    public string S { get; set; }
    public int N { get; set; }
    public ulong[] Power { get; set; }
    public ulong[] Hash { get; set; }
    public RollingHash(string s)
    {
        this.S = s;
        this.N = s.Length;
        // B^nを計算しておく
        this.Power = new ulong[this.N + 1];
        this.Power[0] = 1;
        for (int i = 0; i < N; i++)
        {
            this.Power[i + 1] = this.Power[i] * B;
        }
        // ハッシュを前計算する
        this.Hash = new ulong[this.N + 1];
        for (int i = 0; i < N; i++)
        {
            this.Hash[i + 1] = this.Hash[i] * B + S[i];
        }
    }
    // [l, r) のハッシュ値を求める
    public ulong Get(int l, int r)
    {
        var hash = this.Hash[r] - (this.Hash[l] * this.Power[r - l]);
        return hash;
    }
}

こんな感じで計算部分を ulong にすることでオーバーフロー時に0に戻るようにしています。MOD が 263-1 で計算していることと同じになっているはずです。

263-1 は素数ではないですし、ハッシュの精度が犠牲になるみたいです。その代わり剰余計算がなくなるので計算処理部分はとても高速になります。例えばここで解説されている問題をローリングハッシュ+二分探索でLCPを求めて解くと、ulong で剰余計算をさぼった実装だとACできますが、MODをとっているとTLEしました。

以上。

参考記事

• Rolling hash – SlideShare
• 蟻本片手に学ぶアルゴリズム ローリングハッシュ – Qiita
• AtCoder ABC 141 E – Who Says a Pun? (500 点) – けんちょんの競プロ精進記録