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 kn. Il existe

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 . 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 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 24 = 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 »

  1. Commencer avec une suite de n zéros
  2. 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.
  3. 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 , un autre mot binaire selon la règle (appelée « shift rule » ou « règle de décalage ») :

Ici, un mot binaire 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é 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).
  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, , p. 1293–1300 (lire en ligne).
  16. « De Bruijn cycle generator »
  17. Sean Eron Anderson, « Bit Twiddling Hacks », Stanford University, 1997–2009 (consulté le )
  18. Philip Busch, « Computing Trailing Zeros HOWTO », (consulté le )
  19. Tuliani 2001.
  20. Hurlbert et Isaak 1993.

Bibliographie

Articles liés

Liens externes

Articles
Programmes
  • 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.