📚

東大院試から学ぶローリングハッシュ

2020/09/27に公開

競技プログラミング

文字列検索で用いられるローリングハッシュというアルゴリズム^[1]を、東大の院試問題（東京大学大学院情報理工学系研究科コンピュータ科学専攻の 2020年度専門科目I 問題3）をもとに紹介します。
問題のPDFは以下になります。^[2]

この問題はローリングハッシュが題材になっているものの、アルゴリズムを事前に知らなくても解けるようになっており、むしろこの問題を通してローリングハッシュを理解することができます。その意味で、非常に教育的な出題と言えますし、これからローリングハッシュを知りたいという方にも有益な問題なのではないかと思います。^[3]

では問題を見ていきましょう。

問題文[１]

いろいろ記号が出てきました。整理してみましょう。

文字列 $s$ について
$s$ の長さ: $l(s)$
$s$ の $i$ 番目の文字: $s[i]$
$s$ の最初の $i$ 文字を除いて得られる文字列: $s + i \ (0 \leq i < l(s))$

文字 $c$ について
$c$ に $N$ 以下の正整数を対応づける関数: $numval(c)$
（例えば文字コードを想像してみれば良いでしょう。）

また、問題 FIND の説明も読んでみましょう。これは文字列検索の説明になります。例えば $s = \mathrm{PROBLEM}, p = \mathrm{OBL}$ の場合,

PROBLEM
OBL

マッチせず

PROBLEM
 OBL

マッチせず

PROBLEM
  OBL

マッチ！

となります。マッチしたとき、

s[2 + 0] = p[0] = \mathrm{O} \\ s[2 + 1] = p[1] = \mathrm{B} \\ s[2 + 2] = p[2] = \mathrm{L}

となり、 $i = 2$ がこの場合の FIND の解となります。
$p = \mathrm{OBE}$ の場合、 $s = \mathrm{PROBLEM}$ のどこにもマッチしないので $i = -1$ が解となります。

問題文[２]

さて、問題 FIND を解くアルゴリズム S が提示されました。このアルゴリズムが何をしているかを考えてみましょう。
for ループの中では $eq(s+i, p)$ という関数が $1$ を返すまで毎回呼び出されています。問題文を読み解くと $eq(s+i, p)$ は $s+i$ の最初の $l(p)$ 文字が $p$ と一致すれば $1$ を返す関数だと分かります。
ここで $s+i$ は $s$ の最初の $i$ 文字を除いて得られる文字列でした。つまり、アルゴリズム S は

$s$ の最初の $0$ 文字を除いて得られる文字列を $p$ と比較....
$s$ の最初の $1$ 文字を除いて得られる文字列を $p$ と比較....
$s$ の最初の $2$ 文字を除いて得られる文字列を $p$ と比較....

という流れであり、これは先ほどの

PROBLEM
OBL

マッチせず

PROBLEM
 OBL

マッチせず

PROBLEM
  OBL

マッチ！

と同じ、愚直な検索であることが分かります。

問題文[３]

(1) はアルゴリズム S の最悪計算量を求めるという問題です。最も時間がかかるのは当然ながら $p$ が $s$ のどこにもマッチせず、for 文のループが最後まで回ってしまう場合です。
問題文の冒頭より、1回の文字列比較 $eq(s+i, p)$ につき、 $O(l(p))$ の時間計算量がかかります。for 文のループ回数は $l(s) - l(p) + 1$ 回, オーダー記法だと $O(l(s) - l(p))$ なので、全体では

O\bigg(l(p)(l(s) - l(p))\bigg)

となります。（ $O(l(s)l(p))$ と書いてしまっても良い気がします）

問題文[４]

ようやくハッシュが登場しました。
元の式をじっと見てもよく分からないので、まずは具体例で考えてみましょう。 $s = \mathrm{ABCDEF}$ とします。また、

numval(A) = 1 \\ numval(B) = 2 \\ numval(C) = 3 \\ ...

としてみます。
イメージしやすいように、 $m = 4$ の場合で考えてみましょう。上記の式は

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 \\

と展開できます。例えば $d=3, q=10$ とすれば,

( 1 \cdot 3^3 + 2 \cdot 3^2 + 3 \cdot 3^1 + 4 ) \mod 10 = 8

ですね。

問題文[５]

(2) です。 $h(s+i, m)$ から $h(s+i+1, m)$ を求めるとはどういうことか、式を整理して考えてみましょう。
$s+i$ は $s$ の最初の $i$ 文字を除いて得られる文字列でしたので、 $s$ の最初の $i$ 文字を除いて得られる文字列の最初の $m$ 文字のハッシュから、 $s$ の最初の $i+1$ 文字を除いて得られる文字列の最初の $m$ 文字のハッシュを求めるということになります。しかも、 $O(1)$ で求められる必要があります。
問題文の冒頭の設定を整理しておくと、 $O(1)$ でできるのは

$s$ と $i$ から $s+i$ を求める演算
$c$ から $numval(c)$ を求める演算
整数の加算・乗算・剰余

でした。

では、先ほどの具体例をもう一度振り返ってみましょう。

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 + 1, 4)$ を $O(1)$ で求められる必要があります。

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

さらに $s + 1$ は $s$ の先頭文字を取り除いた文字列なので、例えば $(s + 1)[0] = s[1]$ です。これに気をつけると、

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)$ の形が $h(s, 4)$ とほとんど変わらないことに気づくのではないでしょうか。
加算・減算・乗算は剰余に閉じている^[4]ので、 $h(s, 4)$ から $h(s + 1, 4)$ を求めるには、

$h(s, 4)$ から $numval(s[0]) \cdot d^3$ を引き、
それに $d$ を掛け、
それに $numval(s[4])$ を足し、
最後に $\mod q$ をとる

という操作をすれば OK です。

一般の

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' = h(s + i, m)$ から $numval(s[i]) \cdot d^{m-1} = numval(s[i]) \cdot d_m$ を引き、
それに $d$ を掛け、
それに $numval(s[i+m])$ を足し、
最後に $\mod q$ をとる

という操作で $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)$ でできるので、これで大丈夫です。

問題文[６]

さて、(3) は本題の、ローリングハッシュによる文字列検索アルゴリズムについて考える問題です。2つの問題が与えられていることに気をつけてください。

まず、前半の問題についてですが、(2) の誘導を活かすことを考えましょう。 $h(s+i, l(p))$ とは、 $s$ の最初の $i$ 文字を取り除いた文字列の最初の $l(p)$ 文字のハッシュ値を指しますが、これを各 $i$ について個別に求める必要はありません。 $h(s, l(p))$ を求めれば、 $O(1)$ で $h(s + 1, l(p))$ が求まり、さらに $O(1)$ で $h(s + 2, l(p))$ が求まり... という具合に計算できます。

したがって、 $h(p, l(p)) = h(s+i, l(p))$ となる最小の非負整数 $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)$ でできます。したがって、for 文の部分の計算量は $O(l(s)-l(p))$ です。
残るは、

$h(p, l(p))$ をあらかじめ計算
$h(s, l(p))$ をあらかじめ計算
$d_{l(p)} = d^{l(p) - 1}$ をあらかじめ計算

これらの部分の計算量を解析する必要があります。

まず、乗算が $O(1)$ でできることから、 $d_{l(p)} = d^{l(p) - 1}$ が $O(l(p))$ で計算できるのは明らかです。
また、 $l(p)$ 文字の文字列のハッシュも、加算と乗算を交互に繰り返すことで $O(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))$ の計算も同様に行えば OK です。

以上より、for 文以外の部分の計算量は $O(l(p))$ であり、全体を通して計算量が $O(l(s) + l(p))$ であることが言えます。なので、これが求めるべきアルゴリズム $H_0$ です。

次に後半の問題ですが、これもちょっと考えればわかることです。このアルゴリズム $H_0$ が問題 FIND を解くには、「ハッシュ値が一致することで文字列が一致する」と言えること、言い換えれば「異なる文字列に異なるハッシュの整数値が対応する」ことが前提になっています。
逆に言えば、異なる文字列に同じハッシュ値が対応してしまう場合は、前提が破綻してしまいます。極端な例ですが、剰余 Mod の $q$ を $q = 1$ としてしまうと、任意の文字列のハッシュ値が $0$ になるので、任意の文字列が同じことになってしまいます。これではアルゴリズム $H_0$ で問題 FIND を解けるわけがありません。
よって、この問題の回答としては 「ハッシュが衝突する場合」 などとしておけばよいでしょう。^[5]

ハッシュが衝突しない限り、アルゴリズム $H_0$ は問題 FIND を解けます。そして、アルゴリズム S が $O(l(s)l(p))$ であったのに対し、アルゴリズム $H_0$ は $O(l(s) + l(p))$ なので、確かに高速になっています！
例えば $l(s) = 10^7, l(p) = 10^3$ 程度としたとき、前者は $10^{10}$ 程度ですが、後者は $10^7$ 程度と見積もれます。

いかがでしたでしょうか。ローリングハッシュのアルゴリズムや計算量、ハッシュ衝突問題なども含めて、網羅的に学ぶことができましたね。
この問題はコンピュータ科学専攻の過去問の中では、やや易〜標準位の難易度^[6]^[7]だと思うので、「こんなの簡単じゃん！」と思った方は、ぜひ東京大学大学院情報理工学系研究科コンピュータ科学専攻を受験してみましょう！

脚注

正確にはラビン-カープ(Rabin-Karp)法というのが今回紹介する文字列検索アルゴリズムの正式名称で、ローリングハッシュはラビン-カープ法で使うハッシュのことを指すのだと思いますが、この記事ではローリングハッシュをアルゴリズムのこととして略記してしまいます。 ↩︎
過去問PDFが非公開になって見れなくなっているかもしれないので、その場合は archive.org 等の魚拓ツールで探してみてください。 ↩︎
もちろん既に競プロなどでローリングハッシュを知っている方にとっては、入試でこの問題を解くのは全くもって余裕だったでしょう。私は今年この専攻に合格したのですが、この過去問を解くまではローリングハッシュを知りませんでした...。ちなみに、コンピュータ科学専攻を受験される方は、文字列検索アルゴリズムとして他にKMPアルゴリズムやBMアルゴリズムも抑えておくと良いでしょう。 ↩︎
これが肌感覚で分かるには、競プロで 1000000007 で割った余りを求める経験がないといけないような気もしますが... ↩︎
競プロの世界では、Mod を $2^{61} - 1$ にすると安全だそうです。参考: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6 ↩︎
実はこの後に小問がもう1つだけあるのですが、ローリングハッシュの紹介からはやや話が逸れるので省きました。 ↩︎
ただし、このような競プロ色の強い問題が出題されるのはごく一部で、入試全体としては "情報数学、数値計算、離散数学、アルゴリズムと計算量、形式言語、論理学、プログラミング言語論、コンピュータアーキテクチャ、オペレーティングシステム、デジタル回路、機械学習" の各分野から幅広く出題されます。合格した私の見解ですが、難問を解ける必要はなく、どの分野についても初歩的な問題をきちんと正答できれば大丈夫だと思います。 ↩︎

問題文[１]

問題文[２]

問題文[３]

問題文[４]

問題文[５]

問題文[６]

Discussion