ローリングハッシュ法について

考え方

ローリングハッシュは文字列のハッシュ値(要約値)を高速に計算することで高速な文字列検索を可能にするアルゴリズムです。 ハッシュとは元のデータを適当な関数を用いて短く変換したもので、元のデータが変化すると変換結果も変わります。

ローリングハッシュハッシュでは文字列を単一の整数値に変換します。このとき同一の文字列は常に同一の整数に変換されるため、変換先が同じ数字なら元の文字列も同じ可能性が高い、ということになります。もちろんたまたま一致する可能性もありますが、変換先の整数がうまくばらけていればそのような確率は十分に下げることができます。

ローリングハッシュでハッシュ値を求める方法

基数$b$と除数$M$とを決めると、文字列$S=(s_1,s_2,…,s_n)$に対してそのハッシュ値$H(S)$は以下の通り計算されます。

$$H(S)=(\sum_{i=1}^{n} s_i b^{n-i})\ mod \ M$$

$s_1$から$s_n$は各文字に対して割り当てられた整数値で、例えば文字コード等が使えます。 $b$や$M$は任意に選ぶことができますが、後述するハッシュ値の衝突問題を防ぐために$M$はある程度大きい素数とするのが一般的です。 ただし、実装上$M$未満の整数二つの積がoverflowせず正しく計算できる必要があります。

重要な性質

このようなハッシュ値を使うと例えば長さ$n$の文字列$S$と、長さ$m$の文字列$T$があったとして

$H(S)$ $b^m+H(T)=H(S+T) \ mod\ M$ が成りたちます。

($S$と$T$をこの順に並べた文字列を$S+T$とします。$X \ mod \ M$を $0 \le X' < M$を満たし、$X$との差が$M$の倍数であるような整数$X'$を求める演算とします。)

この等式より$H(S)$と$H(T)$から容易に$H(S+T)$が求められ、 また逆に $H(S)$と$H(S+T)$から容易に$H(T)$が求められます。

高速な文字列検索

長さ$n$の文字列$S$の中から、長さ$m$の文字列$T$を検索したいとします。

愚直にやると$S$の1文字目から$m$文字目がTと一致するか調べ、$S$の2文字目から$m+1$文字目が$T$と一致するか調べ...というように一つづつずらしていく方法が考えられます。一致判定をする際に最初の方で違うと分かればすぐにやめることができますが、最悪$m$文字目まで確認することになります。そうした場合にかかる時間は$O(nm)$となります。

ローリングハッシュではこれを確率的にではありますが$O(n)$で計算できます。確率的にというのはハッシュ値がたまたまかぶってしまう可能性(衝突の可能性)があるからです。

具体的にどうするかというと、まず$S$の先頭$i$文字からなる文字列を$S'_i$として、$S'_0, \ S'_1, \ S'_2 \ ... \ S'_n$のハッシュ値を求めておきます。 $H(S_{i+1})=(H(S_i) \ b \ +s_{i+1}) \ mod \ M$ を使って計算すればこの前計算は$O(n)$でできます。

C++による実装例

long long M = 1000000007;
long long b = 10007;
vector<long long> H_S_prime(string S) {
    int n = S.size();
    vector<long long> hash_S_prime;
    hash_S_prime.push_back(0);
    for (int i = 0; i < n; i++) {
        hash_S_prime.push_back((hash_S_prime[i] * b + S[i]) % M);
    }
    return hash_S_prime;
}

次に$S$の$\ i+1$文字目から$\ i+m$文字目までが$T$と一致するかを調べます。 $H(T)$は定義に従って計算することで$O(m)$で求められます。 $S$の$\ i+1$文字目から$\ i+m$文字目までで構成される文字列のハッシュ値はローリングハッシュの性質から

$(H(S_{i+m})-H(S_i) \ b^m) \ mod \ M$　と求めることができます。

$b^m$を先に計算すればこの計算は$O(1)$でできるので、$i$を動かしても全体で$O(n)$で一致判定を終わらせることができます。

C++による実装例

#include <iostream>
#include <vector>
using namespace std;
long long M = 1000000007;
long long b = 10007;
long long Hash(string T) {
    int m = T.size();
    long long hash_T = 0;
    for (int i = 0; i < m; i++) {
        hash_T = (hash_T * b + T[i]) % M;
    }
    return hash_T;
}
vector<long long> H_S_prime(string S) {
    int n = S.size();
    vector<long long> hash_S_prime;
    hash_S_prime.push_back(0);
    for (int i = 0; i < n; i++) {
        hash_S_prime.push_back((hash_S_prime[i] * b + S[i]) % M);
    }
    return hash_S_prime;
}
int main(void) {
    string S = "hello";
    string T = "el";
    vector<long long> S_prime = H_S_prime(S);
    long long T_hash = Hash(T);
    long long bm = 1;
    for (int i = 0; i < T.size(); i++) {
        bm = bm * b % M;
    }
    for (int i = 0; i <= S.size() - T.size(); i++) {
        if (T_hash == (S_prime[i + T.size()] - S_prime[i] * bm % M + M) % M) {
            cout << i + 1 << "文字目から" << i + T.size() << "文字目" << endl;
        }
    }
}

ハッシュ値衝突の危険性

ハッシュ値による一致判定は、異なる文字列に対するハッシュ値が被ってしまうことで正しい結果が得られなくなるという問題点があります。 文字列が衝突を意図しないものであることが保証される場合、$b$や$M$は固定してかまいません。衝突確率は$n$個のハッシュ値を計算したときに$O(n^2 / M)$となります。$M$を大きくすれば衝突率は下がりますが、それでも十分でない場合は$b$と$M$の組を複数用意することで時間はその分かかるものの、さらに衝突率を下げることができます。 注意点として、$b$と$M$が互いに素でないと衝突率が上がってしまいます。例えば$b=2,M=2^{30}$とすると、文字列の末尾30文字でハッシュ値が決定してしまうことになりそれより先頭側の一致判定ができなくなります。またそれぞれの文字に対応するする数値が小さいとき、$b$をあまり小さくとると文字列が短いときにハッシュ値が小さい値に偏ります。$b$が$M$に近いときも似た問題が生じます。 衝突を意図した文字列が含まれうる場合は、これら注意点に加えて$b$と$M$、特に$b$を乱択するのが良いです。