Suite de de Bruijn

En mathématiques, et notamment en combinatoire et en informatique théorique, une suite de de Bruijn ou un mot de de Bruijn est un mot circulaire ou collier particulier qui a la propriété de contenir toutes les sous-suites consécutives (ou facteurs) d'une longueur donnée une et une seule fois. Les suites sont nommées d'après le mathématicien néerlandais Nicolaas Govert de Bruijn qui a contribué à leur étude.

Suite de de Bruijn pour

k =2

et

n =2

.

Définition

Formellement une suite de de Bruijn d'ordre n sur k symboles est un mot circulaire ou collier sur un alphabet A à k symboles qui contient toutes les suites de longueur n sur A une et une seule fois. Une telle suite de de Bruijn est de longueur $k n$ . Il existe

{\dfrac {\left(k!\right)^{k^{n-1}}}{k^{n}}}

suites de de Bruijn distinctes sur k symboles et d'ordre n. Comme la suite est considérée circulairement, les quatre mots

0011 0110 1100 1001

définissent la même suite de de Bruijn.

Exemples

Pour un alphabet à deux symboles 0 et 1, il existe deux suites de de Bruijn d'ordre 3, qui sont :

00010111 et 11101000.
La deuxième est l'opposée (0 ↔ 1) de la première (et aussi sa retournée). On ne distingue pas des suites qui se déduisent l'une de l'autre par permutation circulaire. Leur nombre est celui donné par la formule énoncée ci-dessus.

Toujours pour deux symboles, il y a 2048 suites d'ordre 5, parmi lesquelles :

00000100011001010011101011011111 et 00000101001000111110111001101011.

Historique

D'après un rapport interne de Nicolaas Govert de Bruijn[1], l'existence de suites de de Bruijn de tout ordre a été démontré d'abord par Camille Flye Sainte-Marie en 1894[2] pour un alphabet binaire, et dans le cas général par Tatiana van Aardenne-Ehrenfest et lui-même en 1951[3].

Knuth, dans son volume 4A[4], mentionne de très anciens emplois de suites de de Bruijn en Inde. Plus près de nous, en 1894, A. de Rivière posait la question de l'existence d'une suite de de Bruijn binaire dans le journal L'Intermédiaire des Mathématiciens, un journal de mathématiques pour amateurs éclairés, et Camille Flye Sainte-Marie résolvait le problème la même année[1] avec la formule d'énumération $2^{2^{n-1}-n}$ . Ce résultat a été oublié, et Martin 1934 a démontré l'existence de tels mots circulaires sur un alphabet général, avec un algorithme de construction. Enfin, Kees Posthumus (en) a posé le problème en 1944 et a aussi conjecturé la formule $2^{2^{n-1}-n}$ pour des suites binaires. De Bruijn enfin a démontré la conjecture en 1946, et c'est grâce à lui que le problème est devenu universellement connu[1].

Karl Popper a décrit les mêmes objets indépendamment dans un livre paru en 1934[5] où il les appelle shortest random-like sequences (« plus courtes séquences pseudo-aléatoires »).

Constructions

Graphe de de Bruijn B(2,3). Chaque mot de longueur 4 apparaît exactement une fois sur un circuit passant une fois par chaque arête (circuit eulérien). Chaque facteur de longueur 3 apparaît une fois sur un circuit passant une fois par chaque sommet (circuit hamiltonien).

Le même graphe de de Bruijn B(2,3). L'étiquette de chaque arc est le dernier symbole du sommet d'arrivée.

Les suites de de Bruijn peuvent être construites en suivant une chaîne hamiltonienne dans un graphe de de Bruijn d'ordre $n$ sur $k$ symboles ou, de manière équivalente, un cycle eulérien dans un graphe de de Bruijn d'ordre $n -1$ . Pour la construction avec le cycle eulérien, on note alors les étiquettes des arêtes traversées.

Une autre construction, plus surprenante, consiste à concaténer en ordre lexicographique tous les mots de Lyndon dont la longueur divise n[6]. Ainsi, pour n=4, la concaténation des mots de Lyndon

0 0001 0011 01 0111 1

donne le mot de de Bruijn 0000100110101111. Cette construction est linéaire en temps et logarithmique en place parce qu'il existe un algorithme efficace, linéaire en temps et en place, pour engendrer les mots de Lyndon.

Encore une autre construction est au moyen de registres à décalage[7] et basée sur les corps finis[8]. Knuth[9] consacre une partie de la section 7.2.1.1 de son volume 4A à des techniques de construction de suites de de Bruijn.

Exemple détaillé

Pour construire une suite de de Bruijn binaire d'ordre 4, de longueur 2⁴ = 16, contenant les 16 mots binaires de longueur 4, on peut utiliser un circuit eulérien dans le graphe de de Bruijn B(2,3) de la figure.

Chaque arc de ce graphe est formé de quatre bits : les trois premiers sont l'étiquette du sommet de départ, les trois derniers ceux du sommet d'arrivée. Voici un chemin eulérien du graphe (écrit sur deux lignes).

000, 000, 001, 011, 111, 111, 110, 101,
011, 110, 100, 001, 010, 101, 010, 100.

Chaque sommet est visité deux fois, puisqu'il y a deux arcs entrants (et aussi deux arcs sortants). En retenant chaque fois le premier bit du code du sommet, on obtient le mot de de Bruijn :

0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1

On aurait aussi bien pu garder le dernier bit, et alors on obtient :

0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0

On peut également utiliser un circuit hamiltonien, et on obtient alors une suite de de Bruijn d'ordre 3.

Variantes

Une méthode simple pour trouver le bon cheminement consiste par exemple à choisir systématiquement l'arc qui porte l'étiquette qui se termine par 1. C'est une des méthodes présentées dans un article du American Mathematical Monthly[10] :

Algorithme « prefer one »

Commencer avec une suite de n zéros
Essayer d'ajouter un 1 à la suite. Si les n derniers bits n’ont pas été rencontrés auparavant, accepter et répéter l'étape 2, sinon passer à l'étape suivante.
Essayer d'ajouter un 0 à la suite. Si les n derniers bits n’ont pas été rencontrés auparavant, accepter et répéter l'étape 2; sinon arrêter.

Pour n = 3, cette méthode produit successivement les suites :

000
0001 (001 est nouveau)
00011 (011 est nouveau)
000111 (111 est nouveau)
0001110 (111 déjà vu, mais 110 est nouveau)
00011101 (101 est nouveau)
000111010 (011 déjà vu, mais 010 est nouveau)
0001110100 (100 est nouveau)
fin( 001 et 000 sont déjà vus).

Algorithme « prefer opposite »

Une autre façon d’engendrer la séquence est l’algorithme « prefer opposite ». Cet algorithme est similaire au précédent, mais au lieu d’essayer d’ajouter le bit 1 à chaque étape, on essaye de continuer par le bit opposé au dernier bit de la suite. En cas d'échec, on essaie d'ajouter le même bit, et si on échoue encore, l’algorithme se termine.

Cette procédure, cependant, ne produit pas le mot formé uniquement de 1. La règle est donc modifiée comme suit : si la suite se termine par n-1 fois 1, et dans ce cas seulement, ajouter 1.

Pour n = 3, cette méthode produit successivement les suites :

000
0001 (001 est nouveau)
00010 (010 est nouveau)
000101 (101 est nouveau)
0001011 (010 déjà vu mais 011 est nouveau)
00010111 (on privilégie 1 pour obtenir 111)
000101110 (110 est nouveau)
0001011100 (101 déjà vu mais 100 est nouveau)
fin (001 et 000 déjà vu)

Un autre algorithme simple

L'algorithme suivant[11] est basé sur une fonction $f$ qui associe, à un mot binaire $b_{1}b_{2}\cdots b_{n}$ , un autre mot binaire selon la règle (appelée « shift rule » ou « règle de décalage ») :

f(b_{1}b_{2}\cdots b_{n})={\begin{cases}b_{2}b_{3}\cdots b_{n}{\bar {b}}_{1}&{\text{si}}\ \ b_{2}b_{3}\cdot b_{n}1{\text{ est minimal}}\\b_{2}b_{3}\cdots b_{n}b_{1}&sinon\end{cases}}

Ici, un mot binaire $c_{1}c_{2}\cdots c_{n}$ est minimal[12] s'il est minimal parmi tous ses permutés circulaires. Par exemple, 0001, 0101, 1111 sont minimaux, 1000, 1010 ne le sont pas. En d'autres termes, un mot minimal est une puissance d'un mot de Lyndon.

La règle de décalage est appliquée itérativement en commençant par un bloc formé de zéros. Pour n=5, on obtient

00000, 00001, 00011, 00111, 01111, 11111, 11110, 11101, 11011, 10111, 01110, 11100, 11001, 10011, 00110, 01100, 11000, 10001, 00010, 00101, 01011, 10110, 01101, 11010, 10101, 01010, 10100, 01001, 10010, 00100, 01000, 10000.

Si l'on prend les premiers bits de chacun des blocs, on obtient la suite de de Bruijn:

00000111110111001100010110101001

et les auteurs prouvent que c'est une suite de de Bruijn dans le cas général.

Extensions

Peut-on étendre un mot de de Bruijn d'ordre n en un mot d'ordre n+1 ? La réponse est plus subtile que l'on ne pourrait supposer, parce qu'elle fait intervenir la taille de l’alphabet[13] :

Toute suite de de Bruijn binaire d'ordre n peut être étendue en une suite de de Bruijn d'ordre n+2. Toute suite de de Bruijn d'ordre n sur au moins trois symboles peut être étendue en une suite d'ordre n+1.

Il en résulte qu'il existe des suites de de Bruijn infinies ; elles sont définies comme des limites de suites de de Bruijn finies.

Une question similaire est la suivante : peut-on étendre une suite de de Bruijn d'ordre n sur k lettres en un mot d'ordre n sur k+1 lettres ? La réponse est là aussi, positive[14].

Applications

Parmi les « applications », on peut citer la méthode qui permet de trouver un digicode ; s'il est composé de 4 chiffres par exemple, il faudrait en principe tester toutes les 10 000 combinaisons, de longueur totale 40 000. En utilisant une suite de de Bruijn, il suffit de taper au plus 10 003 chiffres (les 3 derniers pour facteur qui chevauche le début).

Les suites de de Bruijn ont trouvé des applications dans des expériences en neurosciences et en psychologie, dans l'étude des stimuli de système nerveux[15] et peuvent être adaptées pour l'usage dans l'imagerie par résonance magnétique fonctionnelle[16].

Les symboles d'une suite de de Bruijn écrits en cercle autour d'un objet circulaire (comme un disque) peuvent servir à identifier une angle en examinant n symboles consécutifs faisant face à un point donné. Des codes de Gray peuvent être utilisés également dans ce cas.

Une suite de de Bruijn peut être employée pour trouver rapidement le bit de poids faible ou le bit de poids fort dans un mot en utilisant des opérations bit à bit[17]^,[18].

Tore de de Bruijn

Tore de de Bruin. Toute matrice d'ordre 2 x 2 apparaît une fois.

Un tore de de Bruijn (en) est un tableau toroïdal qui a la propriété que toute matrice d'ordre m x n dont les éléments peuvent prendre k valeurs y apparaît exactement une fois.

On peut utiliser un tel dispositif pour coder une matrice par le couple d'indices indiquant sa position dans le tore de de Bruijn.

Le calcul de la position de l'unique occurrence d'un mot ou d'une matrice dans une suite ou dans un tore de de Bruijn est connu sous le nom de problème de décodage de de Bruijn. Des algorithmes efficaces en complexité $O(n\log n)$ existent pour certaines suites particulières construites par récurrence[19] et s'étendent au cas bidimensionnel[20].

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « De Bruijn sequence » (voir la liste des auteurs).

De Bruijn 1975.
Flye Sainte-Marie 1894
Aardenne-Ehrenfest, de Bruijn 1951.
Knuth, Combinatorial Algorithms, Part 1, Section 7.2.1.7 : History and further references, Indian prosody, p. 487-489.
Popper 1934, p. 294.
D'après Berstel et Perrin 2007, la séquence construite de cette manière a été décrite, de façon différente, par Martin 1934, et la connexion entre cette suite et les mots de Lyndon a été observée par Fredricksen et Maiorana 1978. La propriété que cette suite est lexicographiquement minimale, est énoncée, mais n'est pas démontrée. Une démonstration a été fournie dans Moreno et Perrin 2015.
Goresky et Klapper 2012, 8.2.5 Shift register generation of de Bruijn sequences.
Ralston 1982, p. 136-139.
Knuth, Shift register sequences, p. 302-308 et Exercices p. 316-318.
Alhakim 2010.
Sawada et WilliamsWong 2016.
Les auteurs de l'article disent « necklace », mais ce mot « collier » signifie usuellement « mot circulaire ».
Becher et Heiber 2011.
Schwartz, Svoray et Weiss 2019.
G. K. Aguirre, M. G. Mattar, L. Magis-Weinberg, « de Bruijn cycles for neural decoding », NeuroImage, vol. 56,‎ 2011, p. 1293–1300 (lire en ligne).
« De Bruijn cycle generator »
Sean Eron Anderson, « Bit Twiddling Hacks », Stanford University, 1997–2009 (consulté le 12 février 2009)
Philip Busch, « Computing Trailing Zeros HOWTO », 2009 (consulté le 29 janvier 2015)
Tuliani 2001.
Hurlbert et Isaak 1993.

Bibliographie

Camille Flye Sainte-Marie, « Question 48 », L'intermédiaire des Mathématiciens, vol. 1,‎ 1894, p. 107–110
Tatiana van Aardenne-Ehrenfest et Nicolaas Govert de Bruijn, « Circuits and trees in oriented linear graphs », Simon Stevin, vol. 28,‎ 1951, p. 203–217 (Math Reviews 0047311, lire en ligne).
Abbas M. Alhakim, « A Simple Combinatorial Algorithm for de Bruijn Sequences », The American Mathematical Monthly, vol. 117, n^o 8,‎ octobre 2010, p. 728-732 (DOI 10.4169/000298910x515794, JSTOR 10.4169/000298910x515794)
Gal Amram et Amir Rubin, « An efficient generalized shift-rule for the prefer-max De Bruijn sequence », Discrete Mathematics, vol. 343, n^o 2,‎ 2020, article n^o 111657 (DOI 10.1016/j.disc.2019.111657)
Gal Amram, Yair Ashlagi, Amir Rubin, Yotam Svoray, Moshe Schwartz et Gera Weiss, « An efficient shift rule for the prefer-max De Bruijn sequence », Discrete Mathematics, vol. 342, n^o 1,‎ 2019, p. 226–232 (DOI 10.1016/j.disc.2018.09.024)
Verónica Becher et Pablo Ariel Heiber, « On extending de Bruijn sequences », Information Processing Letters, vol. 111, n^o 18,‎ 2011, p. 930–932 (Math Reviews 2849850)
Jean Berstel et Dominique Perrin, « The origins of combinatorics on words », Journal européen de combinatoire, vol. 28, n^o 3,‎ 2007, p. 996–1022 (DOI 10.1016/j.ejc.2005.07.019, Math Reviews 2300777, lire en ligne).
Nicolaas Govert de Bruijn, « A combinatorial problem », Proc. Koninklijke Nederlandse Akademie v. Wetenschappen, vol. 49,‎ 1946, p. 758–764 (Math Reviews 0018142, lire en ligne).
Nicolaas Govert de Bruijn, « Acknowledgement of Priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2ⁿ zeros and ones that show each n-letter word exactly once », T.H.-Report 75-WSK-06, Technological University Eindhoven,‎ 1975 (lire en ligne).
Patrick Baxter Dragon, Oscar I. Hernandez, Joe Sawada, Aaron Williams et Dennis Wong, « Constructing de Bruijn sequences with co-lexicographic order: The k-ary Grandmama sequence », European Journal of Combinatorics, vol. 72,‎ 2018, p. 1–11 (DOI 10.1016/j.ejc.2018.03.006).
Harold Fredricksen et James Maiorana, « Necklaces of beads in k colors and k-ary de Bruijn sequences », Discrete Mathematics, vol. 23, n^o 3,‎ 1978, p. 207–210 (DOI 10.1016/0012-365X(78)90002-X, Math Reviews 523071).
Daniel Gabric, Joe Sawada, Aaron Williams et Dennis Wong, « A framework for constructing de Bruijn sequences via simple successor rules », Discrete Mathematics, vol. 341, n^o 11,‎ 2018, p. 2977-2987 (DOI 10.1016/j.disc.2018.07.010)
Mark Goresky et Andrew Klapper, Algebraic Shift Register Sequences, Cambridge University Press, 2012, 498 p. (ISBN 978-1-107-01499-2 et 1107014999, lire en ligne).
Glenn Hurlbert et Garth Isaak, « On the de Bruijn torus problem », Journal of Combinatorial Theory, vol. 64 « Series A », n^o 1,‎ 1993, p. 50–62 (DOI 10.1016/0097-3165(93)90087-O, Math Reviews 1239511, lire en ligne).
Donald E. Knuth, The Art of Computer Programming, vol. 4A : Combinatorial Algorithms, Part 1, Addison-Wesley, 2011 (ISBN 978-0-201-03804-0 et 0-201-03804-8, présentation en ligne)
Monroe H. Martin, « A problem in arrangements », Bulletin of the American Mathematical Society, vol. 40, n^o 12,‎ 1934, p. 859–864 (DOI 10.1090/S0002-9904-1934-05988-3, Math Reviews 1562989, lire en ligne).
Eduardo Moreno et Dominique Perrin, « Corrigendum to "On the theorem of Fredricksen and Maiorana about de Bruijn sequences" [Adv. in Appl. Math. 33 (2) (2004) 413-415] », Advances in Applied Mathematics, vol. 62,‎ 2015, p. 184-187 (DOI 10.1016/j.aam.2003.10.002).
Karl Popper, The Logic of Scientific Discovery, Routledge, 2002 (1^re éd. 1934), 513 p. (ISBN 978-0-415-27843-0, lire en ligne)
Anthony Ralston, « de Bruijn sequences—a model example of the interaction of discrete mathematics and computer science », Mathematics Magazine, vol. 55, n^o 3,‎ 1982, p. 131–143 (DOI 10.2307/2690079, Math Reviews 653429).
Joe Sawada, Aaron Williams et Dennis Wong, « A surprisingly simple de Bruijn sequence construction », Discrete Mathematics, vol. 339, n^o 1,‎ janvier 2016, p. 127-131 (DOI 10.13039/501100000038).
Moshe Schwartz, Yotam Svoray et Gera Weiss, « On embedding De Bruijn sequences by increasing the alphabet size », Arxiv,‎ juin 2019 (arXiv 1906.06157).
Jonathan Tuliani, « de Bruijn sequences with efficient decoding algorithms », Discrete Mathematics, vol. 226, n^os 1-3,‎ 2001, p. 313–336 (DOI 10.1016/S0012-365X(00)00117-5, Math Reviews 1802599).
Yu Hin Au, « Generalized de Bruijn words for primitive words and powers », Discrete Mathematics, vol. 338, n^o 12,‎ décembre 2015, p. 2320-2331 (DOI 10.13039/501100000038, arXiv 0904.3997)

Articles liés

Graphe de de Bruijn
Tore de de Bruijn (en)
Nombre normal
Registre à décalage à rétroaction linéaire
Maximum length sequence

Liens externes

Articles

(en) Eric W. Weisstein, « de Bruijn Sequence », sur MathWorld
suite A166315 de l'OEIS Lexicographically smallest binary de Bruijn sequences
De Bruijn sequence

Programmes

« Combinatorial Object Server »^{(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)}, contient un générateur de suites de de Bruijn.
Générateur par produit de mots de Lyndon (CGI)
Générateur par produit de mots de Lyndon (Java).
Générateur et décodeur de suites de de Bruijn. Implémentation de l'algorithme de Jonathan Tuliani.
Minimal arrays containing all sub-array combinations of symbols: De Bruijn sequences and tori

Portail des mathématiques
Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[db75-1] De Bruijn 1975.

[2] Flye Sainte-Marie 1894

[3] Aardenne-Ehrenfest, de Bruijn 1951.

[4] Knuth, Combinatorial Algorithms, Part 1, Section 7.2.1.7 : History and further references, Indian prosody, p. 487-489.

[5] Popper 1934, p. 294.

[6] D'après Berstel et Perrin 2007, la séquence construite de cette manière a été décrite, de façon différente, par Martin 1934, et la connexion entre cette suite et les mots de Lyndon a été observée par Fredricksen et Maiorana 1978. La propriété que cette suite est lexicographiquement minimale, est énoncée, mais n'est pas démontrée. Une démonstration a été fournie dans Moreno et Perrin 2015.

[7] Goresky et Klapper 2012, 8.2.5 Shift register generation of de Bruijn sequences.

[8] Ralston 1982, p. 136-139.

[9] Knuth, Shift register sequences, p. 302-308 et Exercices p. 316-318.

[10] Alhakim 2010.

[11] Sawada et WilliamsWong 2016.

[12] Les auteurs de l'article disent « necklace », mais ce mot « collier » signifie usuellement « mot circulaire ».

[13] Becher et Heiber 2011.

[14] Schwartz, Svoray et Weiss 2019.

[15] G. K. Aguirre, M. G. Mattar, L. Magis-Weinberg, « de Bruijn cycles for neural decoding », NeuroImage, vol. 56,‎ 2011, p. 1293–1300 (lire en ligne).

[16] « De Bruijn cycle generator »

[17] Sean Eron Anderson, « Bit Twiddling Hacks », Stanford University, 1997–2009 (consulté le 12 février 2009)

[18] Philip Busch, « Computing Trailing Zeros HOWTO », 2009 (consulté le 29 janvier 2015)

[19] Tuliani 2001.

[20] Hurlbert et Isaak 1993.