Théorème des répétitions maximales

En informatique théorique et en combinatoire, et notamment en combinatoire des mots, une répétition est un mot qui est formé d'une consécution, au moins deux fois, d'un autre mot. Par exemple, ababa est une répétition d'exposant 5/2 du mot ab, car ab apparaît deux fois consécutivement, et une troisième fois, mais à moitié seulement.

L'étude des répétitions dans les textes constitue un domaine fondamental en combinatoire des mots, à cause de ses applications importantes à toute la catégorie des algorithmes sur les chaînes de caractères, la compression de données, l'analyse musicale, l'analyse de séquences biologiques, etc.

Un intérêt particulier a été porté à l'étude des répétitions maximales, appelées runs en anglais dans un mot donné : ce sont les répétitions qui ne peuvent être étendues. Une telle répétition peut être efficacement comprimée, et elle a aussi une signification biologique. Un résultat récent établit ce qui, pendant une quinzaine d'années, était appelée la conjecture des runs, à savoir que le nombre de runs dans un mot binaire est toujours inférieur à sa longueur; plus précisément :

Le nombre de répétition maximales (de runs ) dans un mot de longueur ${\displaystyle n}$ est au plus ${\displaystyle n-3}$[1].

Avec la même technique et en utilisant des calculs en machine, ce résultat a été affiné[2] : ce nombre est au plus (22/23)n <0.957n.

Une répétition maximale, ou un run est un facteur (ou sous-intervalle) périodique maximal d'un mot. On entend par mot périodique un mot dont la longueur est au moins deux fois sa période minimale. Par exemple, pour le mot ${\displaystyle w=}$aababaababb, les répétitions maximales sont ${\displaystyle w[1,2]=w[6,7]=}$aa, ${\displaystyle w[10,11]=}$bb, de période 1, ${\displaystyle w[2,6]=}$ababa et ${\displaystyle w[7,10]=}$ababa de période 2, ${\displaystyle w[4,9]=}$abaaba de période 3, et enfin ${\displaystyle w[1,10]=}$ (abbab)${\displaystyle ^{2}}$, de période 5. On a donc un nombre total de runs égal à 7, pour ce mot de longueur 11. Le nombre maximal de run dans un mot de longueur ${\displaystyle n}$ est noté ${\displaystyle \rho (n)}$.

Théorème des runs. Le nombre maximal ${\displaystyle \rho (n)}$ de runs dans un mot de longueur ${\displaystyle n}$ vérifie

${\displaystyle \rho (n)\leq n-3}$,

avec l'amélioration asymptotique ${\displaystyle \rho (n)<{\frac {22}{23}}n<0.957n}$.

Crochemore et. al.[3] et Bannai et. al.[1] retracent l'historique de la conjecture : la conjecture a été formulée par Kolpakov et Kucherov en 1999; ces auteurs ont prouvé que ${\displaystyle \rho (n)=O(n)}$ mais n'ont pas donné de constante pour leur estimation. Depuis, de nombreux travaux ont été menés. La première constante donnée explicitement est de Rytter[4] qui a montré que ${\displaystyle \rho (n)<5n}$. Une des meilleures estimations précédant la démonstration finale[3] donne ${\displaystyle \rho (n)<1,029n}$. Une variante du théorème des runs final a été présenté par les mêmes auteurs en janvier 2015 à la conférence SODA[5]. Dans cet article, l'inégalité est ${\displaystyle \rho (n)<1,5n}$.

Le résultat est basé sur une nouvelle caractérisation des répétitions maximales à l'aide des mots de Lyndon. Cette caractérisation conduit à une preuve bien plus simple et différente des techniques des démonstrations précédentes ; de plus, un structure de données basée sur les arbres de Lyndon qui sont les arbres définis par la factorisation standard des mots de Lyndon, permet un calcul plus efficace parce qu'elle n'utilise pas la factorisation de Lempel-Ziv. Un autre démonstration du théorème des runs, indépendante des racines de Lyndon, a été donnée par Maxime Crochemore et Robert Mercaş[6]

Dans le même article[1], les auteurs prouvent que la somme, notée ${\displaystyle \sigma (n)}$, des longueurs des répétitions maximales d'un mot binaire de longueur n est au plus 3n. De plus, la caractérisation donne un nouvel algorithme linéaire pour calculer toutes les répétitions maximales d'un mot.

Une extension concerne le nombre, noté ${\displaystyle \rho _{k}(n)}$ de répétitions maximales d'exposant au moins k et la somme ${\displaystyle \sigma _{k}(n)}$ des longueurs de ces répétitions. Là aussi, la nouvelle méthode permet d'obtenir des bornes meilleures, à savoir ${\displaystyle \rho _{k}(n)<2n/(k-1)}$ et ${\displaystyle \sigma _{k}(n)<n(k+1)/(k-1)}$. Pour k=3 par exemple, on obtient ${\displaystyle \sigma _{k}(n<2n}$, meilleur que le résultat de Crochemore et. al.[3]. Pour des alphabet de taille plus importante, les majorations sont ${\displaystyle \rho (n,d)\leq n-d}$, et même ${\displaystyle \rho (n,d)\leq n-d-1}$ si ${\displaystyle n>2d}$, où ${\displaystyle \rho (n,d)}$ est le nombre maximum de runs d'un mot de longueur n contenant exactement d symboles distincts.

Les bornes inférieures ont aussi été considérées pour le nombre de répétitions maximales. Il s'agit alors de construire des mots qui contiennent beaucoup de répétitions maximales. La meilleure minoration est[7] est ${\displaystyle \rho (n)>0,944575712n}$. Ce qui donne l'encadrement : ${\displaystyle 0,944n<\rho (n)<0,957n}$, la deuxième étant une approximation de 22/23.

La démonstration esquissée ci-dessous provient de l'exposé de Tomohiro I au colloque DLT 2018[8]. Elle utilise de façon essentielle la notion de mot de Lyndon. On suppose l'alphabet sous-jacent totalement ordonnée. Un mot de Lyndon est un mot qui est strictement plus petit (pour un ordre lexicographique donné) que tous ses conjugués (ou permuté circulaires). Un mot de Lyndon est un mot sans bord car si un mot ${\displaystyle w}$ avait un bord ${\displaystyle x}$, ce mot ${\displaystyle x}$ est un préfixe de ${\displaystyle w}$, donc ${\displaystyle x<w}$, et un suffixe de ${\displaystyle w}$, donc ${\displaystyle w<x}$ parce qu'un mot de Lyndon est plus petit que ses suffixes.

Le calcul de toutes les répétitions maximales remonte à un article de Main et Lorentz[10] qui ont donné un algorithme en ${\displaystyle O(n\log n)}$ et ont montré que cette borne est optimale pour un alphabet non ordonné. La connexion entre runs et mots de Lyndon permet une autre approche du problème : il s'agit de calculer la table des mots de Lyndon maximaux commençant en toute position dans le mot. Un tel algorithme, en ${\displaystyle O(n\alpha (n))}$, où ${\displaystyle \alpha }$ est l'inverse de la fonction d'Ackermann, al été donné par Crochemore et. al.[11].

• Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Ritu Kundu, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter et Tomasz Waleń, « Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries », String Processing and Information Retrieval (SPIRE 2016), vol. 9954 des Lecture Notes in Computer Science,‎ 2016, p. 22–34 (ISBN 978-3-319-46048-2, ISSN 0302-9743, DOI 10.1007/978-3-319-46049-9_3).
• Michael G Main et Richard J Lorentz, « An O(n log n) algorithm for finding all repetitions in a string », Journal of Algorithms, vol. 5, n^o 3,‎ 1984, p. 422–432 (DOI 10.1016/0196-6774(84)90021-X)
• Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter et Tomasz Waleń, « Extracting powers and periods in a word from its runs structure », Theoretical Computer Science, vol. 521,‎ 2014, p. 29–41 (DOI 10.1016/j.tcs.2013.11.018).
• Maxime Crochemore et Robert Mercaş, « On the density of Lyndon roots in factors », Theoretical Computer Science, vol. 656,‎ 2016, p. 234-240 (DOI 10.1016/j.tcs.2016.02.015).
• Maxime Crochemore, Lucian Ilie et Liviu Tinta, « The "runs" conjecture », Theoretical Computer Science, vol. 412, n^o 27,‎ 2011, p. 2931–2941 (DOI 10.1016/j.tcs.2010.06.019)
• Johannes Fischer, Štěpán Holub, Tomohiro I et Moshe Lewenstein, « Beyond the Runs Theorem », dans Costas Iliopoulos, Simon Puglisi et Emine Yilmaz (éditeurs), String Processing and Information Retrieval : 22nd International Symposium, coll. « Lecture Notes in Computer Science » (n^o 9309), 2015 (ISBN 978-3-319-23825-8, DOI 10.1007/978-3-319-23826-5_27, arXiv 1502.04644.pdf), p. 277-286
• 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 (DOI 10.1137/15M1011032, arXiv 1406.0263)
• Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda et Kazuya Tsuruta, « A new characterization of maximal repetitions by Lyndon trees », dans Piotr Indyk (éditeur), Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Society of Industrial and Applied Mathematics (SIAM), janvier 2015 (DOI 10.1137/1.9781611973730.38), p. 562-571
• Wojciech Rytter, « The number of runs in a string: Improved analysis of the linear upper bound », dans Proceedings Symposium on Theoretical Aspects of Computer Science, Springer-Verlag, coll. « Lecture Notes of Comuter Science » (n^o 3884), 2006, p. 184–195
• Jamie Simpson, « Modified Padovan words and the maximum number of runs in a word », Australas. J. Combin., vol. 46,‎ 2010, p. 129-145
• Tomohiro I, « The Runs Theorem and Beyond », dans Developments in Language Theory - 22nd International Conference, DLT, Tokyo, Springer-Verlag, coll. « Lecture Notes of Comuter Science » (n^o 11088), 2018 (ISBN 978-3-319-98653-1, DOI 10.1007/978-3-319-98654-8_2), p. 18–23.
• Ryo Sugahara, Yuto Nakashima, Shunsuke Inenaga, Yuto Nakashima, Hideo Bannai et Masayuki Takeda, « Efficiently computing runs on a trie », Theoretical Computer Science, vol. 887,‎ 2 octobre 2021, p. 143-151 (DOI 10.1016/j.tcs.2021.07.011)

• Algorithmique du texte
• Algorithme de recherche de sous-chaîne
• Répétitions
• Compression de données

• Portail de l'informatique théorique