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