W artykule pt. Słowa pierwsze opublikowanym w aaab
jest słowem Lyndona, ponieważ wszystkie jego pozostałe rotacje, aaba
, abaa
i baaa
,
są od niego większe leksykograficznie.
Innymi przykładami słów Lyndona są aabab
i a
.
Natomiast słowo abaaab
nie jest słowem Lyndona, gdyż jego rotacja aaabab
jest mniejsza leksykograficznie od niego.
Również słowo aabaab
nie jest słowem Lyndona, jako że jego rotacja o 3 litery jest mu równa.
Równoważna definicja słów Lyndona jest taka, że słowa Lyndona są mniejsze od wszystkich swoich właściwych sufiksów (czyli końcowych fragmentów).
Słowa Lyndona nazywa się także słowami pierwszymi, przez analogię do liczb pierwszych; tak jak każda liczba naturalna
przedstawia się jednoznacznie (z dokładnością do kolejności) jako iloczyn liczb
pierwszych, tak każde słowo przedstawia się jednoznacznie jako sklejenie nierosnącego (leksykograficznie) ciągu słów Lyndona.
Przykładowo słowo abaababaabaaba
jest sklejeniem słów Lyndona ab aabab aab aab a
.
Dowód tej własności znalazł się we wspomnianym artykule wraz z innymi podstawowymi faktami dotyczącymi słów Lyndona
oraz ich zadziwiającym związkiem z ciągami de Bruijna.
Po lekturze numeru
Pierwsze z nich dotyczy pojęcia maksymalnych okresowości (ang. runs) w słowie.
Do ich zdefiniowania znów potrzebnych jest kilka pojęć.
Potęgą słowa
Po co rozważać maksymalne okresowości w słowie?
Przede wszystkim reprezentują one każdy możliwy fragment okresowy słowa.
Faktycznie, każdy fragment okresowy albo sam już jest maksymalną okresowością, albo można go maksymalnie rozszerzyć
w obie strony aż do uzyskania maksymalnej okresowości.
W szczególności wszystkie kwadraty (potęgi o wykładniku 2) w słowie, o których pisałem w numerze
Dowód faktu, że liczba maksymalnych okresowości w słowie jest co najwyżej liniowa względem jego długości, został
podany przez Romana Kolpakova i Gregory’ego Kucherova jeszcze w 1999 roku.
Nie potrafili oni jednak podać żadnego ,,sensownego” współczynnika w tej zależności liniowej,
choć na podstawie eksperymentów komputerowych wyszło im, że ten współczynnik powinien być równy po prostu 1.
Przez kolejne lata różni badacze podawali dowody konkretnych oszacowań górnych z coraz to lepszymi stałymi, nierzadko posiłkując się obliczeniami komputerowymi.
W szczególności pierwszą konkretną stałą w oszacowaniu, równą 5, uzyskał Wojciech Rytter w 2006 roku.
W 2011 roku Maxime Crochemore wraz ze współpracownikami, wykorzystując cały klaster komputerów, uzyskał oszacowanie
górne ze współczynnikiem
Ostateczny dowód jest na tyle elementarny, że możemy go w tym miejscu naszkicować.
Główny pomysł polega na tym, żeby każdej maksymalnej okresowości przypisać jedną pozycję w słowie, zwaną pozycją specjalną,
tak aby różnym maksymalnym okresowościom przypisać różne pozycje specjalne.
W ten sposób automatycznie otrzymamy żądane ograniczenie górne.
Aby nie męczyć się z pewnymi szczegółami technicznymi, w tym artykule udowodnimy jedynie słabszą wersję tezy, że każda pozycja specjalna
może być przypisana co najwyżej dwóm maksymalnym okresowościom;
stąd wyniknie, że w słowie o długości
Przyjmiemy także, że rozpatrywane słowo
Pozycje dowolnego słowa
-
jeśli
lub nie istnieje (bo jest ostatnią pozycją w słowie), to jest słowem Lyndona, -
jeśli
, to jest słowem anty-Lyndona.
Przykład przypisania pozycji specjalnych można znaleźć na poniższym rysunku.
Potrzeba chwili, żeby tę definicję przetrawić.
Zacznijmy od uzasadnienia, że każda maksymalna okresowość ma pozycję specjalną.
Jeśli maksymalna okresowość
Wykażemy teraz, że jeśli pozycja b
?
Otóż gdyby tam była litera a
, to maksymalną okresowość można by rozszerzyć o jedną pozycję w prawo, gdyż zachodziłoby
Podobnie można wykazać, że w przypadku [b] fragment b
jest mniejsze od a
; słowa anty-Lyndona są tak naprawdę
słowami Lyndona w tym poniekąd odwróconym porządku leksykograficznym.
Oczywiście na każdej pozycji w słowie zaczyna się jedno najdłuższe słowo Lyndona i jedno najdłuższe słowo anty-Lyndona. Każde z tych słów możemy jednoznacznie rozszerzyć okresowo w lewo i w prawo, z okresem równym jego długości, otrzymując maksymalną okresowość, jeśli tylko okres powtórzy się w niej co najwyżej dwukrotnie. To ostatecznie dowodzi, że każda pozycja jest pozycją specjalną co najwyżej dwóch maksymalnych okresowości, i kończy nasz dowód.
Na koniec warto zaznaczyć, że Bannai i in. w swojej pracy podali nowy, prostszy algorytm wyznaczania maksymalnych okresowości,
a kluczową rolę w tym algorytmie pełni twierdzenie o jednoznacznym rozkładzie słowa na niemalejące słowa Lyndona.
Tablica sufiksowa, obok drzewa sufiksowego, jest jedną z podstawowych struktur danych w algorytmach tekstowych.
Na przykład jeśli mamy tablicę sufiksową słowa
Tablica sufiksowa została wprowadzona w 1990 roku przez Udiego Manbera i Gene’a Myersa.
Korzystając z drzew sufiksowych, można ją skonstruować w czasie liniowym w przypadku słowa nad małym alfabetem.
Jest też znany algorytm autorstwa Juhy Kärkkäinena i Petera Sandersa (2003 r.), który konstruuje ją w czasie liniowym bez użycia drzew sufiksowych.
Tyle w teorii; natomiast praktyka pokazuje, że wszystkie te algorytmy są wolniejsze i bardziej pamięciochłonne niż
algorytm o nazwie DivSufSort autorstwa Yuty Moriego działający w czasie
Ten rozdźwięk między złożonością czasową a czasem działania na praktycznych danych był dość kłopotliwy dla badaczy zajmujących się algorytmami tekstowymi. Dopiero w 2021 roku Nico Bertram i in. w swojej pracy pt. Lyndon Words Accelerate Suffix Sorting przedstawili algorytm poparty poważną analizą teoretyczną i działający w praktyce szybciej niż DivSufSort. Jak tytuł pracy wskazuje, w ich algorytmie istotną rolę pełnią właśnie słowa Lyndona. Algorytm Bertrama i in. ma jednak wciąż ponadliniową złożoność czasową (choć korzysta z liniowej pamięci). Jego złożoność została poprawiona do liniowej, z jednoczesnym dodatkowym przyspieszeniem w praktyce, w pracy autorstwa Jannika Olbricha i in., opublikowanej bardzo niedawno, bo w 2022 roku.