この記事を訪れていただいてありがとうございます．
こういう記事を書くのは初めてなのでどうぞお手柔らかに．
さて今回の内容は**「Lyndon 文字列入門」**です．
キーワードは以下の通りです．
- Lyndon 文字列（Lyndon word）
- Lyndon 分解（Lyndon factorization）
- Lyndon 分解アルゴリズム
この記事で紹介する Lyndon 文字列は，文字列の辞書式順序を用いて定義されるものです．みなさんがごく自然にイメージするあの辞書式順序です．念のため以下では辞書式順序を例とともに簡単に説明しています．
文字列の辞書式順序
（注：非常にゆるく記述しています．）
アルファベット（文字の集合）上の全順序が与えられたとき，2つの文字列の辞書式順序は以下のようなルールによって定義される．
- 2つの文字列を先頭から比較し，初めて異なる文字間の順序が2つの文字列の順序に等しい．
- 長さの異なる2つの文字列について，一方が他方の接頭辞となっている場合，接頭辞となっている文字列の順序は小さい．
例.
アルファベット $Σ = $ {a, b, c}，$Σ$ 上の全順序 a $\prec$ b $\prec$ c としたとき，
- aabc $\prec$ aacb （ルール 1 より，3 文字目の順序で決定）
- aab $\prec$ aababc （ルール 2 より決定）
- aab $=$ aab （自明）
Lyndon 文字列
まずは Lyndon 文字列が何者であるかをずばり定義します．
よく使われる定義を2つ紹介します．
| Lyndon 文字列の定義 1 |
|---|
| 文字列 $\mathit{λ}$ が Lyndon 文字列であるとは，$\mathit{λ}$ の空文字列でない任意の真の接尾辞より $\mathit{λ}$ の辞書式順序が小さいことである． |
ここでの "$\mathit{λ}$ の真の接尾辞"とは，$\mathit{λ}$ の接尾辞のうち $\mathit{λ}$ 以外の接尾辞を指します．つまり，$\mathit{λ} =$ aabab について，$\mathit{λ}$ の真の接尾辞の集合 $=$ {abab, bab, ab, b}．
さて，$\mathit{λ}$ = ababb は babb, abb, bb, b のいずれの接尾辞よりも辞書式順序が小さいことがわかります（a $\prec$ b とする）．よって，ababb は Lyndon 文字列です．では，$\mathit{λ}$ = abbabb はどうでしょうか．確認してみると，abbabb $\succ$ abb となってしまいましたね．よって，abbabb は Lyndon 文字列ではありません．
| Lyndon 文字列の定義 2 |
|---|
| 文字列 $\mathit{λ}$ が Lyndon 文字列であるとは，$\mathit{λ}$ の任意の真の循環文字列より $\mathit{λ}$ の辞書式順序が小さいことである． |
ここでの "$\mathit{λ}$ の真の循環文字列"とは，以下の例のように一文字ずつずらして得られる文字列のことです．例えば $\mathit{λ} =$ aabab について，$\mathit{λ}$ の真の循環文字列の集合 = {ababa, babaa, abaab, baaba} となります．（"真の" というのはおおよそ「自明なもの = 自分自身」を考えないという意味です）．
$\mathit{λ} =$ ababb は ababa, babaa, abaab, baaba のいずれの循環文字列よりも辞書式順序が小さいことがわかります（a $\prec$ b とする）．よって，ababb は Lyndon 文字列です．では，$\mathit{λ} =$ abbabb はどうでしょうか．$\mathit{λ}$ の真の循環文字列の集合は {bbabba, babbab, abbabb, bbabba, babbab} です．ここで注意したいのは，文字列として同じであっても，循環により得られるのであれば異なるものとしています．すると，abbabb = abbabb となるので．abbabb は Lyndon 文字列ではありません．
さて，2つの定義を紹介しましたが，どちらも定義というからには同値な定義となっています．この証明は難しくないのでぜひ挑戦してみてください．
Exercise 1
上記の Lyndon 文字列の2つの定義が同値であることを示せ．
今回は特に利用しませんが，Lyndon 文字列を用いた議論で多用される簡単な性質を一つ紹介します．
| Lyndon 文字列の性質 |
|---|
| Lyndon 文字列は，ボーダーを持たない． |
文字列 $\mathit{x}$ が文字列 $\mathit{w}$ のボーダー（border）であるとは，$\mathit{x}$ が $\mathit{w}$ の真の接頭辞かつ接尾辞であることである．たとえば，$\mathit{w} =$ abababa について a, aba, ababa はいずれも $\mathit{w}$ のボーダーです．
もし文字列 $\mathit{w}$ がボーダー $\mathit{x}$ を持つならば，$\mathit{x}$ は $\mathit{w}$ の真の接尾辞かつ真の接頭辞であるので，定義 1 に照らし合わせると，$\mathit{w} \succ \mathit{x}$ となり，$\mathit{w}$ は Lyndon 文字列でないことがわかります．
では，Lyndon 文字列についてわかったかどうかを確認してみましょう．下の文字列はそれぞれ Lyndon 文字列でしょうか．
- apple
- orange
- string
- stringologist
- lyndon
正解がすぐに見えないように少し余談をはさみます．
Lyndon 文字列の登場は 1954年に遡り，Roger C. Lyndon の論文です．
Roger Lyndon は数学者であり，この Lyndon 文字列の概念は代数学の世界で登場しました．Lyndon 文字列（Lyndon word）という名前についてですが，最初から呼ばれているわけではなく，後にそう呼ばれるようになりました（当時は standard lexicographic sequence とか regular word とか呼ばれていたそうです）．
ちなみにかの有名な Knuth 本（Donald E. Knuth 著 "The Art of Computer Programming"）では，primary word として紹介されています．
さて話はさらにそれていきますが，この記事が投稿された 12月18日はなんの日か知っているでしょうか？そう，Roger Lyndon 先生の誕生日です！しかも 1917年のお生まれなので今年は生誕 100 周年です．このような日に日本語記事がほとんどない Lyndon 文字列について投稿できるなんてなんと素晴らしいことでしょう．この続きもぜひ読んでいってください．
では先程の問題の答えにいきましょう．正解は....，アルファベットの全順序を与えていないのでわかりませんね．オーソドックスに a $\prec$ b $\prec \ldots \prec$ z としておけば，Lyndon 文字列は 1 番のみですね．
その気になれば，4 番以外が Lyndon 文字列となる全順序が存在します．4 番はボーダーを持つのでどんな順序を考えても Lyndon 文字列になりませんね．
Exercise 2
1, 2, 3, 5 の文字列がすべて Lyndon 文字列であるような全順序を与えよ．
ちなみに，任意の文字列の集合に対して，集合中の文字列がすべて Lyndon 文字列であるような全順序が存在するかどうか判定し，存在するならば全順序を与える問題に対して，入力文字列の長さの総和に線形な時間で計算できるアルゴリズムが存在します．後に紹介する Lyndon 分解のアルゴリズムを理解するとわかるかもしれません．
Exercise 3
文字列の集合が与えられたとき，集合中の文字列がすべて Lyndon 文字列であるような全順序が存在するかどうか判定し，存在するならば全順序を与える線形時間アルゴリズムを考えよ．
Lyndon 文字列の紹介はここまでにして，ここからは Lyndon 文字列関連で有名な Lyndon 分解と呼ばれる文字列の分解について紹介していきます．
Lyndon 分解
文字列の分解
まずはじめに文字列の分解について説明します．文字列の分解とは，何らかのルール（ルールがないこともルールの一つ）に基いた部分文字列の列（この部分文字列を連結すると元の文字列になる）のことをいいます．特にそれぞれの部分文字列のことを factor と呼ぶこととします．
例えば，次のルールを満たす分解を考えてみましょう．
- 各 factor は，文字 a で始まる．
- 出現位置が右の factor であるほど，先頭から続く a の数が多くなる．
文字列 abaababaabaaabbaaaabbaa に対するこの分解は，
ab|aababaab|aaabb|aaaabbaa
が一つ挙げられます（この場合複数の分解が存在しています）．
上記の例のように分解のルールには，
- factor 自身が満たすべきルール
- factor が相互に満たすべきルール
があるといえます．ここでは，前者を"ローカルルール"，後者を"グローバルルール"と呼ぶことにします．
Lyndon 分解
さて，いよいよ Lyndon 分解に進んでいきましょう．Lyndon 分解も 2 種類のルールから定義できます．まず，ローカルルールはご想像どおり，
- 各 factor は Lyndon 文字列である．
です．このルールのみを適用した分解を考えてみましょう．文字列 abaababaababaaabbaaaabbaa に対する分解は，
ab|aababaabab|aaab|b|aaaab|b|a|a
が挙げられますね．もちろんこの場合も複数の分解が存在しています．極端な話，長さ 1 の文字列は自明に Lyndon 文字列であるので，
a|b|a|a|b|a|b|a|a|b|a|b|a|a|a|...
も一つです．
この分解はまだ，いわゆる Lyndon 分解ではありません．そこで，このグローバルルールを追加してみましょう．
- Lyndon 文字列（factor）の列は，辞書式順序が非増加の列である．
急に複雑になったかのように見えますが，落ち着いて例を見ながら確認してみましょう．同じ文字列についてこの分解は，
ab|aabab|aabab|aaabb|aaaabb|a|a
となります．
- ab, aabab, aabab, aaabb, aaaabb, a, a はそれぞれ Lyndon 文字列．
- ab $\succ$ aabab $=$ aabab $\succ$ aaabb $\succ$ aaaabb $\succ$ a $=$ a を満たす．
2 つのルールを満たしていますね．これが Lyndon 分解です．
ここでちゃんと定義をしてみます．
| Lyndon 分解の定義 |
|---|
| 文字列の列 $w_1, \ldots, w_m$ が文字列 $w$ の Lyndon 分解であるとは，$w_i (1 \leq i \leq m)$ は Lyndon 文字列であり，$w_1 \succ \ldots \succ w_m$ であり，$w = w_1 \cdots w_m$ を満たすことである． |
参考までに Lyndon 分解は，1958年に Chen, Fox, Lyndon らによって提案されています．著者"全員"の頭文字を取って，CFL 分解 と呼ばれることもあります．
さてご理解いただけたでしょうか．ところで上の文字列について Lyndon 分解は他には存在するのでしょうか．答えは NO です．どんな文字列を考えても NO です．
| Lyndon 分解の性質 1 |
|---|
| 任意の文字列 $w$ について，$w$ の Lyndon 分解は，一意に定まる． |
この定義からこの性質，どう感じますか？
私くらいになると，一意に定まるのは当たり前だろうくらいに感じてしまいますが，きっと初めて聞くと（いい意味で）気持ち悪いでしょう．
この Lyndon 分解の一意性は，次の性質が担保しています．
| Lyndon 分解の性質 2 |
|---|
| 文字列 $w$ の Lyndon 分解 $w_1, \ldots, w_m$ について，$w_1$ は $w$ の Lyndon 文字列である接頭辞のうち最長の接頭辞である． |
文字列 $w$ の Lyndon 分解 $w_1, \ldots, w_m$ について，定義より $w_2, \ldots, w_m$ は文字列 $w_2 \cdots w_m$ の Lyndon 分解であるので，最長という一意性から，分解が一意に定まることがわかります．この性質は，ここまでの知識で十分証明できると思いますので挑戦してみてください．
Exercise 4
Lyndon 分解の性質 2 を証明せよ．
Lyndon 分解アルゴリズム
もちろん気になるのはどうやってこの分解を計算するんだということですよね．
いろいろな方法が知られていますが，ここでは最もエレガントな線形時間アルゴリズムを紹介します．このアルゴリズムは以下の論文で紹介されているもので，著者の名前を借りて，Duval の（Lyndon 分解）アルゴリズムと呼んでいます．
Jean P. Duval, "Factorizing Words over an Ordered Alphabet", Journal of Algorithms, 1983
アルゴリズムのポイント
このアルゴリズムは，Lyndon 分解の性質 2 により，最長の Lyndon 文字列を繰り返し計算していくことで Lyndon 分解を計算します．ではその最長の Lyndon 文字列をどのように計算することができるのか．そのすべては次の補題に詰め込まれています．
| 最長 Lyndon 文字列補題 [Duval, 1978] |
|---|
| $x$ を Lyndon 文字列とし，文字列 $w$ のある接頭辞が $x^k x' (k \geq 1)$（$x'$ は $x$ の真の接頭辞） で表されかつ，$x[\mid x' \mid +1] \neq w[\mid x^k x' \mid +1]$ であるとき，次のいずれかが成り立つ．1) $x[\mid x' \mid +1] \prec w[\mid x^k x' \mid +1]$ のとき，$w[1..\mid x^k x' \mid +1]$ は Lyndon 文字列．2) $x[\mid x' \mid +1] \succ w[\mid x^k x' \mid +1]$ のとき，$x$ は $w$ の Lyndon 文字列である接頭辞のうち最長の接頭辞． |
補題をじっと眺める必要はありません．次の図を見ながら状況を説明していきます．
文字列 $w$ があります．
文字列 $x$ は，$w$ の接頭辞であり Lyndon 文字列です．
この $x$ が 1 回以上繰り返し出現しています．
このあとに $x$ は出現しておらず，$x$ の接頭辞が続いています（空文字列でも可）．
ここに出現する最も長い $x$ の接頭辞を $x'$ とします．
以降，この $x'$ の次続いている文字 $w[|x^k x'| +1]$ を $c$ とします．
条件を満たす最も長い接頭辞を $x'$ としているので，$x[|x'|+1] \neq c$ が成り立っています．
するとこの補題が言っているのは，
- $x[|x'|+1] \prec c$ ならば，$w[1..|x^k x'|+1]$ は Lyndon 文字列です．
- $x[|x'|+1] \succ c$ ならば，$w[x]$ は $w$ の Lyndon 文字列である接頭辞のうち最長の接頭辞です．
次に具体例で確認してみましょう．
次の図は 1 つ目のケースに対応した例です．
接頭辞 $x =$ ababc が Lyndon 文字列であるとわかっています．
この ababc は 3 回と 3 文字続いています．
ababc が途切れた原因は，ababc の 4 文字目の b と 途切れたところの文字 c です．
この 2 つの辞書式順序は，b $\prec$ c なので，接頭辞 $($ababc$)^3$abac は Lyndon 文字列であることがわかります．
次の図は 2 つ目のケースに対応した例です．
接頭辞 $x =$ ababc が Lyndon 文字列であるとわかっています．
この ababc は 3 回と 3 文字続いています．
ababc が途切れた原因は，ababc の 4 文字目の b と 途切れたところの文字 a です．
この 2 つの辞書式順序は，b $\succ$ a なので，接頭辞 $ababc$ は Lyndon 文字列である最長の接頭辞であることがわかります．
この補題の正しさの証明はここでは省略することにします（Lyndon 文字列の定義 1 から導くことが出来ます）．
Exercise 5
補題を証明せよ．
アルゴリズムの動作
それではアルゴリズムの話をしていきましょう．とは言っても上の補題の状況を計算していくだけです．
- Lyndon 文字列である接頭辞 $x$ がどこまで繰り返しているかを計算する．
- 補題の 1 つ目のケースより，$x$ より長い Lyndon 文字列である接頭辞が存在するとき，その接頭辞を $x$ として 1 に戻る．
- 補題の 2 つ目のケースより，$x$ が Lyndon 文字列である最長の接頭辞である．
というわけで，以下に最長の Lyndon 文字列（Lyndon 分解の最初の factor）を計算するアルゴリズムを示しています．
擬似コード（Longest Lyndon Prefix）
$i \leftarrow 1;$
$j \leftarrow 2;$
while($w[i] \preceq w[j]$ && $j < |w|$){
if($w[i] = w[j]$){
$i \leftarrow i+1;$
$j \leftarrow j+1;$
}else{ // $w[i] \prec w[j]$
$i \leftarrow 0;$
$j \leftarrow j+1;$
}
}
output $(j-i, \lfloor \frac{j-1}{j-i} \rfloor)$ // 最長 Lyndon 文字列の長さと繰り返しの数
具体例（文字列 aabaabbaaa）とともに追っていきます．
長さ 1 の文字列は自明に Lyndon 文字列であるので，$x = $ a としてスタートします．$x$ がどこまで繰り返しているかは，先頭位置（$i = 1$）と $x$ の終了位置の次の位置（$j = i + 1$）から文字が等しい間，一文字ずつ右にスライドしていけばわかります（コードの if 文）．この例では，$(i, j) = (2, 3)$ となったところで，$x = $ a が 2 回繰り返していることがわかります．
これは補題の状況を表しているので次に 2 つの文字の辞書式順序の比較です．ここでは，$x[i] = $ a $\prec$ b $= x[j]$ より，1 つ目のケースにあたり，$x[1..3] = $ aab が Lyndon 文字列であることがわかります．
より長い Lyndon 文字列 $x = $ aab が見つかったので，これがどこまで繰り返しているかを，$(i, j) = (1, 4)$ として同様に計算します．この例では，$(i, j) = (4, 7)$ となったところで，$x = $ aab が 2 回繰り返していることがわかります．これも補題の 1 つ目のケースにあたり，$x[1..7] = $ aabaabb が Lyndon 文字列であることがわかります．
さらに長い Lyndon 文字列 $x = $ aabaabb が見つかったので，これがどこまで繰り返しているかを，$(i, j) = (1, 8)$ として同様に計算します．この例では，$(i, j) = (3, 10)$ となったところで，$x$ が 1 回と 2 文字分繰り返していることがわかります．さてこれは $x[i] = $ b $\succ$ a $= x[j]$ より（else 文），補題の 2 つ目のケースにあたり，$x[1..7] = $ aabaabb が Lyndon 文字列である最長の接頭辞であることがわかりました．
最後に出力ですが，この例では aabaabb の情報（ここでは長さ 7）を出力すれば良いわけですが，次のような例（文字列 aababaababaababaaab）を考えてみましょう．この文字列に対してアルゴリズムを実行すると，$(i, j) = (13, 18)$ で停止します（このとき $x = $ aabab）．もちろん最長の Lyndon 文字列だけであれば長さ 5 を出力すれば良いのですが，実はこの aabab はあと 2 回繰り返していて，これらはそれぞれ入力文字列の Lyndon 分解の factor になることがわかっているので（ちなみにこの入力文字列の Lyndon 分解は aabab|aabab|aabab|aaab），Lyndon 分解を計算したいのであれば一緒に出力しておきたいところです（この文字列に対する最後の状態を下の図に示す）．ちなみに $x$ の長さは $j - i$ であることは自明ですね．あとは繰り返しの数ですが，これは長さ $j$ の文字列中に長さ $j - i$ がいくつ収まっているかということなので，$\lfloor \frac{j}{j-i} \rfloor$ 回ですね．
アルゴリズムの計算量
最後に計算量を簡単に説明します．このアルゴリズムは文字の比較を行っているだけなのでその回数を見積もります．
$j$ の動きに注目しましょう．最長の Lyndon 文字列を見つけるまでの各操作で，$j$ はかならず 1 ずつ増加し，減少することはありません．最長の Lyndon 文字列を $x$ とすると $j = |x^k x'|+1$ で終了し，$x^k$ の情報が出力されます．つまり，$x$ の長さ以上の文字列が出力され，$j$ は最長 Lyndon 文字列長の 2 倍以下になりますね．出力された文字列はそれ以降の計算の対象とはならないので，$j$ の増加量は高々文字列長 n の 2 倍である．つまり，Lyndon 分解アルゴリズム全体の文字の比較回数は高々 2n となり，計算時間は $O(n)$ 時間となります．一方で領域は，入力文字列を除けば $i, j$ の情報だけなので $O(1)$ 追加領域となっています．
以上がアルゴリズムの説明でした．線形時間はもちろんのこと領域もほとんど使わない，しかも簡単な文字比較のみの実にエレガントなアルゴリズムでしたね．
まとめ
今回の記事はここまでです．最後に，5 つの Execise に取り組んでいる人はいないとは思いますが，また別の記事で解説しようと思います（反応が良いほど早く書きます）．ここまでありがとうございました．