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.^[1] 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és^[2]^,^[3] : 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^[4]. 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^[5] é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^[6], 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^[7]. 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^[6]. 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^[6]. Un algorithme efficace a été présenté en 2020 par Bille et al^[8].

Applications

Une des applications est due à Bannai et al.^[9]. 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.

Notes et références

↑ Frantisek Franek, A. S. M. Sohidull Islam, M. Sohel Rahman et William F. Smyth, « Algorithms to Compute the Lyndon Array », dans Prague Stringology Conference, 2016 (ISBN 978-80-01-05996-8, lire en ligne), p. 172-184
↑ Felipe A. Louza, W. F. Smyth, Giovanni Manzini et Guilherme P. Telles, « Lyndon array construction during Burrows–Wheeler inversion », Journal of Discrete Algorithms, vol. 50,‎ 2018, p. 2–9 (ISSN 1570-8667, DOI 10.1016/j.jda.2018.08.001)
↑ Frantisek Franek et Michael Liut, « Algorithms to Compute the Lyndon Array Revisited », dans Prague Stringology Conference, 2019 (ISBN 978-80-01-06618-8, lire en ligne), p. 16-28
↑ Uwe Baier, « Linear-time Suffix Sorting - A New Approach for Suffix Array Construction », dans Roberto Grossi et Moshe Lewenstein (éditeurs), 27th Annual Symposium on Combinatorial Pattern Matching, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, coll. « Leibniz International Proceedings in Informatics (LIPIcs) » (n^o 54), 2016 (ISBN 978-3-95977-012-5, DOI 10.4230/LIPIcs.CPM.2016.23, lire en ligne), p. 123:1-23:12
↑ Frantisek Franek et Michael Liut, « Computing Maximal Lyndon Substrings of a String », Algorithms, vol. 13, n^o 11,‎ 2020, article n^o 294 (ISSN 1999-4893, DOI 10.3390/a13110294).
↑ ^{a b et c} Felipe A. Louza, Sabrina Mantaci, Giovanni Manzini, Marinella Sciortino et Guilherme P. Telles, « Inducing the Lyndon Array », dans String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019,, Segovia, coll. « Lecture Notes in Computer Science », 2019 (ISBN 978-3-030-32685-2, DOI 10.1007/978-3-030-32686-9_10, arXiv 1905.12987), p. 138–151.
↑ Ge Nong, « Practical linear-time O(1)-workspace suffix sorting for constant alphabets », ACM Transactions on Information Systems, vol. 31, n^o 3,‎ 2013, p. 1–15 (ISSN 1046-8188, DOI 10.1145/2493175.2493180).
↑ Philip Bille, Jonas Ellert, Johannes Fischer, Inge Li Gørtz, Florian Kurpicz, J. Ian Munro et Eva Rotenberg, « Space Efficient Construction of Lyndon Arrays in Linear Time », dans Artur Czumaj, Anuj Dawar et Emanuela Merelli (éditeurs), 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, coll. « Leibniz International Proceedings in Informatics (LIPIcs) » (n^o 168), 2020 (DOI 10.4230/LIPIcs.ICALP.2020.14, lire en ligne), p. 14:1-14:18.
↑ Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda et Kazuya Tsuruta, « The “Runs” Theorem », SIAM Journal on Computing, vol. 46, n^o 5,‎ 2017, p. 1501–1514 (ISSN 0097-5397, DOI 10.1137/15M1011032).

Articles liés

[FranekSmyth2016-1] Frantisek Franek, A. S. M. Sohidull Islam, M. Sohel Rahman et William F. Smyth, « Algorithms to Compute the Lyndon Array », dans Prague Stringology Conference, 2016 (ISBN 978-80-01-05996-8, lire en ligne), p. 172-184

[LouzaSmyth2018-2] Felipe A. Louza, W. F. Smyth, Giovanni Manzini et Guilherme P. Telles, « Lyndon array construction during Burrows–Wheeler inversion », Journal of Discrete Algorithms, vol. 50,‎ 2018, p. 2–9 (ISSN 1570-8667, DOI 10.1016/j.jda.2018.08.001)

[FranekLiut2019-3] Frantisek Franek et Michael Liut, « Algorithms to Compute the Lyndon Array Revisited », dans Prague Stringology Conference, 2019 (ISBN 978-80-01-06618-8, lire en ligne), p. 16-28

[Baier2016-4] Uwe Baier, « Linear-time Suffix Sorting - A New Approach for Suffix Array Construction », dans Roberto Grossi et Moshe Lewenstein (éditeurs), 27th Annual Symposium on Combinatorial Pattern Matching, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, coll. « Leibniz International Proceedings in Informatics (LIPIcs) » (n^o 54), 2016 (ISBN 978-3-95977-012-5, DOI 10.4230/LIPIcs.CPM.2016.23, lire en ligne), p. 123:1-23:12

[FranekLiut2020-5] Frantisek Franek et Michael Liut, « Computing Maximal Lyndon Substrings of a String », Algorithms, vol. 13, n^o 11,‎ 2020, article n^o 294 (ISSN 1999-4893, DOI 10.3390/a13110294).

[LouzaMantaci2019-6] {a b et c} Felipe A. Louza, Sabrina Mantaci, Giovanni Manzini, Marinella Sciortino et Guilherme P. Telles, « Inducing the Lyndon Array », dans String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019,, Segovia, coll. « Lecture Notes in Computer Science », 2019 (ISBN 978-3-030-32685-2, DOI 10.1007/978-3-030-32686-9_10, arXiv 1905.12987), p. 138–151.

[Nong2013-7] Ge Nong, « Practical linear-time O(1)-workspace suffix sorting for constant alphabets », ACM Transactions on Information Systems, vol. 31, n^o 3,‎ 2013, p. 1–15 (ISSN 1046-8188, DOI 10.1145/2493175.2493180).

[Bille2020-8] Philip Bille, Jonas Ellert, Johannes Fischer, Inge Li Gørtz, Florian Kurpicz, J. Ian Munro et Eva Rotenberg, « Space Efficient Construction of Lyndon Arrays in Linear Time », dans Artur Czumaj, Anuj Dawar et Emanuela Merelli (éditeurs), 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, coll. « Leibniz International Proceedings in Informatics (LIPIcs) » (n^o 168), 2020 (DOI 10.4230/LIPIcs.ICALP.2020.14, lire en ligne), p. 14:1-14:18.

[BannaiI2017-9] Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda et Kazuya Tsuruta, « The “Runs” Theorem », SIAM Journal on Computing, vol. 46, n^o 5,‎ 2017, p. 1501–1514 (ISSN 0097-5397, DOI 10.1137/15M1011032).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]