Słowo Lyndona

Słowo Lyndona lub słowo pierwsze – niepuste słowo spełniające dwa warunkiSzablon:Odn:

jest pierwotne, tzn. nie można go przedstawić w postaci potęgi $u^{k}$ dla $k ⩾ 2$ ^{[uwaga 1]},
wśród swoich cyklicznych obrotów^{[uwaga 2]} jest najmniejsze względem porządku leksykograficznego $≼ .$

Przykładowo dla alfabetu ${a, b}$ można utworzyć 8 słów Lyndona nie dłuższych niż 4 litery ułożonych w porządku leksykograficznym:

a, a a a b, a a b, a a b b, a b, a b b, a b b b, b

Szablon:Odn.

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 Szablon:Odn.
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ż drugieSzablon:Odn.

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 $s = l_{1} l_{2} \dots l_{k},$ a rozkład ten jest jednoznaczny jeśli spełnia warunek monotoniczności $l_{k} ≼ \dots ≼ l_{2} ≼ l_{1}$ Szablon:Odn Szablon:Odn Szablon:Odn. W literaturze wynik takiego podziału jest nazywany rozkładem Lyndona (Szablon:Ang.)Szablon:Odn lub rozkładem standardowym (ang. Szablon:K)Szablon:Odn.
Twierdzenie 4: Rozkład Lyndona można wyznaczyć w czasie liniowym Szablon:Odn.

Historia

Szablon:Wikisłownik Nazwa słowa pochodzi od amerykańskiego matematyka Szablon:Link-interwiki, który je opisał w 1954 wskazując, że są to „standardowe” leksykograficznie ciągiSzablon:Odn Szablon:Odn. Zostały one również zdefiniowane w 1953 przez rosyjskiego matematyka Szablon:Link-interwiki jako poprawne słowa (Szablon:W języku)Szablon:Odn Szablon:Odn.

Efektywny algorytm na dzielenie słów na słowa Lyndona opublikował Jean-Pierre Duval w 1983Szablon:Odn Szablon:Odn, który działał w liniowym czasie i przy stałym zapotrzebowaniu na pamięćSzablon:Odn. 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 skompresowaneSzablon:Odn.

Jean-Pierre Duval opublikował w 1988 również algorytm na generowanie słów Lyndona dla podanego alfabetu i rozmiaru słówSzablon:Odn.

Zastosowanie

Słowa Lyndona są wynikiem zdefiniowania elementów bazy w Szablon:Link-interwiki Szablon:Odn.

W kolejnych latach znalazły zastosowanie w algorytmach tekstowych stosowanych w informatyce i bioinformatyce, a zwłaszcza w sortowaniuSzablon:Odn i analizie sekwencji DNA Szablon:Odn. Znalazły one również zastosowanie w generowaniu ciągów de Bruijna Szablon:Odn.

Zobacz też

Uwagi

Szablon:Uwagi

Przypisy

Szablon:Przypisy

Bibliografia

Linki zewnętrzne

Błąd rozszerzenia cite: Istnieje znacznik <ref> dla grupy o nazwie „uwaga”, ale nie odnaleziono odpowiedniego znacznika <references group="uwaga"/>

[uwaga 1]

[uwaga 2]

Słowo Lyndona

Spis treści

Twierdzenia

Historia

Zastosowanie

Zobacz też

Uwagi

Przypisy

Bibliografia

Linki zewnętrzne

Menu nawigacyjne

Słowo Lyndona

Twierdzenia

Historia

Zastosowanie

Zobacz też

Uwagi

Przypisy

Bibliografia

Linki zewnętrzne

Menu nawigacyjne

Szukaj