De-Bruijn-Folge

Eine De-Bruijn-Folge $B(k,n)$ ist ein Wort eines Alphabets $A$ mit $k$ Symbolen mit folgender Eigenschaft: Jedes mögliche Wort der Länge $n$ gebildet aus den Symbolen in $A$ taucht als zusammenhängendes Teilwort von $B$ auf, und $B$ ist das kürzeste Wort mit dieser Eigenschaft. $n$ wird die Ordnung von $B$ genannt. Dabei werden verschiedene $B$, die durch zyklische Vertauschung der Symbole auseinander hervorgehen, nicht unterschieden. Eine De-Bruijn-Folge enthält also alle Wörter der Länge $n$ aus $k$ Symbolen (in zusammenhängender Form) genau einmal, wobei das Wort zyklisch betrachtet wird, das heißt die Symbole am Ende dürfen mit denen am Anfang fortgesetzt werden, um ein Teilwort zu bilden.

De-Bruijn-Folge für k = 2 und n = 2.

Hauptteil

De-Bruijn-Folgen existieren für jedes $(n,k)$. Ein Beispiel ist für $k=2$ (Alphabet aus zwei Symbolen, 0 und 1) und $n=2$ die De-Bruijn-Folge $B=(0,0,1,1)$. Hierin kommen alle Wörter der Länge $n=2$ vor: $(0,0),(0,1),(1,1),(1,0)$. Für $n=3$ gibt es zwei mögliche De-Bruijn-Folgen: $(00010111)$ und $(11101000)$. Jede De-Bruijn-Folge hat die Länge $k^{n}$, und es gibt ${\frac {(k!)^{k^{n-1}}}{k^{n}}}$ verschiedene De-Bruijn-Folgen der Ordnung $n$.

De-Bruijn-Folgen lassen sich graphisch als Eulerwege oder Hamiltonpfade eines De-Bruijn-Graphen darstellen. Das sind gerichtete Graphen, deren $k^{n}$ Knoten alle Wörter der Länge $n$ aus dem Alphabet mit $k$ Symbolen darstellen, und deren Knoten verbunden sind, falls diese Wörter überlappen. Für $k=2$ und $n=2$ sind beispielsweise alle Knoten bis auf $(0,0)$ und $(1,1)$ miteinander verbunden.

De-Bruijn-Folgen haben Anwendungen z. B. in der Konstruktion von Kartentricks, in der Kryptographie, Genetik und Bioinformatik (zum Beispiel Pavel Pevzner), bei Telegraphen, fehlerkorrigierenden Codes, Computerspeicher-Hashing und Maschinellem Sehen. Sie lassen sich auch durch Schieberegisterfolgen erzeugen.

Verallgemeinerung

Analoge Objekte können für höhere Dimensionen $d$ definiert und konstruiert werden, speziell der Fall $d=2$ wurde von mehreren Autoren untersucht und dieser heißt De-Bruijn-Torus.

Es ist eine Matrix mit Einträgen aus einem Alphabet (oft nur die beiden Symbole 0 und 1), die alle möglichen $m\times n$ Untermatrizen (auch: Sub-matrizen) genau einmal enthält. Gegenüberliegende Seiten der Matrix werden miteinander identifiziert, deshalb der Name Torus. Für $n=1$ erhält man De-Bruijn-Folgen als Spezialfall.

Wenn man sich auf quadratische, binäre Tori beschränkt, lassen sich $(4,4;2;2)_{2}$ De-Bruijn-Tori, die alle $2\times 2$ binären Untermatrizen enthalten, leicht konstruieren. Der nächste quadratische De-Bruijn-Torus ist $(256,256;4;4)_{2}$ und wurde von W.-C. Shiu induktiv konstruiert.

De-Bruijn-Torus

Höhere De-Bruijn-Tori sind noch nicht bekannt, z. B. für alle $6\times 6$ binären Untermatrizen ($2^{36}=68719476736$ Möglichkeiten) würde man $(262144,262144;6;6)_{2}$ brauchen, das liegt gerade noch im Bereich des Realisierbaren: wenn die Darstellung 0,1 mm per Pixel (Matrixeintrag) benötigt, bräuchte man eine Fläche von ca. 26 Quadratmetern.

Namensgebung

De-Bruijn-Folgen sind nach Nicolaas Govert de Bruijn benannt, der darüber 1946 veröffentlichte und 1951 mit Tatjana van Aardenne-Ehrenfest. De Bruijn wiederum gibt an, dass sie zuerst in Fall k=2 von Camille Flye Sainte-Marie 1894 behandelt wurden. Erste De-Bruijn-Folgen tauchten aber schon im alten Indien auf in Zusammenhang mit Sanskrit-Prosodie. Es gab auch weitere Veröffentlichungen vor De Bruijn, so von M. H. Martin (in Zusammenhang mit Dynamik), I. J. Good (1946), Karl Popper (1934), N. M. Korobov, durch den Telegrapheningenieur Émile Baudot (1888). Unter Zauberern waren sie ebenfalls bekannt, allerdings wurden sie von diesen oft fälschlicherweise Gray-Codes genannt.

Literatur

• Donald Knuth The art of computer programming, 4 A, Teil 1, Addison-Wesley 2011
• Hal Frederickson, Anthony Ralston A survey of full length nonlinear shift register cycle algorithms, SIAM Review, Band 24, 1982, S. 195–221
• Anthony Ralston De Bruijn Sequences - a model example of the interaction of discrete mathematics and computer science, Mathematics Magazine, Band 55, 1982, S. 131–143
• Sherman K. Stein Mathematics, the man made universe, Freeman 1963, Dover 1999, Kapitel 9 (Memory Wheels), mit weiteren historischen Hinweisen
  • Das Kapitel beruht auf einer früheren Version: Sherman K. Stein The mathematician as an explorer, Scientific American, Mai 1961, S. 149–158