Lyndonord

Inom matematiken, inom områdena kombinatorik och datavetenskap, är ett Lyndonord en sträng som kommer före alla andra av sina cykliska permutationer i en lexikografisk ordning. Lyndonord är uppkallade efter den amerikanske matematikern Roger Lyndon som införde dem 1954 som "standard lexicographic sequences" ("lexikografiska standardsekvenser").

Definition

Flera likvärda definitioner är möjliga. Ett k-närt Lyndonord av längden n är en sträng med n tecken över ett alfabet med storleken k och som är det minsta elementet i lexikografisk ordning av alla sina rotationer. Att vara den singulärt minsta rotationen medför att ett Lyndonord avviker från alla icke-triviala rotationer, och sålunda är icke-periodiskt.

Alternativt har ett Lyndonord egenskapen att, närhelst det delas i två delsträngar, den vänstra alltid är lexikografiskt mindre än den högra. Detta innebär att om w är ett Lyndonord och uv är en faktorisering i två delsträngar u och v som underförstått inte är tomma, så är u < v. Denna definition medför att w är ett Lyndonord om och bara om det finns två Lyndonord u och v sådana att u < v och w = uv. Fastän att det kan finnas mer än ett val av u och v med denna egenskap, så finns det ett speciellt val av u och v som kallas standardfaktoriseringen där v är så långt som möjligt.

Enumeration

Lyndonorden över det binära alfabetet med två symboler {0,1}, sorterade först efter längd och sedan i lexikografisk ordning inom varje längdklass bildar en oändlig sekvens som börjar

ε, 0, 1, 01, 001, 011, 0001, 0011, 0111, 00001, 00011, 00101, 00111, 01011, 01111, ...

Här betecknar ε den tomma strängen. Den första sträng som inte ingår är "00" som utesluts därför att den är periodisk (den består av två upprepade delsträngar "0"). Nästa uteslutna sträng är "10", som är aperiodisk, men inte minimal i permutationsklassen, eftersom den kan permuteras cykliskt till "01" som är mindre.

Antalet binära Lyndonord av varje längd, med början på längden noll, bildar heltalsföljden

1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, ... (talföljd A001037 i OEIS).

Lyndonord motsvarar aperiodiska halsbands klassrepresentanter och kan sålunda räknas med halsbandspolynom.

Om vi med representanten menar en cyklisk permutation av en sträng som är lika med den lexikografiskt minsta (ej nödvändigtvis unik, men alla Lyndonord är såklart representanter) ser vi att alla representanter för periodiska strängar av längden n kan bildas genom (upprepad) sammansättning av något Lyndonord med en längd som motsvarar periodiciteten. Till exempel kan 011011, med periodiciteten tre, bildas av 011 upprepat två gånger. Vi får alltså alla periodiska representanter för en sträng av längden n om vi sätter ihop alla Lyndonorden med längderna p_i, där p_i är alla de tal som delar n (inklusive ett).

Exempel: Vi får alla representanter för de periodiska binära strängarna av längden sex om vi upprepar Lyndonorden av längderna 1 (000000 och 111111), 2 (010101) och 3 (001001 och 011011).

Om vi nu konstaterar att det finns kⁿ strängar av längden n och drar ifrån de strängar som kan bildas av representanterna för de periodiska strängarna (d.v.s. antalet Lyndonord av längden p_i multiplicerat med p_i) är återstoden de cykliska permutationerna av Lyndonorden av längden n.

Exempel: De periodiska strängarna av längden sex i föregående exempel ger genom cyklisk permutation en (000000 och 111111), två (010101=101010) repektive tre (001001=010010=100100 och 011011=101101=110110) strängar vardera, sammanlagt 2 ⋅1 + 1 ⋅ 2 + 2 ⋅ 3 = 10 strängar som är periodiska. Totalt finns det 2⁶ = 64 strängar. Drar vi bort de tio som är periodiska återstår 54 aperiodiska strängar som har sex unika cykliska permutationer vardera, d.v.s. representeras av nio olika Lyndonord (000001, 000011, 000111, 000101, 001011, 001101, 010111, 011101 och 0111111).

Följdexempel: För att få antalet lyndonord med längden tolv får vi förutom de tio strängar som är periodiska för längden sex (och bildas av Lyndonorden av längd ett, två respektive tre. dra bort de 9 ⋅ 6 = 54 strängarna som kan bildas av två delsträngar av längden sex och de 3 ⋅4 = 12 som kan bildas av tre delsträngar av längden fyra, det vill säga 2¹² - 76 = 4096 - 76 = 4020 strängar är cykliska permutationer av 4020 / 12 = 335 Lyndonord.

Särskilt ser man att antalet k-nära Lyndonord av längden p är lika med (k^p - k) / p om p är ett primtal, eftersom det bara är de k upprepningarna av samma Lyndonord av längden 1, d.v.s. de som består av samma tecken som är periodiska. Till exempel finns det två binära periodiska strängar av längden fem (00000 och 11111), varför de övriga 2⁵ - 2 = 30 strängarna är de cykliska permutationerna av sex olika Lyndonord (00001, 00011, 00101, 00111, 01101 och 01111).

Kontentan av ovanstående resonemang blir att antalet k-nära Lyndonord av längden n kan uttryckas med

$L_{k}(n)={\frac {1}{n}}\sum _{d|n}\mu (d)k^{n/d}={\frac {1}{n}}\sum _{d|n}\mu (n/d)k^{d}$

där μ(x) är Möbiusfunktionen för x.

Värden

• L_k(1) = k
• L_k(2) = (k² − k)/2
• L_k(3) = (k³ − k)/3
• L_k(4) = (k⁴ − k²)/4
• L_k(5) = (k⁵ − k)/5
• L_k(6) = (k⁶ − k³ − k² + k)/6
• L_k(pⁿ) = (k^pn − k^{pn − 1})/pⁿ om p är ett primtal
• L_αβ(n)=$\sum _{[i,j]=n}$(i,j)L_α(i)L_β(j) där (i,j) är den största gemensamma delaren till i, och j och [i,j] är deras minsta gemensamma multipel.

Generation

Duval (1988) anger en effektiv algoritm för att lista Lyndonorden upp till n med ett givet alfabet av storleken k i lexikografisk ordning. Om w är ett av orden i sekvensen och har längden |w| kan det nästföljande ordet hittas genom följande steg:

1. Repetera tecknen i w så att ett nytt ord x bildas med längden exakt n, där tecknet på plats i i ordet x är detsamma som tecknet på platsen i mod |w| i ordet w. (Det vill säga: sätt samman w med sig själv tills det bildade ordet är minst så långt som n och "klipp bort" det som blir över på högersidan så att din nya sträng har längden n.)
2. Så länge det avslutande tecknet i x är det sista tecknet i alfabetets sorteringsordning, ta bort det så att ett kortare ord bildas. (Om sista tecknet i ditt alfabet är "ö" så ta bort alla "ö" som avslutar strängen.)
3. Byt sedan ut det avslutande tecknet i x med dess efterföljare i alfabetets sorteringsordning. (Om din sträng nu slutar på exempelvis "g" och tecknet efter "g" i ditt alfabet är "h" så ersätt detta "g" med "h".)

Exempel: om alfabetet är (i ordning) {1,2,3,4,5} och w är 15234 och n är 7:

1. x=1523415 (d.v.s. w plus de två första tecknen i w)

2. x=152341 (bort med den avslutande femman som är alfabetets sista bokstav; notera också att detta ord har en mindre representant 115234)

3. x=152342 (ersätt den avslutande ettan med dess efterföljare i ordningen)

Exempel: om alfabetet är (i ordning) {a,b,c} och w är abc och n är 7 får vi:

(Förra Lyndonordet ⇒ steg 1 ⇒ steg 2 ⇒ steg 3, d.v.s. nästa Lyndonord)

abc ⇒ abcabca ⇒ abcabca ⇒ abcabcb

abcabcb ⇒ abcabcb ⇒ abcabcb ⇒ abcabcc

abcabcc ⇒ abcabcc ⇒ abcab ⇒ abcac

abcac ⇒ abcacab ⇒ abcacab ⇒ abcacac

abcacac ⇒ abcacac ⇒ abcaca ⇒ abcacb

etcetera.

I värsta fall är tiden för generation av ett ords efterföljare O(n). Men om man lagrar de producerade orden i en array med längden n och konstruktionen av x från w genomförs genom att lägga till tecken till slutet av w snarare än att göra en ny kopia av w, så är medeltiden för att generera efterföljaren till w (om vi antar att varje ord är lika troligt) konstant. Därför kan följden av alla Lyndonord av längd högst n genereras på en tid som är proportionell mot sekvensens längd. En konstant andel av orden i denna följd har längden exakt n, så samma procedur kan användas för att effektivt generera ord av längden exakt n eller ord vars längd delar n, genom att filtrera bort de genererade ord som inte fyller dessa kriterier.

Standardfaktorisering

Enligt Chen-Fox-Lyndons sats kan varje sträng bildas på ett unikt sätt genom konkatenering (sammansättning) en sekvens av Lyndonord på ett sådant sätt att orden i sekvensen inte ökar lexikografiskt. Det avslutande Lyndonordet i denna sekvens är det lexikografiskt minsta suffixet till den givna strängen. En faktorisering i en inte ökande sekvens av Lyndonord (en så kallad Lyndonfaktorisering) kan åstadkommas i linjär tid (det vill säga T(n)=O(n)). Lyndonfaktorizseringar kan användas som del av en bijektiv variant av Burrows-Wheeler-transformering för datakompression. och i algorimer för digital geometri.

Duval (1983) utvecklade en algoritm för standardfaktorisering som går i linjär tid och konstant rum. Den itererar över en sträng och försöker hitta så långa Lyndonord som möjligt. När den hittar ett lägger den till det i resultatlistan och fortsätter att söka i resten av strängen. Den resulterande listan är den givna strängens standardfaktorisering. En mer formell beskrivning av algoritmen följer nedan.

Med en given sträng S med längden N (strängen består av tecknen S[0]+S[1]+...+S[n-1]) går man igenom följande steg:

1. Låt m vara index för teckenkandidaten till att läggas till i resultatlistan. Initialt är m = 1 (räkning av symboler i en sträng startar från noll, så när vi börjar är S[m]=S[1] strängens andra tecken).
2. Låt k vara index för det tecken som vi jämför med. Initialt är k = 0. När vi börjar är alltså S[k]=S[0] strängens första tecken.
3. Upprepa följande steg så länge k och m är mindre än N.
   1. Om S[k] = S[m]: lägg till S[m] till de för närvarande samlade tecknen. Öka k och m med ett.
   2. Om S[k] < S[m]: om vi lägger till S[m] till de för närvarande samlade tecknen får vi ett Lyndonord. Men vi kan inte lägga till det till listan, eftersom det kan ingå i ett större Lyndonord. Så vi ökar m med ett och sätter k till noll; härigenom kommer nästa tecken att jämföras med strängens första tecken.
   3. Om S[k] > S[m]: lägger vi till S[m] till de hittills samlade tecknen kan det inte bli ett Lyndonord eller en möjlig början på ett. Så, lägg först till m-k insamlade tecken till resultatlistan, ta bort dem från strängen och sätt m=1 och k=0 så att de pekar på det andra respektive första tecknet i strängen.
4. Lägg till det som är kvar av S på resultatlistan.

Exempel

Antag att vi initialt har strängen S=abbabaab. Vi sätter m=1 och k=0 och börjar jämföra:

${\begin{array}{|c|c|c|c|c|}\hline k&S[k]&m&S[m]&S[k]\sim S[m]\\\hline 0&a&1&b&<\\0&a&2&b&<\\0&a&3&a&=\\1&b&4&b&=\\2&b&5&a&>\\\hline \end{array}}$

Här blev S[k] > S[m] så vi tar bort m-k=3 tecken, d.v.s. abb, och lägger detta Lyndonord till vår resultatlista. Av S återstårr nu abaab. Vi återställer m och k, och fortsätter:

${\begin{array}{|c|c|c|c|c|}\hline k&S[k]&m&S[m]&S[k]\sim S[m]\\\hline 0&a&1&b&<\\0&a&2&a&=\\1&b&3&a&>\\\hline \end{array}}$

Här blev S[k] > S[m] så vi tar bort m-k=2 tecken, d.v.s. ab, och lägger detta Lyndonord till vår resultatlista. Av S återstår nu bara aab och vi fortsätter:

${\begin{array}{|c|c|c|c|c|}\hline k&S[k]&m&S[m]&S[k]\sim S[m]\\\hline 0&a&1&a&=\\1&a&2&b&<\\\hline \end{array}}$

S[k] blev inte större än S[m] innan vi nådde ordets slut, så aab är vårt sista Lyndonord. Faktoriseringen av abbabaab är alltså (abb)(ab)(aab), och vi noterar också att abb > ab > aab.

Samband med de Bruijn-sekvenser

Om man konkatenerar alla Lyndonord med en längd som delar ett givet tal n i lexikografisk ordning får man en de Bruijn-sekvens - en cirkulär följd av tecken sådan att varje sekvens med längden n förekommer en och endast en gång som delsekvens i följden.

Exempel: Om man konkatenerar alla de binära Lyndonorden som har en längd som delar fyra i lexikografisk ordning, d.v.s. (0)(0001)(0011)(01)(0111)(1), till en cyklisk sträng får man 0000100110101111, som innehåller alla strängar av längden fyra, d.v.s. {0000, 0001, 0010, ..., 1111}, en och endast en gång.

Denna metod tillsammans med den effektiva generationen av Lyndonord ger ett effektivt sätt att producera en de Bruijn-sekvens inom linjär tid och logaritmiskt rum.

Referenser

• Berstel, Jean; Perrin, Dominique (2007), ”The origins of combinatorics on words”, European Journal of Combinatorics 28 (3): 996–1022, doi:10.1016/j.ejc.2005.07.019, http://www-igm.univ-mlv.fr/~berstel/Articles/2007Origins.pdf .
• Berstel, J.; Pocchiola, M. (1994), ”Average cost of Duval's algorithm for generating Lyndon words”, Theoretical Computer Science 132 (1-2): 415–425, doi:10.1016/0304-3975(94)00013-1, http://www-igm.univ-mlv.fr/~berstel/Articles/1994AverageCostDuval.pdf .
• Brlek, S.; Lachaud, J.-O.; Provençal, X.; Reutenauer, C. (2009), ”Lyndon + Christoffel = digitally convex”, Pattern Recognition 42 (10): 2239–2246, doi:10.1016/j.patcog.2008.11.010, http://www.lama.univ-savoie.fr/~provencal/articles/BrlekLachaudProvencalReutenauer--LyndonChristoffelConvex.pdf .
• Chen, K.-T.; Fox, R. H.; Lyndon, R. C. (1958), ”Free differential calculus. IV. The quotient groups of the lower central series”, Annals of Mathematics, 2nd Ser. 68 (1): 81–95, doi:10.2307/1970044 .
• Donald, Yau (2010), Lambda-rings, World Scientific Publishing Co. Pte. Ltd. Singapore, s. 129, ISBN 981-4299-09-X, http://books.google.se/books?id=d7vKnjxyvxQC&pg=PA129&lpg=PA129#v=onepage&q&f=false 
• Duval, Jean-Pierre (1983), ”Factorizing words over an ordered alphabet”, Journal of Algorithms 4 (4): 363–381, doi:10.1016/0196-6774(83)90017-2 .
• Duval, Jean-Pierre (1988), ”Génération d'une section des classes de conjugaison et arbre des mots de Lyndon de longueur bornée” (på franska), Theoretical Computer Science 60 (3): 255–283, doi:10.1016/0304-3975(88)90113-2 .
• Fredricksen, Harold; Maiorana, James (1978), ”Necklaces of beads in k colors and k-ary de Bruijn sequences”, Discrete Mathematics 23 (3): 207–210, doi:10.1016/0012-365X(78)90002-X .
• Gil, J.; Scott, D. A. (2009), A bijective string sorting transform, http://bijective.dogma.net/00yyy.pdf .
• Kufleitner, Manfred (2009), ”On bijective variants of the Burrows-Wheeler transform”, i Holub, Jan; Žďárek, Jan, Prague Stringology Conference, s. 65–69, http://www.stringology.org/event/2009/p07.html .
• Lothaire, M. (1983), Combinatorics on words, Encyclopedia of Mathematics and its Applications, "17", Addison-Wesley Publishing Co., Reading, Mass., ISBN 978-0-201-13516-9, http://books.google.com/books?id=UV9_3plEr8wC 
• Lyndon, R. C. (1954), ”On Burnside's problem”, Transactions of the American Mathematical Society 77: 202–215, doi:10.2307/1990868 .
• Martin, M. H. (1934), ”A problem in arrangements”, Bulletin of the American Mathematical Society 40 (12): 859–864, doi:10.1090/S0002-9904-1934-05988-3 .
• Melançon, G. (2001), ”Lyndon word”, i Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer, ISBN 978-1556080104 
• Moreau, C. (1872), ”Sur les permutations circulaires distinctes (On distinct circular permutations)” (på franska), Nouvelles annales de mathématiques, journal des candidats aux écoles polytechnique et normale, Sér. 2 11: 309–31, http://www.numdam.org/item?id=NAM_1872_2_11__309_0 
• Ruskey, Frank (2003), Info on necklaces, Lyndon words, De Bruijn sequences, arkiverad från ursprungsadressen den 2006-10-02, https://web.archive.org/web/20061002130346/http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html .
• Schützenberger, M. P. (1965), ”On a factorisation of free monoids”, Proceedings of the American Mathematical Society 16: 21–24, doi:10.2307/2033993 .