文字列検索で用いられるローリングハッシュ というアルゴリズムを、東大の院試問題(東京大学大学院情報理工学系研究科コンピュータ科学専攻 の 2020年度 専門科目I 問題3)をもとに紹介します。
問題のPDFは以下になります。
この問題はローリングハッシュが題材になっているものの、アルゴリズムを事前に知らなくても解けるようになっており、むしろこの問題を通してローリングハッシュを理解することができます。その意味で、非常に教育的な出題と言えますし、これからローリングハッシュを知りたいという方にも有益な問題なのではないかと思います。
では問題を見ていきましょう。
過去問の解答は公開されていないため、ここに書いた解説は公式のものではない点にはくれぐれもご注意ください。
問題文[1]
いろいろ記号が出てきました。整理してみましょう。
文字列 s s s について
s s s の長さ: l ( s ) l(s) l ( s )
s s s の i i i 番目の文字: s [ i ] s[i] s [ i ]
s s s の最初の i i i 文字を除いて得られる文字列: s + i ( 0 ≤ i < l ( s ) ) s + i \ (0 \leq i < l(s)) s + i ( 0 ≤ i < l ( s ) )
文字 c c c について
c c c に N N N 以下の正整数を対応づける関数: n u m v a l ( c ) numval(c) n u m v a l ( c )
(例えば文字コードを想像してみれば良いでしょう。)
また、問題 FIND の説明も読んでみましょう。これは文字列検索の説明になります。例えば s = P R O B L E M , p = O B L s = \mathrm{PROBLEM}, p = \mathrm{OBL} s = P R O B L E M , p = O B L の場合,
マッチせず
マッチせず
マッチ!
となります。マッチしたとき、
s [ 2 + 0 ] = p [ 0 ] = O s [ 2 + 1 ] = p [ 1 ] = B s [ 2 + 2 ] = p [ 2 ] = L
s[2 + 0] = p[0] = \mathrm{O} \\
s[2 + 1] = p[1] = \mathrm{B} \\
s[2 + 2] = p[2] = \mathrm{L}
s [ 2 + 0 ] = p [ 0 ] = O s [ 2 + 1 ] = p [ 1 ] = B s [ 2 + 2 ] = p [ 2 ] = L
となり、i = 2 i = 2 i = 2 がこの場合の FIND の解となります。
p = O B E p = \mathrm{OBE} p = O B E の場合、s = P R O B L E M s = \mathrm{PROBLEM} s = P R O B L E M のどこにもマッチしないので i = − 1 i = -1 i = − 1 が解となります。
問題文[2]
さて、問題 FIND を解くアルゴリズム S が提示されました。このアルゴリズムが何をしているかを考えてみましょう。
for ループの中では e q ( s + i , p ) eq(s+i, p) e q ( s + i , p ) という関数が 1 1 1 を返すまで毎回呼び出されています。問題文を読み解くと e q ( s + i , p ) eq(s+i, p) e q ( s + i , p ) は s + i s+i s + i の最初の l ( p ) l(p) l ( p ) 文字が p p p と一致すれば 1 1 1 を返す関数だと分かります。
ここで s + i s+i s + i は s s s の最初の i i i 文字を除いて得られる文字列でした。つまり、アルゴリズム S は
s s s の最初の 0 0 0 文字を除いて得られる文字列 を p p p と比較....
s s s の最初の 1 1 1 文字を除いて得られる文字列 を p p p と比較....
s s s の最初の 2 2 2 文字を除いて得られる文字列 を p p p と比較....
という流れであり、これは先ほどの
マッチせず
マッチせず
マッチ!
と同じ、愚直な検索であることが分かります。
問題文[3]
(1) はアルゴリズム S の最悪計算量を求めるという問題です。最も時間がかかるのは当然ながら p p p が s s s のどこにもマッチせず、for 文のループが最後まで回ってしまう場合です。
問題文の冒頭より、1回の文字列比較 e q ( s + i , p ) eq(s+i, p) e q ( s + i , p ) につき、O ( l ( p ) ) O(l(p)) O ( l ( p ) ) の時間計算量がかかります。for 文のループ回数は l ( s ) − l ( p ) + 1 l(s) - l(p) + 1 l ( s ) − l ( p ) + 1 回, オーダー記法だと O ( l ( s ) − l ( p ) ) O(l(s) - l(p)) O ( l ( s ) − l ( p ) ) なので、全体では
O ( l ( p ) ( l ( s ) − l ( p ) ) )
O\bigg(l(p)(l(s) - l(p))\bigg)
O ( l ( p ) ( l ( s ) − l ( p ) ) )
となります。(O ( l ( s ) l ( p ) ) O(l(s)l(p)) O ( l ( s ) l ( p ) ) と書いてしまっても良い気がします)
問題文[4]
ようやくハッシュが登場しました。
元の式をじっと見てもよく分からないので、まずは具体例で考えてみましょう。s = A B C D E F s = \mathrm{ABCDEF} s = A B C D E F とします。また、
n u m v a l ( A ) = 1 n u m v a l ( B ) = 2 n u m v a l ( C ) = 3 . . .
numval(A) = 1 \\
numval(B) = 2 \\
numval(C) = 3 \\
...
n u m v a l ( A ) = 1 n u m v a l ( B ) = 2 n u m v a l ( C ) = 3 . . .
としてみます。
イメージしやすいように、m = 4 m = 4 m = 4 の場合で考えてみましょう。上記の式は
h ( s , 4 ) = ( n u m v a l ( s [ 0 ] ) ⋅ d 3 + n u m v a l ( s [ 1 ] ) ⋅ d 2 + n u m v a l ( s [ 2 ] ) ⋅ d 1 + n u m v a l ( s [ 3 ] ) ) m o d q = ( 1 ⋅ d 3 + 2 ⋅ d 2 + 3 ⋅ d 1 + 4 ) m o d q
h(s, 4) \\
= \Bigg( numval(s[0]) \cdot d^3 + numval(s[1]) \cdot d^2 + numval(s[2]) \cdot d^1 + numval(s[3]) \Bigg) \mod q \\
= \Bigg( 1 \cdot d^3 + 2 \cdot d^2 + 3 \cdot d^1 + 4 \Bigg) \mod q \\
h ( s , 4 ) = ( n u m v a l ( s [ 0 ] ) ⋅ d 3 + n u m v a l ( s [ 1 ] ) ⋅ d 2 + n u m v a l ( s [ 2 ] ) ⋅ d 1 + n u m v a l ( s [ 3 ] ) ) m o d q = ( 1 ⋅ d 3 + 2 ⋅ d 2 + 3 ⋅ d 1 + 4 ) m o d q
と展開できます。例えば d = 3 , q = 10 d=3, q=10 d = 3 , q = 1 0 とすれば,
( 1 ⋅ 3 3 + 2 ⋅ 3 2 + 3 ⋅ 3 1 + 4 ) m o d 10 = 8
( 1 \cdot 3^3 + 2 \cdot 3^2 + 3 \cdot 3^1 + 4 ) \mod 10 = 8
( 1 ⋅ 3 3 + 2 ⋅ 3 2 + 3 ⋅ 3 1 + 4 ) m o d 1 0 = 8
ですね。
問題文[5]
(2) です。h ( s + i , m ) h(s+i, m) h ( s + i , m ) から h ( s + i + 1 , m ) h(s+i+1, m) h ( s + i + 1 , m ) を求めるとはどういうことか、式を整理して考えてみましょう。
s + i s+i s + i は s s s の最初の i i i 文字を除いて得られる文字列でしたので、s s s の最初の i i i 文字を除いて得られる文字列の最初の m m m 文字のハッシュから、s s s の最初の i + 1 i+1 i + 1 文字を除いて得られる文字列の最初の m m m 文字のハッシュを求めるということになります。しかも、O ( 1 ) O(1) O ( 1 ) で求められる必要があります。
問題文の冒頭の設定を整理しておくと、O ( 1 ) O(1) O ( 1 ) でできるのは
s s s と i i i から s + i s+i s + i を求める演算
c c c から n u m v a l ( c ) numval(c) n u m v a l ( c ) を求める演算
整数の加算・乗算・剰余
でした。
では、先ほどの具体例をもう一度振り返ってみましょう。
h ( s , 4 ) = ( n u m v a l ( s [ 0 ] ) ⋅ d 3 + n u m v a l ( s [ 1 ] ) ⋅ d 2 + n u m v a l ( s [ 2 ] ) ⋅ d 1 + n u m v a l ( s [ 3 ] ) ) m o d q
h(s, 4) \\
= \Bigg( numval(s[0]) \cdot d^3 + numval(s[1]) \cdot d^2 + numval(s[2]) \cdot d^1 + numval(s[3]) \Bigg) \mod q
h ( s , 4 ) = ( n u m v a l ( s [ 0 ] ) ⋅ d 3 + n u m v a l ( s [ 1 ] ) ⋅ d 2 + n u m v a l ( s [ 2 ] ) ⋅ d 1 + n u m v a l ( s [ 3 ] ) ) m o d q
でした。ここから、h ( s + 1 , 4 ) h(s + 1, 4) h ( s + 1 , 4 ) を O ( 1 ) O(1) O ( 1 ) で求められる必要があります。
h ( s + 1 , 4 ) = ( n u m v a l ( ( s + 1 ) [ 0 ] ) ⋅ d 3 + n u m v a l ( ( s + 1 ) [ 1 ] ) ⋅ d 2 + n u m v a l ( ( s + 1 ) [ 2 ] ) ⋅ d 1 + n u m v a l ( ( s + 1 ) [ 3 ] ) ) m o d q
h(s + 1, 4) \\
= \Bigg( numval((s + 1)[0]) \cdot d^3 + numval((s + 1)[1]) \cdot d^2 + \\ numval((s + 1)[2]) \cdot d^1 + numval((s + 1)[3]) \Bigg) \mod q
h ( s + 1 , 4 ) = ( n u m v a l ( ( s + 1 ) [ 0 ] ) ⋅ d 3 + n u m v a l ( ( s + 1 ) [ 1 ] ) ⋅ d 2 + n u m v a l ( ( s + 1 ) [ 2 ] ) ⋅ d 1 + n u m v a l ( ( s + 1 ) [ 3 ] ) ) m o d q
さらに s + 1 s + 1 s + 1 は s s s の先頭文字を取り除いた文字列なので、例えば ( s + 1 ) [ 0 ] = s [ 1 ] (s + 1)[0] = s[1] ( s + 1 ) [ 0 ] = s [ 1 ] です。これに気をつけると、
h ( s + 1 , 4 ) = ( n u m v a l ( s [ 1 ] ) ⋅ d 3 + n u m v a l ( s [ 2 ] ) ⋅ d 2 + n u m v a l ( s [ 3 ] ) ⋅ d 1 + n u m v a l ( s [ 4 ] ) ) m o d q
h(s + 1, 4) \\
= \Bigg( numval(s[1]) \cdot d^3 + numval(s[2]) \cdot d^2 + numval(s[3]) \cdot d^1 + numval(s[4]) \Bigg) \mod q
h ( s + 1 , 4 ) = ( n u m v a l ( s [ 1 ] ) ⋅ d 3 + n u m v a l ( s [ 2 ] ) ⋅ d 2 + n u m v a l ( s [ 3 ] ) ⋅ d 1 + n u m v a l ( s [ 4 ] ) ) m o d q
となります。
ここまで来ると、h ( s + 1 , 4 ) h(s + 1, 4) h ( s + 1 , 4 ) の形が h ( s , 4 ) h(s, 4) h ( s , 4 ) とほとんど変わらないことに気づくのではないでしょうか。
加算・減算・乗算は剰余に閉じている ので、h ( s , 4 ) h(s, 4) h ( s , 4 ) から h ( s + 1 , 4 ) h(s + 1, 4) h ( s + 1 , 4 ) を求めるには、
h ( s , 4 ) h(s, 4) h ( s , 4 ) から n u m v a l ( s [ 0 ] ) ⋅ d 3 numval(s[0]) \cdot d^3 n u m v a l ( s [ 0 ] ) ⋅ d 3 を引き、
それに d d d を掛け、
それに n u m v a l ( s [ 4 ] ) numval(s[4]) n u m v a l ( s [ 4 ] ) を足し、
最後に m o d q \mod q m o d q をとる
という操作をすれば OK です。
一般の
h ( s + i , m ) = ( n u m v a l ( ( s + i ) [ 0 ] ) ⋅ d m − 1 + n u m v a l ( ( s + i ) [ 1 ] ) ⋅ d m − 2 + . . . + n u m v a l ( ( s + i ) [ m − 1 ] ) ) m o d q = ( n u m v a l ( s [ i ] ) ⋅ d m − 1 + n u m v a l ( s [ i + 1 ] ) ⋅ d m − 2 + . . . + n u m v a l ( s [ i + m − 1 ] ) ) m o d q
h(s + i, m) \\
= \Bigg( numval((s+i)[0]) \cdot d^{m-1} + numval((s+i)[1]) \cdot d^{m-2} + \\ ... + numval((s+i)[m-1]) \Bigg) \mod q \\
= \Bigg( numval(s[i]) \cdot d^{m-1} + numval(s[i+1]) \cdot d^{m-2} + \\ ... + numval(s[i+m-1]) \Bigg) \mod q
h ( s + i , m ) = ( n u m v a l ( ( s + i ) [ 0 ] ) ⋅ d m − 1 + n u m v a l ( ( s + i ) [ 1 ] ) ⋅ d m − 2 + . . . + n u m v a l ( ( s + i ) [ m − 1 ] ) ) m o d q = ( n u m v a l ( s [ i ] ) ⋅ d m − 1 + n u m v a l ( s [ i + 1 ] ) ⋅ d m − 2 + . . . + n u m v a l ( s [ i + m − 1 ] ) ) m o d q
についても、
h ′ = h ( s + i , m ) h' = h(s + i, m) h ′ = h ( s + i , m ) から n u m v a l ( s [ i ] ) ⋅ d m − 1 = n u m v a l ( s [ i ] ) ⋅ d m numval(s[i]) \cdot d^{m-1} = numval(s[i]) \cdot d_m n u m v a l ( s [ i ] ) ⋅ d m − 1 = n u m v a l ( s [ i ] ) ⋅ d m を引き、
それに d d d を掛け、
それに n u m v a l ( s [ i + m ] ) numval(s[i+m]) n u m v a l ( s [ i + m ] ) を足し、
最後に m o d q \mod q m o d q をとる
という操作で h ( s + i + 1 , m ) h(s + i + 1, m) h ( s + i + 1 , m ) が求まります。擬似コードで書くと以下のようになるでしょう。
tmp = numval ( s[ i] ) ;
tmp = tmp * d_m;
ans = h' + tmp * ( - 1 ) ;
ans = ans * d;
ans = ans + numval ( s[ i+ m] ) ;
ans = ans % q;
return ans;
numval()
, +
, *
, %
は O ( 1 ) O(1) O ( 1 ) でできるので、これで大丈夫です。
問題文[6]
さて、(3) は本題の、ローリングハッシュによる文字列検索アルゴリズムについて考える問題です。2つの問題が与えられていることに気をつけてください。
まず、前半の問題についてですが、(2) の誘導を活かすことを考えましょう。h ( s + i , l ( p ) ) h(s+i, l(p)) h ( s + i , l ( p ) ) とは、s s s の最初の i i i 文字を取り除いた文字列の最初の l ( p ) l(p) l ( p ) 文字のハッシュ値を指しますが、これを各 i i i について個別に求める必要はありません。h ( s , l ( p ) ) h(s, l(p)) h ( s , l ( p ) ) を求めれば、O ( 1 ) O(1) O ( 1 ) で h ( s + 1 , l ( p ) ) h(s + 1, l(p)) h ( s + 1 , l ( p ) ) が求まり、さらに O ( 1 ) O(1) O ( 1 ) で h ( s + 2 , l ( p ) ) h(s + 2, l(p)) h ( s + 2 , l ( p ) ) が求まり... という具合に計算できます。
したがって、h ( p , l ( p ) ) = h ( s + i , l ( p ) ) h(p, l(p)) = h(s+i, l(p)) h ( p , l ( p ) ) = h ( s + i , l ( p ) ) となる最小の非負整数 i i i を求めるアルゴリズムを擬似コードで書くと、以下のようになるでしょう。
h(p, l(p)) をあらかじめ計算
h(s, l(p)) をあらかじめ計算
d_l(p) をあらかじめ計算
if (h(p, l(p)) == h(s, l(p)))
return 0;
for (i = 0; i <= l(s)-l(p)-1; i++)
h(s+i, l(p)) と d_l(p) から h(s+i+1, l(p)) を O(1) で計算
if (h(p, l(p)) == h(s+i+1, l(p)))
return i+1;
return -1;
ハッシュはただの整数値ですから、ハッシュ同士の比較は当然 O ( 1 ) O(1) O ( 1 ) でできます。したがって、for 文の部分の計算量は O ( l ( s ) − l ( p ) ) O(l(s)-l(p)) O ( l ( s ) − l ( p ) ) です。
残るは、
h ( p , l ( p ) ) h(p, l(p)) h ( p , l ( p ) ) をあらかじめ計算
h ( s , l ( p ) ) h(s, l(p)) h ( s , l ( p ) ) をあらかじめ計算
d l ( p ) = d l ( p ) − 1 d_{l(p)} = d^{l(p) - 1} d l ( p ) = d l ( p ) − 1 をあらかじめ計算
これらの部分の計算量を解析する必要があります。
まず、乗算が O ( 1 ) O(1) O ( 1 ) でできることから、d l ( p ) = d l ( p ) − 1 d_{l(p)} = d^{l(p) - 1} d l ( p ) = d l ( p ) − 1 が O ( l ( p ) ) O(l(p)) O ( l ( p ) ) で計算できるのは明らかです。
また、l ( p ) l(p) l ( p ) 文字の文字列のハッシュも、加算と乗算を交互に繰り返すことで O ( l ( p ) ) O(l(p)) O ( l ( p ) ) で計算できます。例えば h ( s , l ( p ) ) h(s, l(p)) h ( s , l ( p ) ) は
ans = numval ( s[ 0 ] ) ;
for ( i = 1 ; i <= l ( p) - 1 ; i++ )
ans = ans * d;
ans = ans + numval ( s[ i] ) ;
ans = ans % q;
return ans;
というように求まります。h ( p , l ( p ) ) h(p, l(p)) h ( p , l ( p ) ) の計算も同様に行えば OK です。
以上より、for 文以外の部分の計算量は O ( l ( p ) ) O(l(p)) O ( l ( p ) ) であり、全体を通して計算量が O ( l ( s ) + l ( p ) ) O(l(s) + l(p)) O ( l ( s ) + l ( p ) ) であることが言えます。なので、これが求めるべきアルゴリズム H 0 H_0 H 0 です。
次に後半の問題ですが、これもちょっと考えればわかることです。このアルゴリズム H 0 H_0 H 0 が問題 FIND を解くには、「ハッシュ値が一致することで文字列が一致する」と言えること、言い換えれば「異なる文字列に異なるハッシュの整数値が対応する」ことが前提になっています。
逆に言えば、異なる文字列に同じハッシュ値が対応してしまう場合は、前提が破綻してしまいます。極端な例ですが、剰余 Mod の q q q を q = 1 q = 1 q = 1 としてしまうと、任意の文字列のハッシュ値が 0 0 0 になるので、任意の文字列が同じことになってしまいます。これではアルゴリズム H 0 H_0 H 0 で問題 FIND を解けるわけがありません。
よって、この問題の回答としては 「ハッシュが衝突する場合」 などとしておけばよいでしょう。
ハッシュが衝突しない限り、アルゴリズム H 0 H_0 H 0 は問題 FIND を解けます。そして、アルゴリズム S が O ( l ( s ) l ( p ) ) O(l(s)l(p)) O ( l ( s ) l ( p ) ) であったのに対し、アルゴリズム H 0 H_0 H 0 は O ( l ( s ) + l ( p ) ) O(l(s) + l(p)) O ( l ( s ) + l ( p ) ) なので、確かに高速になっています!
例えば l ( s ) = 1 0 7 , l ( p ) = 1 0 3 l(s) = 10^7, l(p) = 10^3 l ( s ) = 1 0 7 , l ( p ) = 1 0 3 程度としたとき、前者は 1 0 10 10^{10} 1 0 1 0 程度ですが、後者は 1 0 7 10^7 1 0 7 程度と見積もれます。
いかがでしたでしょうか。ローリングハッシュのアルゴリズムや計算量、ハッシュ衝突問題なども含めて、網羅的に学ぶことができましたね。
この問題はコンピュータ科学専攻の過去問の中では、やや易〜標準 位の難易度だと思うので、「こんなの簡単じゃん!」と思った方は、ぜひ東京大学大学院情報理工学系研究科コンピュータ科学専攻を受験 してみましょう!