|
De Bruijn-sekvens Inom kombinatoriken är en k-när de Bruijn-sekvens B(k, n) av ordningen n en cyklisk sekvens till ett givet alfabet A med storleken k i vilken varje möjlig delsekvens av längden n uppträder en och endast en gång som på varandra följande tecken. Sekvensen är uppkallad efter den holländske matematikern Nicolaas Govert de Bruijn. Varje B(k, n) har längden kn. Det finns skilda de Bruijn-sekvenser B(k, n). Enligt de Bruijn själv[1] bevisades existensen av de Bruijn-sekvenser för alla ordningar med ovanstående egenskaper först för alfabet med två bokstäver av Camille Flye Sainte-Marie 1894,[2] medan utvidgningen till större alfabeten är ett verk av Tanja van Aardenne-Ehrenfest och honom själv. HistoriaDet tidigaste kända exemplet på en de Bruijn-sekvens kommer från sanskritsprosodi. Sedan Pingalas arbeten har varje möjligt trestavigt mönster av långa och korta vokaler ett namn i form av en konsonant: som "y" för kort-lång-lång och "r" för lång-kort-lång.[3][4] För att komma ihåg dessa namn, används minnesramsan yamātārājabhānasalagām[5], i vilken varje trestavigt mönster inleds av sitt "konsonantnamn": yamātā har alltså ett kort-lång-lång-mönster, rājabhā lång-kort-långt, och så vidare.[6] Denna minnesramsa, som är ekvivalent med en de Bruijn-sekvens av binära tripplar (0111010001 vilket motsvarar 11101000, med tillägg av första och sista tecknet i andra änden 0+11101000+1 för att kompensera för att ramsan är linjär och ej cyklisk), är av okänd ålder men är åtminstone lika gammal som C. P. Browns bok från 1869 om versmått på sanskrit som nämner den.[6][7][8][9] I ett nummer av den franska pusseltidskriften L'Intermédiaire des Mathématiciens ställde A. de Rivière 1894 frågan om det fanns ett sätt att arrangera alla binärsekvenser av längden n i en cirkulär sträng med längden . Problemet löstes, tillsammans med räkningen av antalet lösningar , av C. Flye Sainte-Marie samma år. Detta glömdes dock mer eller mindre bort och Martin (1934) bevisade existensen av sådana cykler för generella storlekar av alfabet andra än två. Slutligen, när K. Posthumus ställde antagandet att antalet binära sekvenser var , bevisade de Bruijn antagandets riktighet 1946, genom vilket problemet blev välkänt.[1] Karl Popper beskriver oberoende dessa binärsekvenser i avsnitt 55 av sin Logik der Forschung (1934) och kallar dem n-Nachwirkungsfreie Alternativen och ger även formeln för deras antal.[10] De Bruijn skriver att "motsvarande räkningsproblem för ett alfabet med σ bokstäver verkar först ha ställts och lösts 1951" och avser då van Aardenne-Ehrenfest, de Bruijn (1951).[1] Exempel
Konstruktionde Bruijn-sekvenser kan konstrueras genom att ta en Hamiltonväg på en n-dimensionell de Bruijn-graf över k tecken (eller, likvärdigt, en Eulercykel på en (n − 1)-dimensionell de Bruijn-graf).[11] En alternativ konstruktion kan åstadkommas genom att konkatenera alla Lyndonord som har en längd som delar n i lexikografisk ordning.[12] Se artikeln om Lyndonord för en närmare beskrivning. de Bruijn-sekvenser kan också skapas genom att använda skiftregister[13] eller via ändliga kroppar.[14] Exempel Mål: Att konstruera en B(2, 4) de Bruijn-sekvens med längden 24 = 16 genom en Eulercykel på den (n − 1 = 4 − 1 = 3) tredimensionella de Bruin-graf som avbildas i figuren till höger. Notera att det leder två riktade kanter från varje hörn (och även två till varje hörn). Varje kant (båge) i denna tredimensionella de Bruijn-graf motsvarar en sekvens på fyra siffror: de tre siffror som betecknar hörnet (noden) som kanten lämnar följda av den siffra som betecknar kanten. Om man från hörnet 000 färdas längs kanten betecknad 1 kommer man till hörnet 001 och får delsekvensen 000+1=0001 i de Bruijn-sekvensen (notera att hörnet 001, nästa utgångspunkt avslutar 0001). Att färdas längs alla sexton kanterna en och endast en gång innebär att man använder sig av varje av de sexton fyrsiffriga sekvenserna exakt en gång vardera, vilket genererar en de Bruijn-sekvens. Om vi till exempel följer en Eulerkrets genom hörnen i denna ordning...
..blir detta våra överlappande, och unika, fyrsiffriga sekvenser:
Vilket resulterar i denna de Bruijn-sekvens:
Nedan markeras med {X X X} hur de åtta hörnen passeras (de unika fyrsiffriga sekvenserna får man genom att lägga till siffran efter hörnet, som ju är vilken kant man följer från hörnet - notera också att man lämnar hörnet den ena gången längs ena kanten och den andra gången längs den andra, till exempel {0 0 0} 0 respektive {0 0 0} 1). {0 0 0} 0 1 1 1 1 0 1 1 0 0 1 0 1
0 {0 0 0} 1 1 1 1 0 1 1 0 0 1 0 1
0 0 {0 0 1} 1 1 1 0 1 1 0 0 1 0 1
0 0 0 {0 1 1} 1 1 0 1 1 0 0 1 0 1
0 0 0 0 {1 1 1} 1 0 1 1 0 0 1 0 1
0 0 0 0 1 {1 1 1} 0 1 1 0 0 1 0 1
0 0 0 0 1 1 {1 1 0} 1 1 0 0 1 0 1
0 0 0 0 1 1 1 {1 0 1} 1 0 0 1 0 1
0 0 0 0 1 1 1 1 {0 1 1} 0 0 1 0 1
0 0 0 0 1 1 1 1 0 {1 1 0} 0 1 0 1
0 0 0 0 1 1 1 1 0 1 {1 0 0} 1 0 1
0 0 0 0 1 1 1 1 0 1 1 {0 0 1} 0 1
0 0 0 0 1 1 1 1 0 1 1 0 {0 1 0} 1
0 0 0 0 1 1 1 1 0 1 1 0 0 {1 0 1}
... 0} 0 0 0 1 1 1 1 0 1 1 0 0 1 {0 1 ...
... 0 0} 0 0 1 1 1 1 0 1 1 0 0 1 0 {1 ...
...och vi är tillbaka vid utgångspunkten. Varje av de åtta tresiffriga sekvenserna (motsvarande de åtta hörnen) förekommer exakt två gånger och varje av de sexton fyrsiffriga sekvenserna (motsvarande de sexton kanterna) förekommer exakt en gång. AlgoritmMan kan bilda en de Bruijn-sekvens genom konkatenering i lexikografisk ordning av alla Lyndonord med en längd som delar n. Det finns en algoritm som genererar alla Lyndonord med längder upp till och med n i lexikografisk ordning. Det första Lyndonordet består endast av alfabetets första tecken (t.ex. strängen "a") och det sista endast av det sista (t.ex. strängen "ö"), så start- och slutpunkterna är givna (från "a" ger algoritmen nästa ("aaa...ab") och från denna får man nästa tills man kommer till "ö"). Om det erhållna Lyndonordets längd delar strängens längd n så läggs den till till den de Bruijn-sekvens man bygger (sålunda "a"&"aaa...ab"&...&"äööö...ö"&"ö"). de Bruijn-torus En de Bruijn-torus är en toroidal array med egenskapen att varje k-när m × n-matris förekommer exakt en gång. (Arrayen behöver inte uttryckas toroidalt utan kan skrivas som en tvådimensionell m × n-matris.) Om n är ett så har vi en de Bruijn-sekvens, och om m=n och jämnt kan man också skapa en torus, annars är det en öppen fråga om de går att tillverka. Den minsta är (4,4;2,2)2 eller B2 som är 4x4 stor och som innehåller alla binära 2×2-matriser (den enda möjliga konfigurationen, bortsett från symmetrioperationer, är avbildad till höger). Nästa är (256,256;4,4)2 som är 256×256 stor och innehåller alla binära 4×4-matriser. AnvändningEn de Bruijn-sekvens kan användas för att förkorta en brute force-attack på en portkodsliknande sekvens som inte har en avslutningstangent ("enter" eller "klar") utan accepterar de sista n inslagna tecknen. Till exempel skulle alla fyrsiffriga decimala koder kunna matas in med 10000+3=10003 tangenttryckningar i stället för att mata in 10000 fyrsiffriga koder (40000 tangenttryckningar). Tecknen i en de Bruijn-sekvens skrivna runt ett cirkulärt föremål kan användas för att analysera dettas riktningsvinkel genom att läsa en sekvens om n tecken som är vända mot en bestämd punkt. Graykoder kan användas på ett liknande sätt. En de Bruijn-torus kan användas för en motsvarande tvådimensionell positionsbestämning. de Bruijn-sekvenser har allmän användning inom experimentell neurovetenskap och psykologi vid undersökning av betydelsen av ordningen av olika stimuli på ett nervsystem,[15] och kan utvecklas specifikt för funktionell magnetresonanstomografi.[16] En de Bruijn-sekvens kan användas för att snabbt hitta index för minsta eller mest signifikanta siffra i ett ord genom bitvisa operationer.[17] Noter
Referenser
Externa länkar
|
