Słowo Lyndona

pojęcie matematyczne

Słowo Lyndona lub słowo pierwsze – niepuste słowo spełniające dwa warunki[1]:

  • jest pierwotne, tzn. nie można go przedstawić w postaci potęgi dla [a],
  • wśród swoich cyklicznych obrotów[b] 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:

[2].

Twierdzenia edytuj

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[1].
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[1].

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  [1][3][4]. W literaturze wynik takiego podziału jest nazywany rozkładem Lyndona (ang. Lyndon factorization)[5] lub rozkładem standardowym (ang. standard factorization)[6].
Twierdzenie 4
Rozkład Lyndona można wyznaczyć w czasie liniowym[7].

Historia edytuj

Nazwa słowa pochodzi od amerykańskiego matematyka Rogera Lyndona(inne języki), który je opisał w 1954 wskazując, że są to „standardowe” leksykograficznie ciągi[8][9]. Zostały one również zdefiniowane w 1953 przez rosyjskiego matematyka Anatolija Szyrszowa(inne języki) jako poprawne słowa (ros. правильные слова)[10][11].

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

Jean-Pierre Duval opublikował w 1988 również algorytm na generowanie słów Lyndona dla podanego alfabetu i rozmiaru słów[14].

Zastosowanie edytuj

Słowa Lyndona są wynikiem zdefiniowania elementów bazy w wolnej algebrze Liego(inne języki)[15].

W kolejnych latach znalazły zastosowanie w algorytmach tekstowych stosowanych w informatyce i bioinformatyce, a zwłaszcza w sortowaniu[16] i analizie sekwencji DNA[12]. Znalazły one również zastosowanie w generowaniu ciągów de Bruijna[17].

Zobacz też edytuj

Uwagi edytuj

  1. Potęgowanie słów to ich wielokrotne złożenie, na przykład  [18].
  2. Obrót cykliczny to słowo utworzone przez przeniesienie prefiksu właściwego na koniec słowa[4].

Przypisy edytuj

Bibliografia edytuj

Linki zewnętrzne edytuj