こんにちは。algorithm班のすくです。
この記事はtraPアドベントカレンダー2019 36日目の記事です。
前回の夏のアドカレではとてもお理工な記事を書いたので、今回は不真面目な記事を書こうと思います。
皆さん、何かに不満を抱えていませんか？切り刻んでやりたいと思ったことはありませんか？
このアルゴリズムは、そんなあなたの願いを叶えるアルゴリズムです(大嘘)。任意とはいかずとも多くの物をハッシュすることができます。
1.ローリングハッシュ(Rolling Hash)とは？
wikipedia
ローリングハッシュとは、与えられたもの(文字列が多い)を整数に変換するハッシュアルゴリズムのことです。
同じものを与えると同じ整数が出てきます。なので、違うものを与えると違う整数が出てくるように工夫すると、与えられるものと整数を1対1対応させることができます。
多項式ローリングハッシュ
数列や文字列など、(適切にキャストして)多項式とみなせるものをとした上で、
でHを計算すると、多項式を整数にハッシュすることができます。bの値にもよりますが、通常Hは非常に大きな数字になるので、素数で割ったあまりとして保存します。
なんでbなんて面倒くさいのを入れるんだ、b=1でいいじゃないかと思う方もいると思いますが、b=1だとハッシュしきれません("xy"と"yx"や"wz"を同一視してしまうため)。
2.ラビンカープ法(Rabin–Karp algorithm)
ラビンカープ法とは、とある文字列Sに文字列Tが連続部分文字列として含まれているかどうかを高速に判定するアルゴリズムです。
競技プログラミングの文脈で単にローリングハッシュと言うとこれを指してることが多い気がします。(主観なので殴らないで！)
先程の「TはSの連続部分文字列か」は、とがそれぞれ等しいかで確かめられますが、Ο(|S||T|)かかってしまいます。これをΟ(|S|log(MOD)+|T|)にします。
Tをローリングハッシュした値は
です。これはΟ(|T|)で求まります。
と置いて、
を計算すると、これは
つまり、Sのl文字目~r文字目の部分文字列をローリングハッシュした値の倍になっています。よって、
という式が成り立ちます。は累積和を使うと前計算Ο(|S|)の上でΟ(1)で計算できます。また、Mが素数という性質を使って、繰り返し二乗法などではΟ(log(MOD))で計算できます。
以上より、Sのl文字目~r文字目の部分文字列をローリングハッシュした値は前計算Ο(|S|)の上でΟ(log(MOD))で計算できることがわかりました。
, についてこの計算をすると、Sの長さ|T|である部分文字列をローリングハッシュした値すべてを求められます。これは前計算Ο(|S|)の上でΟ(log(MOD))の回計算なので、前計算込みでΟ(|S|log(MOD))で計算できます。
個の文字列が最初に求めた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の値を適当に決め、問題文の指示どおりに部分文字列の範囲を指定し、その部分文字列をローリングハッシュした値を求め、ハッシュ値が何種類あるかを求めればいけるはず！
アレッ！？WA！？通らない！！なんで！？？
そうです、ローリングハッシュはあくまでハッシュ、衝突することがあるのです…
衝突って？
最初に言ったとおり、この式はaが同じならHは同じです。しかし、aが違う時にHが違う保証は残念ながらありません。入力aが違うのにハッシュ値Hが同じになってしまうこと、これを衝突(collision)といいます。今回のWAの原因はこいつです。
衝突を回避しよう
今の所、衝突を100%回避する方法を僕は知りません(あるかもしれない)。
でも、衝突する確率を限りなく0%に近づけることは可能なのでそれをします。
さっきのコードで(b,MOD)の組を適当に用意しました(コードでは(114514,1000000007))。
それを５つずつ用意します(天下無双)
AC！
どうやら衝突を回避できたようです(bの値が死ぬほど汚え～)。
なぜ衝突を回避できたのかというと、bとMODの組を増やしたことにより、衝突する確率が低くなったからです。
増やす前のMODは、つまりハッシュした値は大体通りしかないのに対し、この問題で与えられる文字列の長さは最大で、連続部分文字列は約個ある計算になります。全ての連続部分文字列が出てくるわけではありませんが、これでは衝突しても文句は言えません。
増やした後にはほどのMODが５つあり、全て素数です。つまり、ハッシュ値が大体通りある計算になり、衝突を回避するのに十分な通り数と言えます(実際はMODは２つで十分で、僕のはオーバーキルです)。
余談なんですが、B,MODそれぞれが相違である必要はなく、特にBが相違ならMODが共通でもいいと思います。というかこの問題に関してはそれで通ります。
AOJ #4021663
4.う し た ぷ に き あ く ん 笑でロリハをする
笑
(注釈:この項は人としてふざけてるので急いでいる人は飛ばして下さい)
MODの値は素数でなければいけないけどbの値はならなんでもいいっぽいです(あまり小さすぎるのはダメ)。ということでbを†文字列†にしちゃいます。
string B[5]={"u_shi","ta_pu","ni_chi_a","ku_n","wara"};
う し た ぷ に き あ く ん 笑
(勿論そのままでは扱えないので整数になおしています(小声))
これで出してみると…？
はい通った～～wwwwwwwwwwwう し た ぷ に き あ く ん 笑でもロリハできた～～wwwwwwwこれがほんとのハッシュドビ
いってて…
このように、う し た ぷ に き あ く ん 笑に限らず、整数の代わりに文字列をbに据えることでもACが得られます。bにいろんな文字列を置いてコードにメッセージ性を与えていこう！
5.二次元ローリングハッシュ
ここまでは主に文字列や数列をハッシュする話を書きました。でもちょっと待てよ…
行列もハッシュできないか？
行列に恨みがある人のために行列(二重配列)をローリングハッシュするアルゴリズムを作りました。
これを拡張します。
しました。
行列Sの、左上が、右下がの部分行列(?)のハッシュ値は2.で書いたような変形をしてやると
こうすると、累積和や繰り返し二乗も踏まえて前計算Ο(nm)の上でΟ(log(nm))で各ハッシュ値は得られます。列挙するならΟ(nmlog(nm))でしょうか。
これが何に使えるかというと、
・行列の中から同じ部分行列がある箇所を検出できる
・画像中で同じ箇所があれば検出できる
・にっくき行列を切り刻める
これを応用すると３次元以上に拡張できると思う(書きたくない！)ので、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 さん |
のお二方です！
明日もまた見て下さいね～！
