Crochemore-Perrin アルゴリズム

どうも、文字列大好き @hdbn です。「文字列アルゴリズム Advent Calendar 2016」 には間に合いませんでしたが、1月10日は「糸 (string) の日」ということで文字列 (string) アルゴリズムの記事を書くことにしました。この記事では文字列照合アルゴリズムの中で最も美しいアルゴリズムの１つである Crochemore-Perrin のアルゴリズムを紹介します。

アルゴリズムの正しさの証明はほぼ元の論文をなぞっていますが、説明を簡単にするために計算量に影響を与えない範囲でオリジナルのアルゴリズムから少し変更しています。計算量の概念など、アルゴリズムの基礎的な知識があれば読めるような内容にしているつもりですが、分かりにくいところなどあれば補足しますのでコメントください。

それでは文字列の周期性が織り成す不思議ワールドをご堪能ください。

概要

解く問題は以下の文字列照合問題です。

入力: 長さ $n$ のテキスト文字列 $T=T[1..n]$, 長さ $m \leq n$ のパターン文字列 $P=P[1..m]$.
出力: $T$ 中の $P$ の全出現位置の集合 $\mathit{Occ}(T,P) = \{ i \mid T[i..i+m-1] = P, 1 \leq i \leq n-m+1 \}$

誰でも思いつく素朴なアルゴリズム (ナイーブ法) としては、テキストの最初の位置から最後の位置まで順番にパターンをテキストにあてがい、パターンとテキストの対応する文字が一致するかを照合する ($\mathit{pos} = 0,...,n-m$ について $T[\mathit{pos}+1..\mathit{pos}+m] = P[1..m]$ であるかを確認する)、というのがあると思います。このアルゴリズムは最悪の場合でも $O(nm)$ 時間、$O(1)$ 追加領域¹でこの問題を解くことができます。平均的にはそんなに遅くはないのですが、最悪の場合、例えば、$T = a^n, P = a^{m}, m = n/2$ を考えると $\Theta(n^2)$ 時間かかってしまい、基本的には $O(n\log n)$ 時間までしか許容できない文字列アルゴリズマーにはとても不満が残ります。

より効率良くこの問題を解くにはどうすれば良いでしょうか。幾つかのアプローチがありますが、ここでは $P$ が固定で $T$ が色々変わる場合を想定して、$P$ に対して何らかの処理をすることで照合を高速に行うことを考えます²。良く知られているアルゴリズムとしては 1977 年に提案された Knuth-Morris-Pratt のアルゴリズム (KMP-法) があります。KMP 法はパターンを $O(m)$ 時間で前処理しておくことで、照合を $O(n)$ 時間で行うことができます。詳細はここでは書きませんが、KMP 法はナイーブ法のようにパターンをテキストにあてがって文字を照合していきますが、ナイーブ法があるテキスト位置 $\mathit{pos}$ で照合が終わったらすぐ隣のテキスト位置 $\mathit{pos}+1$ で同じことを繰り返すのに対して、KMP 法は次にパターンが出現する可能性のあるテキスト位置まで、位置を「飛ばす」ことで計算量を削減しています。この「幾つ位置を飛ばして良いか」という情報をパターンの照合が何文字成功したかという値に応じて覚えておく必要があるため、KMP 法は $\Theta(m)$ の追加領域を必要とします。

KMP 法も美しいアルゴリズムですが、$\Theta(m)$ の追加領域は勿体無いように思えます。追加領域をなんとか $O(1)$ に押さえたまま、$O(n)$ の照合時間が達成できたら言うことなしですが、そんなことができるのでしょうか？この問いに対しては、Galil と Seiferas が 1983 年に初めて解を与え、その後 Crochemore と Perrin が 1991 年に、より簡潔な美しいアルゴリズムを提案しました³。そう、できるんです、文字列の「周期」を使いこなせればね！

理論的準備

Crochemore-Perrin アルゴリズムは、文字列の組合せ論の中で最も重要な結果の１つであると言われる Critical Factorization Theorem (以下 CFT) という文字列のキモ美しい定理を利用しています。CFT の詳細は別の機会に譲るとして、ここではとりあえず CFT の結果だけを利用することにします。必要最小限の概念を以下に定義します。

長さ $n$ の文字列 $w$ と正整数 $p \leq n$ に対して、すべての $1 \leq i \leq n-p$ について $w[i] = w[i+p]$ が成り立つとき、すなわち $w[1..n-p] = w[p+1..n]$ であるとき、$p$ を $w$ の周期と呼ぶ。文字列 $w$ の最小周期を $\pi(w)$ で表す。

文字列 $w$ の長さも $w$ の周期になります。また、最小周期 $\pi(w)$ の倍数も $w$ の周期であることは簡単にわかると思います。

長さ $n$ の文字列 $w$ と正整数 $q \leq n$, 位置 $1 \leq j < n$ に対して、すべての $\max\{ 1, j-q+1 \} \leq i \leq \min\{ j, n-q\}$ について $w[i] = w[i+q]$ が成り立つとき、$q$ を $w$ の位置 $j$ での局所周期と呼ぶ。

局所周期はちょっと分かりにくいかもしれませんが、要は位置 $j$ において、$w[j-q+1..j] = w[j+1..j+q]$ が成り立つ (ただし、この等式において $j-q+1 < 1$ や $j+q > n$ となる場合、$w$ からはみ出る位置については無視する) ということです。このことから、文字列(全体の)周期はどの位置でも局所周期になることが分かりますが、ある位置の局所周期は必ずしも全体の周期とはなりません。CFT は簡単に言うと『任意の文字列に対して、最小局所周期が最小周期と一致する位置が存在する。』です。証明はしませんが、CFT により、任意の長さ $n$ の文字列 $w$ に対して以下の性質を満たす位置 $1\leq c < \pi(w)$ が存在することが保証されます:

任意の整数 $r \leq \max(c, n-c)$ に対して、$r$ が位置 $c$ での局所周期ならば、$r$ は $w$ の周期である。

このような位置を $w$ の critical position と呼びます。

例えば、文字列 $w = \mathtt{aabaabaa}$ については、$3,6,7$ はそれぞれ周期であり、$\pi(w) = 3$ です。位置 $4$ の局所周期としては、$1,3,6,7$ などがあります。位置 $c = 2$ は $w$ の critical position です。

アルゴリズム

前処理

前処理は、CFT によって存在が保証されているパターン $P$ の critical position $c$, 及び最小周期 $\pi(P)$ を求めます。これらは $O(m)$ 時間、$O(1)$ 領域で求めることができますが、この記事ではとりあえず省略します。(CFT の解説記事を書くことがあれば書こうと思います)

照合

パターン文字列 $P$, $p = \pi(P)$, とし、$P$ の critical position を $c < p$ とします。Crochemore-Perrin アルゴリズムのおおまかな流れはナイーブ法や KMP 法と同様に、最初のテキスト位置からはじめてパターンをテキストにあてがって一致するかどうかを確認し、あてがうテキスト位置を更新する(増やす)ことを繰り返します。テキスト位置 $\mathit{pos}$ にて $T[\mathit{pos}+1..\mathit{pos}+m] = P[1..m]$ であるかを確認する際に、Crochemore-Perrin アルゴリズムはまず パターンの右側 $P[c+1..m]$ について 左から右に 照合し、$P[c+1..m]$ がすべて一致したらその後、パターンの左側 $P[1..c]$ について 右から左に 照合し⁴、左右両側がテキストと一致した場合に $P$ の出現を報告します。$\mathit{pos}$ の更新は、右側の照合の結果に応じて以下の様に行います。

右側 $P[c+1..m]$ を確認する途中で不一致が起きた場合は、不一致が起きたテキスト位置と critical position $c$ が重なるように $\mathit{pos}$ を増やします。

右側 $P[c+1..m]$ に不一致がなかった場合は、左側 $P[1..c]$ の照合の結果に関わらず、$\mathit{pos}$ は $p$ 増やします。この時、新しいテキスト位置では $P$ の先頭 $m-p$ 文字については一致すること (すなわち (更新後の $\mathit{pos}$ で) $T[\mathit{pos}+1..\mathit{pos}+m-p]= P[1..m-p]$ であること) が保証できるため、それを考慮して照合を行います (疑似コード中の変数 $s$)。

アルゴリズムの疑似コードを以下に示します。

Crochemore-Perrin-アルゴリズム(照合部分)

// テキスト T[1..m], パターン P[1..m]
// p : P の最小周期
// c : P の critical position (< p)
// pos: パターンをあてがうテキストの位置
pos = s = 0;
while(pos + m <= n){    // invariant: P[1..s] = T[pos+1..pos+s]
  i = max(c, s) + 1;
  while(i <= m && P[i] == T[pos+i]) i++; // 右側の照合
  if(i <= m){ // 右側は不一致 (P[c+1..m] != T[pos+c+1..pos+m])
    pos += i-c;
    s = 0;
  } else {    // 右側は一致 (P[c+1..m] = T[pos+c+1..pos+m])
    j = c;
    while(j > 0 && P[j] == T[pos+j]) j--; // 左側の照合
    if(j == 0) output match; // T[pos+1..pos+m] = P[1..m]
    pos += p;
    s = m - p;
  }
}

非常に簡単なアルゴリズムで、$T$ と $P$ 以外は幾つかの変数しか使っていないため、必要な追加領域は $O(1)$ であることは分かります。が、なぜこれだけで正しくすべての $T$ 中の $P$ の出現が線形時間で計算されているのかは決して自明では無いと思います。まずはアルゴリズムの出力が正しいことを示し、その上で計算量について解析していきましょう。

正しさ

まずは、ループの最初で不変条件 $P[1..s] = T[\mathit{pos}+1..\mathit{pos}+s]$ が保証されることを確認しましょう。$s$ が $0$ の時は自明です。$s$ が $0$ 以外の値を取るのは、右側の $P[c+1..m]$ がテキストと一致し、左側の照合を行うことになった場合です。図2を見ればほぼ自明ですが、$T[\mathit{pos}+c+1..\mathit{pos}+m] = P[c+1..m]$ が成り立ち、critical position $c < p$ より、$T[\mathit{pos}+p+1..\mathit{pos}+m]$ = $P[p+1..m]$ が成り立ちます。一方で、$p$ が $P$ の周期であることから、$P[1..m-p]=P[p+1..m]$ が成り立ちます。次のステップでのテキスト位置は $\mathit{pos} + p$ となりますが、すると、$T[(\mathit{pos}+p)+1..(\mathit{pos}+p)+m-p] = T[\mathit{pos}+p+1..\mathit{pos}+m] = P[p+1..m] = P[1..m-p]$ が成り立ち、$s = m-p$ としたことで次のステップで不変条件が満たされていることがわかります。

不変条件 $s$ の性質から、このアルゴリズムが右側、左側の両方が一致したときのみに、すなわち、出力される位置は必ず正しく $P$ の出現であることは明らかです。

では、最後にアルゴリズムが $P$ の出現を漏らさずにすべて出力するかどうかを確認しましょう。ある位置 $\mathit{pos}$ でパターンをテキストにあてがったとして、次にパターンが出現する位置を $\mathit{pos'} = \mathit{pos} + d~(d>0)$ としましょう。$\mathit{pos'}$ ではパターンが出現するため、$T[\mathit{pos'}+1..\mathit{pos'}+m] = P[1..m]$ が成り立ちます。このとき、$\mathit{pos}$ における照合の結果に応じて$d$ がどのような値を取り得るかについて、疑似コードの場合分けと同様に、以下の２通りを考えます。

右側が不一致の場合

パターンの右側がテキストと不一致だった場合、位置 $i \leq m$ で不一致だったとします。すなわち、$T[\mathit{pos}+c+1..\mathit{pos}+i-1]=P[c+1..i-1]$ かつ $T[\mathit{pos}+i]\neq P[i]$ が成り立つという状況です。背理法で $d \geq i-c$ を示します。

$d < i- c$ を仮定します。すると、$c+d < i$ より $T[\mathit{pos}+c+1..\mathit{pos}+c+d]$ $= P[c+1..c+d]$ $= P[c-d+1..c]$ (ただし、$P$ からはみ出る範囲は無視する) が成り立つため、$d$ は $P$ の位置 $c$ での局所周期となり、critical position の性質から $P$ の周期でもあることが分かります。このことから、$P[i] = P[i-d]$ が成り立ちますが、一方で、$T[\mathit{pos'}+i-d]$ $=T[\mathit{pos}+i]$ $\neq P[i]$ $=P[i-d]$ となり、$P$ が $\mathit{pos'}=\mathit{pos}+d$ で出現するという最初の仮定と矛盾してしまいます。

以上より、$d \geq i-c$ が言えるため、右側が不一致の場合に $\mathit{pos}$ と $\mathit{pos}+i-c$ の間に $P$ の出現はなく、アルゴリズムは $P$ の出現を漏らさないことが証明できました。

右側が一致していた場合

パターンの右側がテキストと一致したので、$P[c+1..m] = T[\mathit{pos}+c+1..\mathit{pos}+m]$ が成り立ちます。また、$T[\mathit{pos'}+1..\mathit{pos'}+m] = T[\mathit{pos}+d+1..\mathit{pos}+d+m] = P[1..m]$ が成り立ちます。ここで、文字列 $T[\mathit{pos}+c+1..\mathit{pos'}+c]$ を考えると、$T[\mathit{pos}+c+1..\mathit{pos'}+c]$ $= P[c+1..c+d]$ $= P[c-d+1..c]$ (ただし、$P$ からはみ出る範囲は無視する)　が成り立ち、$d$ は位置 $c$ における $P$ の局所周期となります。$c$ は $P$ の critical position であることから、$d$ は $P$ の周期にもなっており、$p$ が最小周期であることから $d \geq p$ でなくてはなりません。

以上より、右側が一致していた場合に $\mathit{pos}$ と $\mathit{pos}+p$ の間に $P$ の出現はなく、アルゴリズムは $P$ の出現を漏らさないことが証明できました。

計算時間

全体で何回の文字比較が何回行われるか、を数えます。

右側の照合

図1を見れば、$P$ の右側が不一致の場合は、不一致のテキスト位置と critical position が重なるように $\mathit{pos}$ を増やすため、次のループで文字比較を行うテキスト位置は不一致位置の隣となり、一度パターンと比較されたテキスト位置はその後比較の対象とはなりません。
また、図2を見れば、右側が一致した場合も、$\mathit{pos}$ を少なくとも $s = m-p$ ずらすことになるため、やはり一度パターンと比較されたテキスト位置はその後比較の対象とはなりません。

以上のことから、パターンの右側の照合においては、テキストの各位置は高々1回しか比較対象とならないため、全体で高々 $n$ 回しか文字比較は行われません。

左側の照合

左側の照合についても、各テキスト位置は高々1回しか比較されません。このことは、図2を見れば、

1. ある $\mathit{pos}$ に対しては $T[\mathit{pos}+1..\mathit{pos}+c]$ の高々 $c < p$ 文字しか比較が行われないこと、更に
2. その比較を行ったとしても、$\mathit{pos}$ が $p$ 増やされるため、その後同じテキスト位置が比較されることがないこと
   から分かります。すなわち、パターンの左側の照合においても、テキストの各位置は高々1回しか比較対象とならないため、全体で高々 $n$ 回しか文字比較は行われません。

以上より、アルゴリズム全体の文字の比較回数は左側、右側合わせて $2n$ 回で抑えられることになり、照合時間が $O(n)$ であることがわかりました。

まとめ

いかがでしたでしょうか。肝心要の CFT の詳細を省略してしまったので、文字列マニアの方には少し物足りなかったかもしれませんが、そうでない方には文字列の周期の凄さを少しでも感じてもらえたら幸いです。

補足

オリジナルのアルゴリズムは、以下の通りで、$s$ を利用して若干文字比較回数を減らしています。

Crochemore-Perrin-アルゴリズム(照合部分)

// テキスト T[1..m], パターン P[1..m]
// p : P の最小周期
// c : P の critical position (< p)
// pos: パターンをあてがうテキストの位置
pos = s = 0;
while(pos + m <= n){    // invariant: P[1..s] = T[pos+1..pos+s]
  i = max(c, s) + 1;
  while(i <= m && P[i] == T[pos+i]) i++; // 右側の照合
  if(i <= m){ // 右側は不一致 (P[c+1..m] != T[pos+c+1..pos+m])
    pos += max(i-c, s-p+1);
    s = 0;
  } else {    // 右側は一致 (P[c+1..m] = T[pos+c+1..pos+m])
    j = c;
    while(j > s && P[j] == T[pos+j]) j--; // 左側の照合
    if(j <= s) output match; // T[pos+1..pos+m] = P[1..m]
    pos += p;
    s = m - p;
  }
}

参考文献

• Donald E. Knuth, James H. Morris, Jr., and Vaughan R. Pratt, "Fast Pattern Matching in Strings", SIAM J. Comput., 6(2), 323–350, 1977. http://dx.doi.org/10.1137/0206024
• Zvi Galil, Joel Seiferas, "Time-space-optimal string matching", J. Comp. Sys. Sci., 26, 280-294, 1983. http://doi.org/10.1016/0022-0000(83)90002-8
• Maxime Crochemore, Dominique Perrin, "Two-way string-matching", J. ACM, 38(3), 650-674, 1991. http://doi.org/10.1145/116825.116845

1. ここでは入力のテキスト $T$ とパターン $P$ の保持にかかる領域以外に追加で必要となる領域のみを考えます。 ↩

2. 逆の $T$ が固定され、$P$ が変化する場合は、$T$ に対して接尾辞配列などの索引構造を作ることが考えられます。 ↩

3. ここでは決定的なアルゴリズムのみを考えています。Karp-Rabin による fingerprint を使う方法もありますが、乱択アルゴリズムになるため、正確性か時間のどちらかが犠牲になります。 ↩

4. 左側の照合については、任意の順序でも計算量に影響は与えません。 ↩