Słowo Lyndona lub słowo pierwsze – niepuste słowo spełniające dwa warunki: jest pierwotne, tzn. nie można go przedstawić w postaci potęgi dla , wśród swoich cyklicznych obrotów jest najmniejsze względem porządku leksykograficznego
Przykładowo dla alfabetu można utworzyć 8 słów Lyndona nie dłuższych niż 4 litery ułożonych w porządku leksykograficznym: .
Twierdzenia Twierdzenie 1 Słowo jest słowem Lyndona wtedy i tylko wtedy, gdy jest niepuste i jest wcześniejsze w porządku leksykograficznym niż każdy jego sufiks właściwy. Twierdzenie 2 Słowo jest słowem Lyndona wtedy i tylko wtedy, gdy jest słowem jednoliterowym lub da się przedstawić jako złożenie dwóch słów Lyndona, w którym pierwsze słowo jest wcześniejsze w porządku leksykograficznym niż drugie. Powyższe dwa twierdzenia pozwalają sformułować dwie nowe definicje słowa Lyndona równoważne definicji ze wstępu.
Twierdzenie 3 Dowolne słowo można podzielić na słowa Lyndona a rozkład ten jest jednoznaczny jeśli spełnia warunek monotoniczności . W literaturze wynik takiego podziału jest nazywany rozkładem Lyndona () lub rozkładem standardowym (ang. ). Twierdzenie 4 Rozkład Lyndona można wyznaczyć w czasie liniowym.
Historia
Nazwa słowa pochodzi od amerykańskiego matematyka , który je opisał w 1954 wskazując, że są to „standardowe” leksykograficznie ciągi. Zostały one również zdefiniowane w 1953 przez rosyjskiego matematyka jako poprawne słowa ().
Efektywny algorytm na dzielenie słów na słowa Lyndona opublikował Jean-Pierre Duval w 1983, który działał w liniowym czasie i przy stałym zapotrzebowaniu na pamięć. W kolejnych latach powstawały następne wersje na przykład działające równolegle, korzystające z zewnętrznej pamięci lub obsługujące dane skompresowane.
Jean-Pierre Duval opublikował w 1988 również algorytm na generowanie słów Lyndona dla podanego alfabetu i rozmiaru słów.
Zastosowanie Słowa Lyndona są wynikiem zdefiniowania elementów bazy w .
W kolejnych latach znalazły zastosowanie w algorytmach tekstowych stosowanych w informatyce i bioinformatyce, a zwłaszcza w sortowaniu i analizie sekwencji DNA. Znalazły one również zastosowanie w generowaniu ciągów de Bruijna.
Zobacz też obrót bitowy transformata Burrowsa-Wheelera
Uwagi
Przypisy
Bibliografia
Linki zewnętrzne
Lyndona słowo