Rozdział 5: Generacja ciągów Lyndona i ciągów de Bruijna

Uwaga: Dla uproszczenia rozważamy tylko teksty binarne.

Uogólnienie pozostawiamy jako proste ćwiczenie.

Słowem (ciągiem) de Bruijna rzędu $n$ jest ciąg binarny o długości $2^{n}$, w którym (traktowanym jako ciąg cykliczny) każdy ciąg binarny długości $n$ wystęuje dokładnie raz.

Zdefiniujmy pierwiastek pierwotny $y$ jako najkrótszy prefiks $z$ słowa $y$ taki, że $y$ jest naturalną potęgą $z$.

Słowa Lyndona sa zwartymi reprezentacjami liniowymi słów cyklicznych. Dla słowa $x$ niech $y$ będzie minimalnym cyklicznym przesunięciem $x$. Wtedy pierwiastek pierwotny $z$ słowa $y$ jest słowem Lyndona. Słowo jest ciągiem Lyndona wtedy i tylko wtedy, gdy może powstać w ten sposób.

Definicja równoważna: słowo jest Lyndona jeśli jest leksykograficznie najmniejsze ze swoich przesunięć cyklicznych (równoważnie, najmniejsze ze swoich sufiksów).

Dla danego $n$ przez $ext(x,\, n)$ oznaczmy rozszerzenie okresowe słowa $x$ do długości $n$, oraz przez $LastZero(x)$ oznaczamy najdłuższy prefiks słowa $x$ kończący się zerem. Na przykład
$$ext(00111,\, 13) = 00111\;00111\;001, \quad LastZero(0010111)=0010.$$

Następujący algorytm generuje wszytkie słowa Lyndona o długości co najwyżej $n$:

Algorytm Fredricksen-Maiorana

x := '0';
writeln(x);
while x != '1' do begin
	x := LastZero(ext(x, n));
	Zamień ostatni symbol x na jedynkę;
	writeln(x);
end;

Niech $ L_0 < L_1 < L_2 < \ldots < L_s $ będzie leksykograficznie posortowaną sekwencją wszystkich binarnych słów Lyndona o długości będącej dzielnikiem $n$. Niech $\mathcal{L}_n$ oznacza konkatenację
$$\mathcal{L}_n\ = \ L_0\cdot L_1\cdot L_2\cdot L_3 \cdot \ldots \cdot L_s$$

Przykład: Dla $n=4$ algorym FM wygeneruje:
$$0 \quad 0001 \quad 001 \quad 0011 \quad 01 \quad 011 \quad 0111 \quad 1 $$
$$\mathcal{L}_4 = 0 \quad 0001 \quad 0011 \quad 01 \quad 0111 \quad 1 $$

Powiemy, że $L_k$ jest "małe" gdy $|L_k| < n$, w przeciwnym przypadku jest "duże". Z poprawności algorytmu FM (Fredricksena-Maiorany) wynikają własności:

$L_0=0,\ L_1=0^{n-1}1,\ L_{s-1}=01^{n-1},\ L_s=1$;
jeśli $L_k=\beta\alpha$ oraz $\alpha$ zawiera zero, to $\beta$ jest prefiksem $L_{k+1}$
Jeśli $L_k$ jest małe i $k > 0$ to
- $L_{k-1}$ jest duże;
- $L_{k-1}$ kończy się co najmniej $n - \vert L_k \vert $ jedynkami;
- $L_{k-1}$ jest bezpośrednio wygenerowane przed $L_k$ w algorytmie FM.

Twierdzenie Fredricksena-Maiorany (dla pierwszych $n$)

Przypadek szczególny - rozgrzewka: jeśli $n$ jest liczbą pierwszą, to $\mathcal{L}_n$ zawiera (cyklicznie) każde binarne słowo $x$ długości $n$.

Dowód

Przeprowadźmy dowód rozpatrując kilka przypadków.
Przypadek 1.
Niech $x \in 1^*0^*$. Wtedy $x$ jest podsłowem $L_{s-1}L_sL_0L_1 = 01^n0^n1$. Załóżmy zatem (do końca dowodu), że nie zachodzi przypadek 1. Słowo $x$ jest cyklicznie równoważne pewnemu słowu $L_r$ (równemu minimalnemu cyklicznemu przesunięciu $x$). Wtedy dla pewnych $\alpha$, $\beta$
$$x=\alpha\beta, \quad L_r=\beta\alpha $$
Ustalmy do końca dowodu $\alpha$ i $\beta$.

Przypadek 2.
$\alpha$ zawiera zero. Wtedy $\beta$ jest prefiksem $L_{r+1}$, zatem $x$ jest podsłowem $L_rL_{r+1}$, którego prefiksem jest $\beta\alpha\beta$.

Przypadek 3.
$\alpha\in 1^+$. Załóżmy, że nie zachodzi przypadek 2. Wtedy $\beta \notin 0^+$. Istnieje zatem taki indeks $k$, że $\beta$ jest prefiksem $L_k$, ale $\beta$ nie jest prefiksem $L_{k-1}$. Niech $\gamma$ będzie prefiksem $L_{k-1}$ o długości $\beta$. Zapiszmy $L_{k-1} = \gamma\delta$. Udowodnimy:

Fakt: $\delta \in 1^+.$ Dowód nie wprost. Przypuśćmy, że $\delta$ zawiera 0, wtedy zgodnie z algorytmem Fredricksena-Maiorany następne leksykograficznie słowo Lyndona ma prefiks $\gamma$. Wiemy, że $\beta \neq \gamma$. Natomiast następnym słowem z definicji jest $L_k$, które ma prefiks $\beta\ne \gamma$, o tej samej długości co $\gamma$. Sprzeczność.

Z powyższego faktu wynika, że $\delta = \alpha$, ponieważ są to słowa tej samej długości składające się z samych jedynek. Zatem $x$ jest podsłowem $L_{k-1}L_k$ jako $\delta\beta$, w konsekwencji $x$ jest podsłowem całego słowa $\mathcal{L}_n$. Koniec dowodu.

Twierdzenie Fredricksena-Maiorany (przypadek ogólny, dowolne $n$)

$\mathcal{L}_n$ zawiera (jako słowo cykliczne) każde binarne słowo $x$ długości $n$.

Dowód

Ponownie rozpatrujemy przypadki.

Przypadek 1: $x \in 1^*0^*$. Dowód bez zmian (w stosunku do dowodu przypadku szczególnego). Załóżmy, zatem (do końca dowodu), że nie zachodzi przypadek 1. W przypadkach 2-4 zakładamy, że słowo $x$ jest pierwotne. Zakładamy również, że $x$ nie jest równe żadnemu $L_r$. Wtedy $x$ jest cyklicznie równoważne pewnemu słowu $L_r$ (równemu minimalnemu cyklicznemu przesunięciu $x$). Wtedy dla pewnych niepustych $\alpha,\, \beta$
$$x=\alpha\beta,\ L_r=\beta\alpha$$

Niech $L_k$ będzie leksykograficznie pierwszym dużym słowem o prefiksie $\beta$.

Przypadek 2: $\alpha \notin 1^+$. Dowód bez zmian.
Przypadek 3: $\alpha\in 1^+$, $L_{k-1}$ jest duże. Dowód bez zmian.
Przypadek 4: $\alpha\in 1^+$, $L_{k-1}$ jest małe.

Rozważamy podprzypadki A-C:
(A) $|\beta| < |L_{k-1}|$. Wtedy $L_{k-2}$ jest dużym słowem o prefiksie $\beta$ co przeczy temu, że $L_{k}$ jest najwcześniejsze. Zatem przypadek niemożliwy.
(B) $L_{k-1}$ kończy się co najmniej $|\alpha|$ jedynkami i $\alpha\beta = x$ jest podsłowem $L_{k-1}L_k$.
(C) $L_{k-1}$ kończy się mniej niż $|\alpha|$ jedynkami. Z definicji operacji okresowego rozszerzania wynika, że $L_{k-1}$ jest okresem $\beta$. Jednocześnie $L_{k-2}$ (duże słowo) kończy się co najmniej $n - |L_{k-1}|\geq |\alpha|$ jedynkami (gdyż $|\beta|\geq |L_{k-1}|$ oraz $|\alpha| = n - \beta|$). Zatem $\alpha\beta = x$ jest podsłowem $L_{k-2}L_{k-1}L_k$.

Przypadek 5: Słowo $x$ nie jest pierwotne. Wtedy dla pewnych $k > 1$ oraz $r,\, \alpha,\, \beta$ mamy $x=(\alpha\beta)^k$, $L_r=\beta\alpha$. Jeśli $\alpha\notin 1^+$, to ponieważ słowo $L_r$ jest małe i rozszerzenie okresowe zostaje zaburzone dopiero w ostatnim $\alpha$ to $L_{r+1}$ jest duże i ma prefiks $(\beta\alpha)^{k-1}\beta$. Zatem $x$ jest podsłowem $L_rL_{r+1}$.

Jeśli $\alpha\in 1^+$ to $L_{r-1}$ kończy się na $\alpha$ (ma dostatecznie dużo jedynek), a ponieważ (z rozszerzenia okresowego) $L_{r+1}$ ma prefiks $(\beta\alpha)^{k-1}$ to $x$ jest podsłowem $L_{r-1}L_rL_{r+1}$. Koniec dowodu.

Kilka wzorów

Niech zapisy $Lyn(n),\ Pierw(n)$ oznaczają liczbę binarnych słów Lyndona oraz liczbę słów pierwotnych (nierozkładalnych) długości $n$. Niech $\mu$ będzie funkcją Möbiusa; spełnia ona wzór rekurencyjny:
$$\sum_{d | n} \mu(d) = [n=1].$$
Niech $\phi$ będzie funkcją Eulera (ile jest liczb mniejszych od $n$ względnie pierwszych z $n$). Przyjmujemy $\phi(1)=1$. Użytecznym narzędziem kombinatorycznym jest formuła Möbiusa:
$$\forall_n\ f(n) = \sum_{d | n} g(d) \Rightarrow \forall_n\ g(n) = \sum_{d | n} \mu\left(\frac{n}{d}\right)f(d)$$
Mamy też wzory:
$$2^n = \sum_{d | n} Pierw(d),\quad n = \sum_{d | n} \phi(d).$$

Z formuły inwersyjnej Möbiusa i powyższego wzoru wynikają wzory:
$$Pierw(n) = \sum_{d | n}\mu\left(\frac{n}{d}\right) 2^d, \quad Lyn(n) = \frac{1}{n} \sum_{d | n}\mu\left(\frac{n}{d}\right) 2^d $$
Jeśli $\mathcal{L}_n = L_0\cdot L_1\cdot L_2\cdot L_3 \ldots L_s$ jest rozkładem na słowa Lyndona o długości dzielącej $n$ to oznaczmy $||\mathcal{L}_n|| = s+1$. Inaczej mówiąc $||\mathcal{L}_n||$ jest liczbą słów długości $n$ cyklicznie nierównoważnych (liczba naszyjników binarnych z dokładnością do obrotu). Korzystając z poprzednich wzorów można udowodnić, że:
$$||\mathcal{L}_n|| = \frac{1}{n} \sum_{d | n} \phi\left(\frac{n}{d}\right)2^d.$$
Na przykład:
$$
\begin{gather}
Lyn(6)=9,\; Lyn(3)=2,\; Lyn(2)=1,\; Lyn(1)=2 \\
\vert \mathcal{L}_6 \vert = Lyn(1)+Lyn(2)+Lyn(3)+Lyn(6) = 14 \\
\vert \mathcal{L}_6 \vert = \frac{1}{6}
\left( \phi(1)\cdot 2^6+\phi(2)\cdot 2^3+\phi(3)\cdot 2^2+\phi(6)\cdot 2^1
\right) = \frac{1}{6}\left(1\cdot 2^6+1\cdot 2^3+2\cdot 2^2+2\cdot 2^1 \right)
\\
\end{gather}
$$

Słuszność tych wzorów można prześledzić na przykładzie:
$$
\begin{gather}
\mathcal{L}_6 = 0\ 000001\ 000011\ 000101\ 000111\ 001\ 001011 \
001101\ 001111\ 01\ 010111\ 011\ 011111\ 1
\end{gather}
$$

Teoriografowa metoda generacji ciągów de Bruijna

Chcemy wygenerować ciąg de Bruijna rzędu $n$ nad alfabetem binarnym. Zbudujmy graf (tzw. graf de Bruijna rzędu $n$), którego wierzchołki etykietujemy wszystkimi możliwymi słowami binarnymi długości $n$. Krawędzie etykietujemy symbolami z alfabetu i prowadzimy je według następującej reguły:

Weź wierzchołek opisany $n$-znakową etykietą $\alpha_1 \alpha_2 \ldots \alpha_n$.
Poprowadź krawędź etykietowaną $0$ do wierzchołka $\alpha_2 \ldots \alpha_n 0$.
Poprowadź krawędź etykietowaną $1$ do wierzchołka $\alpha_2 \ldots \alpha_n 1$.

Innymi słowy symbol na krawędzi jest dodawany od prawej strony do słowa reprezentowanego przez bieżący wierzchołek, spychając jednocześnie skrajnie lewy znak. Zatem przejście pewną sekwencją krawędzi $v_1 \stackrel{c_1}{\to} v_2 \stackrel{c_2}{\to} v_3 \ldots v_k$ możemy utożsamić z wygenerowaniem ciągu znaków $\alpha_1 \alpha_2 \ldots \alpha_n c_1 c_2 c_3 \ldots c_{k-1}$, gdzie oczywiście słowo $\alpha_1 \ldots \alpha_n$ stanowi etykietę wierzchołka $v_1$. Takie rozumowanie prowadzi wprost do rozwiązania problemu: w zbudowanym grafie odnajdujemy cykl Hamiltona, z którego bezpośrednio otrzymujemy ciąg de Bruijna. Ponieważ przejście cyklem Hamiltona odwiedzi każdy wierzchołek grafu, więc wygenerowany w ten sposób ciąg będzie zawierał jako podsłowo każde binarne słowo długości $n$. Co prawda nie interesuje nas zawieranie każdego podsłowa w sensie dosłownym, lecz w sensie cykliczności ciągów de Bruijna, ale oznacza to, że w wynikowym ciągu wystarczy wyciąć $n$ pierwszych albo ostatnich znaków. Przykład dla $n = 3$ można zobaczyć na rysunku:

Generacja ciągu de Bruijna poprzez cykl Hamiltona

Generacja ciągu de Bruijna poprzez cykl Hamiltona

Graf de Bruijna dla $n = 3$ nad alfabetem binarnym. Zaznaczono czerwonym kolorem cykl Hamiltona, który (rozpoczęty od wierzchołka o etykiecie $000$) generuje ciąg 00010111000. Po odcięciu $n$ ostatnich znaków mamy 00010111.

Niestety problem znajdowania cyklu Hamiltona jest NP-zupełny. Zauważmy jednak dwie istotne własności grafów de Bruijna:

Grafy de Bruijna posiadają cykl Eulera - do każdego wierzchołka wchodzi tyle samo krawędzi ile wychodzi z niego.
Weźmy graf de Bruijna rzędu $n - 1$ i skonstruujmy dla niego tzw. graf krawędziowy (szczegóły poniżej). Otrzymamy w ten sposób graf de Bruijna rzędu $n$.

Graf krawędziowy dowolnego grafu $G$, to taki graf $G'$, w którym wierzchołkami są krawędzie grafu $G$, natomiast krawędziami jest relacja sąsiedztwa krawędzi w grafie $G$. Tzn. jeśli dwie krawędzie w grafie $G$ mają wspólny wierzchołek, to odpowiadające tym krawędziom wierzchołki w grafie $G'$ połączone są krawędzią. Można łatwo pokazać, że cykl Eulera w pewnym grafie $G$ ma jednoznaczne przełożenie na cykl Hamiltona w jego grafie krawędziowym $G'$.

Z tego wynika, że możemy odnaleźć ciąg de Bruijna używając liniowego algorytmu znajdującego cykl Eulera w grafie rzędu mniejszego o jeden. Zatem dla $n = 3$ operujemy na grafie de Bruijna rzędu $2$. Przykład działania znajduje się na rysunku poniżej.

Generacja ciągu de Bruijna poprzez cykl Eulera

Generacja ciągu de Bruijna poprzez cykl Eulera

Graf de Bruijna rzędu $2$. Cyklowi Hamiltona z poprzedniego rysunku odpowiada cykl Eulera $(00)-(00)-(01)-(10)-(01)-(11)-(11)-(10)-(00)$.

Zastosowanie ciągów de Bruijna do konstrukcji słów o dużej liczbie podsłów

Niech $MaxSub(n)$ oznacza maksymalną liczbę różnych podsłów w słowie binarnym długości $n$. Zachodzi:

Fakt.

$$\forall_{1\leq j\leq n}\ MaxSub(n) \leq 2^{j + 1} - 1 + \binom{n - j + 1}{2}$$

Uzasadnienie

Mamy co nawyżej $ 2^{j+1}-1$ podsłów binarnych długości co najwyżej $j$, oraz co nawyżej ${n-j+1 \choose 2}$ podsłów długości co najmniej $j+1$.

Wystarczy teraz znaleźć takie $j$ dla którego zachodzo równość. Oznaczmy $\gamma_k=2^k+k-1$. Zachodzi następujący fakt:

Fakt.

Jeśli $\gamma_k < n \leq \gamma_{k+1}$ to $MaxSub(n) \geq \; 2^{k+1} - 1 + \binom{n-k+1}{2}$.
Słowo osiągające maksymalną liczbę podsłów można skonstruować w czasie liniowym.

Uzasadnienie

Skonstruujemy słowo spełniające warunki:

wszystkie podsłowa długości $k+1$ w $\pi$ są parami różne, (w konsekwencji wszystkie podsłowa o większej lub równej długości też są różne, jest ich $\binom{n - k + 1}{2}$),
$\pi$ zawiera wszystkie (czyli $2^{k}$) podsłowa binarne długości $k$ (w konsekwencji wszystkie krótsze lub o tej samej długości słowa binarne, jest ich w sumie $2^{k+1}-1$).

Wtedy słowo $\pi$ jest słowem długości $n$ o maksymalnej liczbie podsłów, wynika to z poprzedniego faktu.

Konstrukcja słowa spełniającego powyższe warunki

Weźmy graf de Bruijna $G$ rzędu $k$ - wierzchołkami są wszystkie słowa binarne długości $k$. Znajdujemy w nim ciąg $\pi = a_1a_2 \ldots a_{n-k}$ będący ciągiem etykiet krawędzi pewnego cyklu spełniającego warunki:

cykl ten ma dokładnie $n-k$ krawędzi w $G$,
przechodzi przez każdą krawędź co najwyżej raz,
przechodzi przez każdy wierzchołek $G$ co namniej jeden raz.

Pozostawiamy jako ćwiczenie dowód następującego faktu:

Ciekawy fakt teoriografowy.
Graf de Bruijna rzędu k posiada cykl $\pi$ spełniający warunki (A-C) dla każdego $\gamma_k < n \le \gamma_{k+1}$.

Uliniawiamy $\pi$ dodając na końcu $k$ początkowych liter $\pi$, czyli słowo słowo $a_1 a_2 \ldots a_k$. Słowo $\pi$ ma teraz własności (1) i (2) i jest binarnym słowem długości $n$ maksymalizującym liczbę podsłów.

Przykład

Dla $n=14$ mamy $k=3$, zaczynamy w wierzchołku $000$ w grafie rzędu 3 a następnie konstruujemy cykl spełniający warunki (A-C) o długości $n-k=11$, ciąg etykiet krawędzi cyklu to (patrz rysunek grafu):

$$\pi = 1\;0\;1\;1\;1\;1\;0\;1\;0\;0\;0$$

Dodajemy na końcu 3 początkowe litery i otrzymujemy wynik:

$$\pi = 1\;0\;1\;1\;1\;1\;0\;1\;0\;0\;0\;1\;0\;1$$

Ciąg ten jest binarnym słowem długości 14 o maksymalnej liczbie podsłów wynoszącej
$$2^{k+1} - 1 + \binom{n - k + 1}{2} = 2^4 - 1 + \binom{12}{2} = 15 + 6 \cdot 11 = 81.$$

Informatyka MIMUW