周期性補題

はじめに

文字列大好きの皆さんこんにちは．今日は文字列の周期に関する最重要補題である「周期性補題」を紹介します．周期性補題は 1965年の Fine と Wilf による論文¹の中で記されおり，英語では periodicity lemma あるいは Fine and Wilf's Theorem (on words²) などと呼ばれています．周期性補題は文字列の組み合わせ論の成果の中でも特に応用が広く，使いどころで紹介するような適用先は文字列の問題を考えていると稀によく遭遇します³．知っていれば一歩進んだ文字列アルゴリズムを設計できる．．かもしれません．

準備

まず，議論に必要な用語を導入します．

• 文字列 $w$ の長さを $|w|$ と書く．
• 長さ $0$ の文字列を空文字列と呼び $\varepsilon$ と書く．
• $w$ が文字列 $x, y, z$ の連結で表されるとき（すなわち $w = xyz$ のとき），$x, y, z$ をそれぞれ $w$ の接頭辞，部分文字列，接尾辞であるという．$x, y, z$ はそれぞれ空文字列でもよいことに注意．
• 例: $w = \mathtt{abca}$ の場合．$w$ の接頭辞全体の集合は $\{\varepsilon, \mathtt{a}, \mathtt{ab}, \mathtt{abc}, \mathtt{abca} \}$．$w$ の部分文字列全体の集合は $\{\varepsilon, \mathtt{a}, \mathtt{b}, \mathtt{c}, \mathtt{ab}, \mathtt{bc}, \mathtt{ca}, \mathtt{abc}, \mathtt{bca}, \mathtt{abca} \}$．$w$ の接尾辞全体の集合は $\{\varepsilon, \mathtt{a}, \mathtt{ca}, \mathtt{bca}, \mathtt{abca} \}$．
• 文字列 $w$ の $i$ 番目（$1 \le i \le |w|$）の文字を $w[i]$ と書く．
• 文字列 $w$ の位置 $i$ から始まって $j$ で終わる部分文字列（$1 \le i \le j \le |w|$）を $w[i..j]$ と書く．すなわち，$w[i..j] = w[i]w[i+1] \cdots w[j]$．
• 正整数 $p \le |w|$ が文字列 $w$ の周期である $\Longleftrightarrow$ 任意の $i~(1 \le i \le |w| - p)$ に対して $w[i] = w[i + p]$．
• 直感的に言うと，$w$ を周期 $p$ だけ"ずらす"と重なり合う部分が一致する（図1参照）．

弱周期性補題

ここでは，「弱」周期性補題を紹介します．後に紹介する周期性補題より証明が簡単で，ユークリッドの互除法を知っていれば直感的な説明が可能です．ユークリッドの互除法は以下の観察に基づいて二つの整数 $p$ と $q$ の最大公約数 $\mathit{gcd}(p, q)$ を求めるアルゴリズムです．

$p \ge q$ とする．もし，$p$ が $q$ で割り切れるなら，$\mathit{gcd}(p, q) = q$．そうでないなら，$\mathit{gcd}(p, q) = \mathit{gcd}(p - q, q) = \mathit{gcd}(q, p$ mod $q)$．

それでは，弱周期性補題とその証明を紹介します．

[弱周期性補題]
文字列 $w$ が周期 $p, q$ を持つとする．$p + q \le |w|$ ならば $\mathit{gcd}(p, q)$ も $w$ の周期．

まず，一般性を失うことなく，$p \ge q$ とします．もし $p$ が $q$ で割り切れるなら，明らかに $\mathit{gcd}(p, q) = q$ は $w$ の周期なので，以下，$p$ が $q$ で割り切れない場合を考えましょう．

当座の目標は，$p$ mod $q$ が $w$ の周期であることを示すことです．図2を見てみましょう．まず，$q$ は $w$ の周期なので，$w$ は長さ $q$ の接頭辞を繰り返すことで表現できます（最後のブロックは途中で終わっているかもしれません）．また，周期 $p$ の存在により，$w$ を $p$ 右にずらして重なり合う部分は一致します．すなわち，$w[p+1..|w|] = w[1..|w| - p]$ が成り立ちます．ここで，$p+q \le |w|$ なので，$w$ の位置 $p+1$ から始まる長さ $q$ の部分文字列 $w[p+1..p+q]$ を考えることができ，これが $w[1..q]$ と一致することが分かります．$w[p+1..p+q]$ を周期 $q$ でずらしても等しいので左方向に敷き詰めていくと，結局，$w$ を $p$ mod $q$ 右にずらして重なり合う部分が一致することが分かります．これは，$p$ mod $q$ が $w$ の周期であることを意味しています．

さて，$p$ mod $q$ が $w$ の周期であることが示せたので，$q + (p$ mod $q) \le |w|$ より，$q$ と $p$ mod $q$ に対して同じ議論を再帰的に繰り返すことができます．繰り返しは，ユークリッドの互除法で $\mathit{gcd}(p, q)$ が求まるところで停止するので，$\mathit{gcd}(p, q)$ が $w$ の周期であることが分かります．

周期性補題

弱周期性補題が主張しているのは，「周期 $p$ と $q$ の和が $|w|$ と比べ十分に小さければ（$p + q \le |w|$ ならば），$\mathit{gcd}(p, q)$ も周期である」ということでした．さらに先を探求するために鍵となる問いは「これがベストだろうか？」というものです．もっと $p + q$ の条件を緩めてやることはできないでしょうか？周期性補題はこの問いに答えます．

[周期性補題]
文字列 $w$ が周期 $p, q$ を持つとする．$p + q \le |w| + \mathit{gcd}(p, q)$ ならば $\mathit{gcd}(p, q)$ も $w$ の周期．

見てわかるように，"$+ \mathit{gcd}(p, q)$" の分だけ条件が緩和されています．また，以下の例で示されるように，これ以上条件を緩めると $\mathit{gcd}(p, q)$ が必ず周期になると言えないため，この条件がベストです．

$p + q = |w| + \mathit{gcd}(p, q) + 1$ で $\mathit{gcd}(p, q)$ が周期にならない例: $w = \mathtt{abaababaaba}, p = 8, q = 5$ のとき，$p + q = 13$，$|w| + \mathit{gcd}(7, 5) + 1 = 11 + 1 + 1 = 13$ だが $\mathit{gcd}(7, 5) = 1$ は $w$ の周期ではない．

それでは，周期性補題の証明を見ていきましょう．証明は，$(p + q) / \mathit{gcd}(p, q)$ に関する数学的帰納法で行います．$(p + q) / \mathit{gcd}(p, q)$ は $2$ 以上の整数で，$2$ になるのは $p = q$ のときであることに注意してください．

基底である $(p + q) / \mathit{gcd}(p, q) = 2$ の場合は，$\mathit{gcd}(p, q) = p = q$ が $w$ の周期であることは明らかです．また，$p$ が $q$ で割り切れる場合も明らかに成り立つので，以下，そうでない場合を考えます．

$(p + q) / \mathit{gcd}(p, q)$ が $k~(> 2)$ 未満のとき周期性補題が成り立つことを仮定した上で，$k$ でも成り立つことを示します．戦略は，$w$ の長さ $|w| - q$ の接頭辞かつ接尾辞である $x$ に着目し， $x$ が $q$ と $p - q$ を周期に持つことを示すことです．図3を見てください．まず，$x$ を周期 $q$ と $p$ で右にずらしたときの $x$ の重なり具合から，$p - q$ が $x$ の周期であることが見て取れます．$q$ が $x$ の周期であることも一見自明そうですが，$|x| \geq q$ であることを確認しなければいけません．これは，$|x| = |w| - q \geq p - \mathit{gcd}(p, q) \ge p - (p - q) = q$ と式変形することで確認できます．式を追う上でポイントは，周期性補題の $p + q$ に関する条件より $|w| - q \geq p - \mathit{gcd}(p, q)$ が成り立つこと，$p$ が $q$ で割り切れないという仮定より $p - q \ge \mathit{gcd}(p - q, q) = \mathit{gcd}(p, q)$ が成り立つことです．

さて，$p - q$ と $q$ が $x$ の周期であることが分かったので，これらに対して周期性補題が適用できないか見てみましょう．まず，$(p - q) + q= p \le |w| - q + \mathit{gcd}(p, q) = |x| + \mathit{gcd}(p - q, q)$ より，周期性補題の条件を満たしていることが分かります．さらに，$(p - q + q)/\mathit{gcd}(p - q, q) = p / \mathit{gcd}(p, q) < (p + q) / \mathit{gcd}(p, q) = k$ から，帰納法の仮定によって周期性補題が適用できる範囲にあることが分かります．$x$ の周期 $p - q$ と $q$ に対して，周期性補題を適用すると，$\mathit{gcd}(p -q, q) = \mathit{gcd}(p, q)$ が $x$ の周期であり，同時に $w$ の周期であることが分かります（図4参照）．

使いどころ

ここでは，周期性補題をアルゴリズムに応用する際の使いどころを紹介します．よくあるのが，テキスト中のパターンの出現をコンパクトに表現したいときに使うという使い方です⁴．テキスト $w = uv$ とパターン $x$ が与えられたとき，$u$ と $v$ にまたがって出現するパターンの出現位置（開始位置）を保持したいとします．一般に，そのような出現位置は $O(|x|)$ 個存在し得ますが，周期性補題を使うとそれらを定数領域で保持できることが分かります．

パターン $x$ が $u$ と $v$ にまたがって $3$ 回以上出現するとき，パターンの出現位置は $x$ の最小周期 $p_0$ を公差とする等差数列をなす．

図5のように，$x$ が $u$ と $v$ にまたがって $3$ 回以上出現していたとします．最初の出現から最後の出現までの距離を $p$，もう一つの出現までの距離を $q$ とします．$p_0$ と $q$ は $x$ の周期であり $p_0 + q \le (p - q) + q \le |x|$ なので，周期性補題を適用すると，$\mathit{gcd}(p_0, q)$ は $x$ の周期であることが分かります．ここで，$p_0$ は $x$ の最小周期なので，$q$ は $\mathit{gcd}(p_0, q) = p_0$ で割り切れることになります．同様に，$p_0$ と $p - q$ に対して，周期性補題を適用すると $p - q$ も $p_0$ で割り切れることが示せます．結局，最初の出現から最後の出現にかけて，$x$ の長さ $p_0$ の接頭辞を敷き詰めることができるので，パターンの出現位置は $p_0$ を公差とする等差数列をなすことになります（図6参照）．

まとめ

文字列の周期に関する最重要補題である周期性補題を紹介しました．この記事が周期性補題を利用した文字列アルゴリズムを設計する際の役にたったら幸いです．

1. N. J. Fine and H. S. Wilf, "Uniqueness theorem for periodic functions", American Mathematical Society, 16:109-114, 1965. ↩

2. Fine と Wilf の論文では，文字列の周期性だけでなく，周期的な連続関数上で成り立つ性質も述べています． ↩

3. 適用できる問題を頻繁に考える人は頻繁に遭遇するし，そうでない人はあんまり遭遇しないという意味で． ↩

4. 実はこの使用法も含めて多くの場合，弱周期性補題で事足ります．個人的には，周期性補題を使う場面に遭遇したことはありません（KMP アルゴリズムの遅延評価を厳密にしたいときに使うとか見たことがありますが）．つよい周期性補題の使いどころをご存知の方は，コメントいただけると幸いです． ↩