2019年12月5日 | ブログ記事

ラビンカープ法のおはなし+二次元のロリハいいぞ

0214sh7

こんにちは。algorithm班のすくです。
この記事はtraPアドベントカレンダー2019 36日目の記事です。

前回の夏のアドカレではとてもお理工な記事を書いたので、今回は不真面目な記事を書こうと思います。

皆さん、何かに不満を抱えていませんか?切り刻んでやりたいと思ったことはありませんか?
このアルゴリズムは、そんなあなたの願いを叶えるアルゴリズムです(大嘘)。任意とはいかずとも多くの物をハッシュすることができます。

1.ローリングハッシュ(Rolling Hash)とは?

wikipedia
ローリングハッシュとは、与えられたもの(文字列が多い)を整数に変換するハッシュアルゴリズムのことです。

同じものを与えると同じ整数が出てきます。なので、違うものを与えると違う整数が出てくるように工夫すると、与えられるものと整数を1対1対応させることができます。

多項式ローリングハッシュ

数列や文字列など、(適切にキャストして)多項式とみなせるものをa0,...,an1a_{0},...,a_{n-1}とした上で、

H=a0bn1+a1bn2+...+an1b0H=a_{0}b^{n-1}+a_{1}b^{n-2}+...+a_{n-1}b^{0}

=i=0n1aibni1=\sum_{i=0}^{n-1} a_{i}b^{n-i-1}

でHを計算すると、多項式を整数にハッシュすることができます。bの値にもよりますが、通常Hは非常に大きな数字になるので、素数で割ったあまりとして保存します。

なんでbなんて面倒くさいのを入れるんだ、b=1でいいじゃないかと思う方もいると思いますが、b=1だとハッシュしきれません("xy"と"yx"や"wz"を同一視してしまうため)。

2.ラビンカープ法(Rabin–Karp algorithm)

ラビンカープ法とは、とある文字列Sに文字列Tが連続部分文字列として含まれているかどうかを高速に判定するアルゴリズムです。
競技プログラミングの文脈で単にローリングハッシュと言うとこれを指してることが多い気がします。(主観なので殴らないで!)

先程の「TはSの連続部分文字列か」は、T0,T1,...,TT1T_0,T_1,...,T_{|T|-1}Si,Si+1,...Si+T1S_i,S_{i+1},...S_{i+|T|-1}がそれぞれ等しいかで確かめられますが、Ο(|S||T|)かかってしまいます。これをΟ(|S|log(MOD)+|T|)にします。

Tをローリングハッシュした値はi=0T1Tibni1(modM)\sum_{i=0}^{|T|-1} T_{i}b^{n-i-1} (modM)
です。これはΟ(|T|)で求まります。

Hi=Sibni1H_i=S_ib^{n-i-1}

と置いて、

Hl+Hl+1+...+Hr(modM)H_l+H_{l+1}+...+H_{r} (mod M)

を計算すると、これは

Slbnl1+...+Srbnr1S_{l}b^{n-l-1}+...+S_{r}b^{n-r-1}

=bnr1×(Slbrl+...+Srb0)(modM)=b^{n-r-1}×(S_{l}b^{r-l}+...+S_{r}b^0) (modM)

つまり、Sのl文字目~r文字目の部分文字列をローリングハッシュした値のbnr1b^{n-r-1}倍になっています。よって、

Slbrl+...+Srb0=(bnr1)1×(Hl+Hl+1+...+Hr)S_{l}b^{r-l}+...+S_{r}b^0=(b^{n-r-1})^{-1}×(H_l+H_{l+1}+...+H_{r})

という式が成り立ちます。Hl+Hl+1+...+HrH_l+H_{l+1}+...+H_{r}は累積和を使うと前計算Ο(|S|)の上でΟ(1)で計算できます。また、Mが素数という性質を使って、繰り返し二乗法などで(bnr1)1(b^{n-r-1})^{-1}はΟ(log(MOD))で計算できます。

以上より、Sのl文字目~r文字目の部分文字列をローリングハッシュした値は前計算Ο(|S|)の上でΟ(log(MOD))で計算できることがわかりました。

l=0,1,...,STl=0,1,...,|S|-|T|, r=T1,T,...,S1r=|T|-1,|T|,...,|S|-1についてこの計算をすると、Sの長さ|T|である部分文字列をローリングハッシュした値すべてを求められます。これは前計算Ο(|S|)の上でΟ(log(MOD))のST+1|S|-|T|+1回計算なので、前計算込みでΟ(|S|log(MOD))で計算できます。

ST+1|S|-|T|+1個の文字列が最初に求めたTのハッシュ値と等しいかどうかでループを回すことで、「TはSの連続部分文字列か」という問題はΟ(|S|log(MOD)+|T|)で求めることができました。

3.問題を解いてみる

こんな問題がありました。AOJリンク

Substring (2444)

長さnの文字列s=s1,s2,…,snおよびm個のクエリが与えられる。 各クエリqk (1 ≤ k ≤ m)は、"L++", "L--", "R++", "R--"の4種類のいずれかであり、 k番目のクエリqkに対してl[k]とr[k]を以下で定義する。

L++:l[k]=l[k-1]+1,r[k]=r[k-1]
L--:l[k]=l[k-1]-1,r[k]=r[k-1]
R++:l[k]=l[k-1],r[k]=r[k-1]+1
R--:l[k]=l[k-1],r[k]=r[k-1]-1

但し、l[0]=r[0]=1である。
この時、m個の部分文字列 sl[k], sl[k]+1, …, sr[k]-1, sr[k] (1 ≤ k ≤ m) について、何種類の文字列が作られるかを答えよ。

bとMODの値を適当に決め、問題文の指示どおりに部分文字列の範囲を指定し、その部分文字列をローリングハッシュした値を求め、ハッシュ値が何種類あるかを求めればいけるはず!

AOJ #4021102

wa
アレッ!?WA!?通らない!!なんで!??

そうです、ローリングハッシュはあくまでハッシュ、衝突することがあるのです…

衝突って?

H=a0bn1+a1bn2+...+an1b0H=a_{0}b^{n-1}+a_{1}b^{n-2}+...+a_{n-1}b^{0}

最初に言ったとおり、この式はaが同じならHは同じです。しかし、aが違う時にHが違う保証は残念ながらありません。入力aが違うのにハッシュ値Hが同じになってしまうこと、これを衝突(collision)といいます。今回のWAの原因はこいつです。

衝突を回避しよう

今の所、衝突を100%回避する方法を僕は知りません(あるかもしれない)。
でも、衝突する確率を限りなく0%に近づけることは可能なのでそれをします。

さっきのコードで(b,MOD)の組を適当に用意しました(コードでは(114514,1000000007))。

それを5つずつ用意します(天下無双)

AOJ #4021098

ac
AC!
tumblr_p34edoLF9U1s26u9bo2_400

どうやら衝突を回避できたようです(bの値が死ぬほど汚え~)。

なぜ衝突を回避できたのかというと、bとMODの組を増やしたことにより、衝突する確率が低くなったからです。

増やす前のMODは1000000007(109)1000000007(\approx10^9)、つまりハッシュした値は大体10910^9通りしかないのに対し、この問題で与えられる文字列の長さは最大で3×1053×10^5、連続部分文字列は約4.5×10104.5×10^{10}個ある計算になります。全ての連続部分文字列が出てくるわけではありませんが、これでは衝突しても文句は言えません。

増やした後には10910^9ほどのMODが5つあり、全て素数です。つまり、ハッシュ値が大体104510^{45}通りある計算になり、衝突を回避するのに十分な通り数と言えます(実際はMODは2つで十分で、僕のはオーバーキルです)。

余談なんですが、B,MODそれぞれが相違である必要はなく、特にBが相違ならMODが共通でもいいと思います。というかこの問題に関してはそれで通ります。
AOJ #4021663

4.う し た ぷ に き あ く ん 笑でロリハをする

(注釈:この項は人としてふざけてるので急いでいる人は飛ばして下さい)

MODの値は素数でなければいけないけどbの値は1b<MOD1 \leq b<MODならなんでもいいっぽいです(あまり小さすぎるのはダメ)。ということでbを†文字列†にしちゃいます。

string B[5]={"u_shi","ta_pu","ni_chi_a","ku_n","wara"};

う し た ぷ に き あ く ん 笑

(勿論そのままでは扱えないので整数になおしています(小声))

これで出してみると…?

AOJ #4021686
ac2

はい通った~~wwwwwwwwwwwう し た ぷ に き あ く ん 笑でもロリハできた~~wwwwwwwこれがほんとのハッシュドビ

いってて…

このように、う し た ぷ に き あ く ん 笑に限らず、整数の代わりに文字列をbに据えることでもACが得られます。bにいろんな文字列を置いてコードにメッセージ性を与えていこう!

5.二次元ローリングハッシュ

ここまでは主に文字列や数列をハッシュする話を書きました。でもちょっと待てよ…

行列もハッシュできないか?

行列に恨みがある人のために行列(二重配列)をローリングハッシュするアルゴリズムを作りました。

H=a0bn1+a1bn2+...+an1b0H=a_{0}b^{n-1}+a_{1}b^{n-2}+...+a_{n-1}b^{0}

これを拡張します。

H=a0,0bn1cm1+a0,1bn1cm2+...+a0,m1bn1c0H=a_{0,0}b^{n-1}c^{m-1}+a_{0,1}b^{n-1}c^{m-2}+...+a_{0,m-1}b^{n-1}c^{0}

+a1,0bn2cm1+a1,1bn2cm2+...+a1,m1bn2c0+ a_{1,0}b^{n-2}c^{m-1}+a_{1,1}b^{n-2}c^{m-2}+...+a_{1,m-1}b^{n-2}c^{0}

\vdots

+an1,0b0cm1+an1,1b0cm2+...+an1,m1b0c0+ a_{n-1,0}b^{0}c^{m-1}+a_{n-1,1}b^{0}c^{m-2}+...+a_{n-1,m-1}b^{0}c^{0}

=i=0n1j=0m1ai,jbni1cmj1=\sum_{i=0}^{n-1}\sum_{j=0}^{m-1} a_{i,j}b^{n-i-1}c^{m-j-1}

しました。

行列Sの、左上が(l1,r1)(l_1,r_1)、右下が(l2,r2)(l_2,r_2)の部分行列(?)のハッシュ値は2.で書いたような変形をしてやると

Sl1,r1bl2l1cr2r1+...+Sl1,r2bl2l1c0+Sl2,r1b0cr2r1+...+Sl2,r2b0c0\begin{matrix} S_{l_{1},r_{1}}b^{l_{2}-l_{1}}c^{r_{2}-r_{1}} &+...+&S_{l_{1},r_{2}}b^{l_{2}-l_{1}}c^{0} \\ \vdots& &\vdots \\ +S_{l_{2},r_{1}}b^{0}c^{r_{2}-r_{1}} &+...+&S_{l_{2},r_{2}}b^{0}c^{0} \end{matrix}

=(bnl21)1(cmr21)1(Sl1,r1bnl11cmr11+...+Sl1,r2bnl11cmr21+Sl2,r1bnl21cmr11+...+Sl2,r2bnl21cmr21)(modM)=(b^{n-l_2-1})^{-1}(c^{m-r_2-1})^{-1}(\begin{matrix} S_{l_{1},r_{1}}b^{n-l_1-1}c^{m-r_1-1} &+...+&S_{l_{1},r_{2}}b^{n-l_1-1}c^{m-r_2-1} \\ \vdots& &\vdots \\ +S_{l_{2},r_{1}}b^{n-l_2-1}c^{m-r_1-1} &+...+&S_{l_{2},r_{2}}b^{n-l_2-1}c^{m-r_2-1} \end{matrix})(modM)

こうすると、累積和や繰り返し二乗も踏まえて前計算Ο(nm)の上でΟ(log(nm))で各ハッシュ値は得られます。列挙するならΟ(nmlog(nm))でしょうか。

これが何に使えるかというと、
・行列の中から同じ部分行列がある箇所を検出できる
・画像中で同じ箇所があれば検出できる
にっくき行列を切り刻める

これを応用すると3次元以上に拡張できると思う(書きたくない!)ので、d次元のものならこれを使って切り刻めるってわけですね

バグ消しきれてるか怪しいですが、コード置きます

class RollingHash{
    private:
    long long B[5]={114514,1919,810,893,364364};
    long long C[5]={31415,9265,3589,79323,846};
    long long M[5]={1000000007,1000000009,999999937,998244353,2147483647};
    long long Binv[5],Cinv[5];
    
    public:
    vector<string> S;
    vector<vector<long long>> H[5],Hsum[5];
    
    //繰り返し二乗法
    long long BE(long long b,int e,int m){
        long long r=1;
        while(e){
            if(e&1){
                r=(r*b)%M[m];
            }
            b=(b*b)%M[m];
            e >>=1;
        }
        return r;
    }

    
    void init(vector<string> cs){
        S=cs;
        int n=S.size();
        int m;
        if(n==0){
            m=0;
        }else{
            m=S[0].size();
        }
        
        //逆元
        for(int i=0;i<5;i++){
            Binv[i]=BE(B[i],M[i]-2,i);
            Cinv[i]=BE(C[i],M[i]-2,i);
        }
        
        //本体
        for(int i=0;i<5;i++){
            H[i].resize(n+1);
            for(int j=0;j<n+1;j++){
                H[i][j].assign(m+1,{0});
            }
            long long b=1,c=1;
            for(int j=n-1;j>=0;j--){
                c=1;
                for(int k=m-1;k>=0;k--){
                    H[i][j][k]=(((b*c)%M[i])*(long long)S[j][k])%M[i];
                    c=(c*C[i])%M[i];
                }
                b=(b*B[i])%M[i];
            }
        }
        
        //累積和
        for(int i=0;i<5;i++){
            Hsum[i].resize(n+1);
            for(int j=0;j<n+1;j++){
                Hsum[i][j].assign(m+1,{0});
            }
            for(int j=0;j<n;j++){
                for(int k=0;k<m;k++){
                    Hsum[i][j+1][k+1]=(Hsum[i][j+1][k+1]+H[i][j][k])%M[i];
                    Hsum[i][j+1][k+1]=(Hsum[i][j+1][k+1]+Hsum[i][j+1][k])%M[i];
                    Hsum[i][j+1][k+1]=(Hsum[i][j+1][k+1]+Hsum[i][j][k+1])%M[i];
                    Hsum[i][j+1][k+1]=(Hsum[i][j+1][k+1]-Hsum[i][j][k]+M[i])%M[i];
                }
            }
        }
    }
    
    //計算
    long long get(int l1,int r1,int l2,int r2,int m){
        long long R=(Hsum[m][l2+1][r2+1]-Hsum[m][l1][r2+1]-Hsum[m][l2+1][r1]+Hsum[m][l1][r1])%M[m];
        R=(R+M[m])%M[m];
        R=(R*BE(Binv[m],(S.size())-l2-1,m))%M[m];
        R=(R*BE(Cinv[m],(S[0].size())-r2-1,m))%M[m];
        return R;
    }
    
    
};

4.の通り、メッセージ性を与えることもできます

string B[5]={"逝くものは","斯くのごときか","長江は","昼を夜となし","はるけき日"};
string C[5]={"ゆかしきいさを","指す方の","はた窮みなき","嘆じてん","聖さびはや"};

これはなに

6.おわりに

いかがでしたか?

これを読んだみなさんもローリングハッシュをする気が起きましたでしょうか?え?起きない?そう…

どうでもいいけどローリングハッシュって必殺技っぽくない?競プロerに聞く名前がかっこいいアルゴリズム第一位だよ(サンプル数1)

さ~て、明日のtraPアドベントカレンダー2019は?

ramune さん
cyan さん

のお二方です!

明日もまた見て下さいね~!

この記事を書いた人
0214sh7

あおこーだー

この記事をシェア

このエントリーをはてなブックマークに追加

関連する記事

2019年12月7日
Pythonで競技プログラミングの勧め【AdC2019 38日目】
ebi
2019年12月4日
緑コーダーが1日1ACを265日続けた結果
hukuda222
2019年12月11日
円周率が無理数であることの証明【AdC2019 42日目】
Tarara
2019年12月11日
ぷよぷよってナンですか?【AdC2019 42日目】
arahi10
2019年12月10日
ブログ投稿ツイートを無理やり自動化した話【AdC2019 41日目】
xecua
2019年12月10日
理工系科目英語クラスについて【AdC2019 41日目】
kano

活動の紹介

カテゴリ

タグ