Tableau de Lyndon

En combinatoire, et particulièrement en combinatoire des mots et en algorithmique du texte, le tableau de Lyndon d'une chaîne w est un tableau $L$ de même taille dont les entrées contiennent les longueurs des mots de Lyndon maximaux commençant dans les positions respectives. Ce tableau est utile dans la détermination et le décompte des répétitions de facteurs dans le mot.

Description

Tableau de Lyndon

Le tableau de Lyndon $L$ d'une chaîne $w$ est un tableau de même taille tel que $L[i]$ est la longueur du plus long facteur de $w$ commençant en position $i$ qui est un mot de Lyndon. Formellement :

$L[i]=\max \{h:w[i,i+h-1]\text{ est un mot de Lyndon}\}.$

Exemple

Les tableaux sont numérotés à partir de 0. Soit $w=00011001$. Le tableau de Lyndon du mot est donné dans la dernière colonne ci-dessous :

Indice	Lyndon	L
0	00011001	8
1	0011	4
2	011	3
3	1	1
4	1	1
5	001	3
6	01	2
7	1	1

Le tableau de Lyndon est

$L=(8,4,3,1,1,3,2,1)$.

Autres tableaux

Deux autres tableaux sont liés au tableau de Lyndon d'un mot, d'une part le tableau des suffixes et d'autre part le tableau dites des valeurs inférieures suivantes :

Le tableau des valeurs inférieures suivantes (en anglais next smaller value array) $N=N_A$ est défini pour un tableau d'entiers $A[1,n]$ ; il contient, pour l'indice $i$, le plus petit indice d'une valeur dans $A[i+1,n]$ qui est plus petite que $A[i]$ ; si une telle valeur n'existe pas, le tableau contient pour cet indice la valeur maximale $n$. Formellement,

$N_A[i]=\min \{n\}\cup \{j\mid j>i\text{ et }A[j]<A[i]\}.$.

Par exemple, pour le tableau

$A=(8,4,3,1,1,3,2,1)$,

le tableau des valeurs inférieures suivantes est

$N=N_A=(1,2,3,8,8,6,7,8)$.

Relation entre ces tableaux

Franek et al. ont montré que le tableau de Lyndon se calcule facilement en temps linéaire en appliquant la construction du next smaller value array à l'inverse du tableau des suffixes : si on note $S$ le tableau des suffixe du mot et $U$ l'inverse de ce tableau (de sorte que $S[i]=j$ ssi $U[j]=i$), alors le tableau de Lyndon est donné par la formule

$L[i]=N_U[i]-i$.

Exemple

Pour le mot $w=00011001$, le tableau des suffixes - qui donne la longueurs des suffixes dans l'ordre lexicographique - est

$S=S(w)=(0,5,1,6,2,7,4,3)$

et le tableau des inverses est

$U=(0,2,4,7,6,1,3,5)$.

Le tableau des valeurs inférieures suivantes pour U est

$N=N_U=(8,5,5,4,5,8,8,8)$.

La formule $L[i]=N_U[i]-i$ donne

$N_U-I=(8,4,3,1,1,3,2,1)=L$ !

Complexité du calcul

D'autres algorithmes ont été donnésModèle:, : un algorithme quadratique en place basé sur l'algorithme de Duval itéré pour la factorisation de Lyndon et un schéma algorithmique linéaire basé sur le tri linéaire des suffixes, calculant le tableau des suffixes inverses et lui appliquant l'algorithme de calcul des valeurs inférieures suivantes. Ces algorithmes s'exécutent en temps quadratique dans le pire des cas, un troisième prend un temps linéaire, au prix d'un calcul préalable du tableau de suffixes et du tableau de suffixes inverse de la chaîne. Deux variantes d'un algorithme donné par Frantisek Franek et Michael Liut évitent le calcul préalable de structures de données globales et s'exécutent dans le pire des cas en temps $n\log n$.

D'après Felipe Louza et ses coauteurs, tous les algorithmes qui calculent de tableau de Lyndon en temps linéaire utilisent le calcul du tableau des suffixes dans une étape de précalcul. Un algorithme de tri des suffixes d'une chaîne a été donné par Nong en 2013. Une variante de cet algorithme qui calcule simultanément le tableau de Lyndon et le tableau des suffixes d'une chaîne de longueur $n$ en temps $O(n)$ et en place additionnelle $\sigma +O(1)$ où $\sigma$ est la taille de l'alphabet, a été donné par Louza et al. Des résultats expérimentaux avec des ensembles de données réels et synthétiques montrent que leur algorithme est non seulement efficace en espace, mais aussi rapide dans la pratique. Un algorithme efficace a été présenté en 2020 par Bille et al.

Applications

Une des applications est due à Bannai et al.. Ils ont utilisé les racines de Lyndon des runs pour prouver la conjecture des runs selon laquelle le nombre de runs dans un mot est majoré par la longueur du mot. Dans le même article, ils ont présenté un algorithme pour calculer tous les runs dans un mot en temps linéaire qui nécessite la connaissance de tous les facteurs de Lyndon maximaux à droite du mot donné, donc le tableau de Lyndon du mot pour à un ordre sur l'alphabet et pour son ordre inverse.

Articles liés

• Mot de Lyndon
• Transformation de Burrows-Wheeler