Suite de de Bruijn

Suite de de Bruijn pour Modèle:Math et Modèle:Math.

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.

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 Modèle:Math. Il existe

$\frac{{(k!)}^{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, l'existence de suites de de Bruijn de tout ordre a été démontré d'abord par Camille Flye Sainte-Marie en 1894 pour un alphabet binaire, et dans le cas général par Tatiana van Aardenne-Ehrenfest et lui-même en 1951.

Knuth, dans son volume 4A, 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 avec la formule d'énumération $2^{2^{n-1}-n}$. Ce résultat a été oublié, et Modèle:Harvsp a démontré l'existence de tels mots circulaires sur un alphabet général, avec un algorithme de construction. Enfin, Modèle:Lien 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.

Karl Popper a décrit les mêmes objets indépendamment dans un livre paru en 1934 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 Modèle:Math sur Modèle:Math symboles ou, de manière équivalente, un cycle eulérien dans un graphe de de Bruijn d'ordre Modèle:Math. 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. 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 et basée sur les corps finis. Knuth 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 :

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 (101 déjà vu, mais 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 est basé sur une fonction Modèle:Math 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{array}{cc}{b}_2{b}_3\cdots b_n{\overline{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{array}$

Ici, un mot binaire $c_1{c}_2\cdots c_n$ est minimal 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 : Modèle:Énoncé 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.

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 et peuvent être adaptées pour l'usage dans l'imagerie par résonance magnétique fonctionnelle.

Les symboles d'une suite de de Bruijn écrits en cercle autour d'un objet circulaire (comme un disque) peuvent servir à identifier un 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 à bitModèle:,.

Generalisations

Tore de de Bruijn

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

Modèle:Article détaillé Un Modèle:Lien 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 et s'étendent au cas bidimensionnel.

Suite généralisée

Une suite de de Bruijn généralisée avec les paramètres $(n,l,k)$ est une suite cyclique de $n$ bits telle que chaque facteur de longueur $l$ figure au plus $k$ fois. Une telle suite est dite équilibrée si elle contient autant de 0 que de 1.

Une suite de de Bruijn usuelle d'ordre $m$ est une suite de de Bruijn généralisée avec les paramètres $(2m,m,1)$. Une telle suite est toujours équilibrée. Le résultat principal de Modèle:Harvsp caractérise les paramètres $(n,l,k)$ pour lesquels il existe une suite de Bruijn généralisée équilibrée avec des paramètres $(n,l,k)$. Les auteurs prouvent que, pour des entiers positifs $n,l$ et $k$, il existe une suite de Bruijn généralisée équilibrée avec les paramètres $(n,l,k)$ si et seulement si $n$ est pair et $k>n/2^l$

Bibliographie

• Modèle:Article
• Modèle:Article.
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article.
• Modèle:Article
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article
• Modèle:Ouvrage.
• Modèle:Article.
• Modèle:Ouvrage
• Modèle:Article.
• Modèle:Article.
• Modèle:Ouvrage
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article

Articles liés

• Graphe de de Bruijn
• Modèle:Lien
• Nombre normal
• Registre à décalage à rétroaction linéaire
• Maximum length sequence
• Permutation circulaire lexicographiquement minimale

Liens externes

Articles

• Modèle:MathWorld
• Modèle:OEIS Lexicographically smallest binary de Bruijn sequences
• De Bruijn sequence

Programmes

• Modèle:Lien brisé, 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