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

Le théorème des répétitions maximales (en anglais « the "runs" theorem ») qui s’appelait, avant d'avoir été démontrée, la conjecture des répétitions maximales (en anglais « the "runs" conjecture ») est un résultat de combinatoire des mots. Il donne une majoration du nombre de répétitions maximales (ou "runs") que peut contenir un mot donné.

Description informelle modifier

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   est au plus  [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.

Définitions modifier

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  aababaababb, les répétitions maximales sont  aa,  bb, de période 1,  ababa et  ababa de période 2,  abaaba de période 3, et enfin   (abbab) , 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   est noté  .

Théorème des runs. Le nombre maximal   de runs dans un mot de longueur   vérifie

 ,

avec l'amélioration asymptotique  .

Historique modifier

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   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  . Une des meilleures estimations précédant la démonstration finale[3] donne  . Une variante du théorème des runs final a été présenté par les mêmes auteurs en à la conférence SODA[5]. Dans cet article, l'inégalité est  .

Résultats et discussion modifier

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  , 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é   de répétitions maximales d'exposant au moins k et la somme   des longueurs de ces répétitions. Là aussi, la nouvelle méthode permet d'obtenir des bornes meilleures, à savoir   et  . Pour k=3 par exemple, on obtient  , meilleur que le résultat de Crochemore et. al.[3]. Pour des alphabet de taille plus importante, les majorations sont  , et même   si  , où   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  . Ce qui donne l'encadrement :  , la deuxième étant une approximation de 22/23.

Éléments de démonstration modifier

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   avait un bord  , ce mot   est un préfixe de  , donc  , et un suffixe de  , donc   parce qu'un mot de Lyndon est plus petit que ses suffixes.

Racine de Lyndon modifier

Tout run de période   contient en facteur un mot de Lyndon de longueur  . Ce mot est la racine de Lyndon de la répétition. Par exemple, le run

cbabacbabac

contient la racine de Lyndon abacb qui est en effet le plus petit parmi les 5 mots cbaba, babac, abacb, bacba, acbab. La notion de racine de Lyndon (ou L-root) apparaît dans un article de Crochemore et al. de 2014[9]. La racine de Lyndon d'une répétition est unique.

Runs cubiques modifier

Un run cubique est une répétition d'exposant au moins 3. Un tel mot contient en facteur le carré (ou une puissance supérieure) de sa racine de Lyndon. Par exemple, le run cubique

cbabacbabacbabac

contient le facteur abacbabacb qui est le carré de sa racine de Lyndon abacb. Les deux occurrences de sa racine de Lyndon déterminent un point dans le run qui est appelé sa frontière et qu'on peut noter

cbabacb·abacbabac

Deux runs cubique n'ont pas de frontière commune : supposons au contraire que deux carrés de racines de Lyndon   et   ont la même frontière, et que   est plus court que   ; alors   est suffixe de   par la première occurrence et préfixe de   par la deuxième occurrence, donc   serait un bord de  , ce qui contredit le fait qu'un mot de Lyndon est sans bord. Ainsi, chaque run cubique détermine donc une ou plusieurs frontières, et ces frontières sont propres au run.

Il en résulte qu'un mot de longueur   ne peut avoir plus de   runs cubiques. En fait, on peut améliorer cette borne en  ; en considérant non seulement un ordre lexicographique donné mais aussi son ordre opposé (avec   si et seulement si  ). Ainsi, le mot

cbabacbabacbabac

a pour le préfixe le cube de cbaba qui, pour l'ordre opposé  , est un mot de Lyndon. Il définit donc deux autres frontières :

cbaba·cbaba·cbabac

Chaque run cubique définit alors au moins deux frontières, l'une pour chaque ordre, et ces frontières sont distincts parce qu'une racine de Lyndon pour un ordre n'est certainement pas un conjugué minimal de la racine pour l’ordre opposé. Tout run cubique détermine donc au moins deux frontières, et ses frontières ne se partagent pas, d'où la majoration en n/2[9].

Cas général modifier

Dans le cas général, où les runs ne sont pas cubiques, un raffinement de l'argument précédent doit être appliqué. Un tel run possède toujours une racine de Lyndon, mais il n'y en a pas nécessairement deux, donc pas de frontière. Si w[s,e] est la racine d'un run w[i,j], on peut vérifier que la racine est le plus long facteur de Lyndon de w commençant en position s, à condition que la lettre w[j+1] qui suit est plus petite que la lettre en position j+1-p (où p est la période) : par exemple, pour le run cbabacbabac, si la lettre suivante est un a, la racine de Lyndon est le facteur souligné dans

cbabacbabaca pour a<b<c,

et c'est bien le plus long facteur qui commence en position s et qui est un mot de Lyndon ; si la lettre qui suit est un c, alors, en opérant sur l'ordre opposé a>b>c, le facteur souligné

cbabacbabacc

est à nouveau le plus long facteur en position s qui est un mot de Lyndon. Ces racines sont indépendantes du run considéré, elles sont appelées racines globales.

Pour tout run   composé du facteur w[i,j] et de période p, on note   l'ensemble des débuts des positions des racines de Lyndon globales, pour l'ordre < et son opposé, à l'exception de la position  . On a alors les deux propriétés :

  et, si  , alors  .

Il en résulte que le nombre de runs est au plus  .

Calcul des runs modifier

Le calcul de toutes les répétitions maximales remonte à un article de Main et Lorentz[10] qui ont donné un algorithme en   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  , où   est l'inverse de la fonction d'Ackermann, a été donné par Crochemore et. al.[11].

Notes et références modifier

Bibliographie modifier

  • 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,‎ , 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, no 3,‎ , 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,‎ , 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,‎ , 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, no 27,‎ , 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 » (no 9309), (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, no 5,‎ , 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), (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 » (no 3884), , p. 184–195
  • Jamie Simpson, « Modified Padovan words and the maximum number of runs in a word », Australas. J. Combin., vol. 46,‎ , 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 » (no 11088), (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,‎ , p. 143-151 (DOI 10.1016/j.tcs.2021.07.011)

Articles liés modifier