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

Le théorème des répétitions maximales (en anglais Modèle:Citation étrangère) qui s’appelait, avant d'avoir été démontrée, la conjecture des répétitions maximales (en anglais Modèle:Citation étrangère) 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

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 $n$ est au plus $n-3$.

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

Définitions

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 $w=$aababaababb, les répétitions maximales sont $w[1,2]=w[6,7]=$aa, $w[10,11]=$bb, de période 1, $w[2,6]=$ababa et $w[7,10]=$ababa de période 2, $w[4,9]=$abaaba de période 3, et enfin $w[1,10]=$ (abbab)$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 $n$ est noté $\rho (n)$.

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

$\rho (n)\le n-3$,

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

Historique

Crochemore et. al. et Bannai et. al. retracent l'historique de la conjecture : la conjecture a été formulée par Kolpakov et Kucherov en 1999; ces auteurs ont prouvé que $\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 qui a montré que $\rho (n)<5n$. Une des meilleures estimations précédant la démonstration finale donne $\rho (n)<1,029n$. Une variante du théorème des runs final a été présenté par les mêmes auteurs en Modèle:Date- à la conférence SODA. Dans cet article, l'inégalité est $\rho (n)<1,5n$.

Résultats et discussion

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, une 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. Une 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ş

Dans le même article, les auteurs prouvent que la somme, notée $\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é ${\rho }_k(n)$ de répétitions maximales d'exposant au moins k et la somme ${\sigma }_k(n)$ des longueurs de ces répétitions. Là aussi, la nouvelle méthode permet d'obtenir des bornes meilleures, à savoir ${\rho }_k(n)<2n/(k-1)$ et ${\sigma }_k(n)<n(k+1)/(k-1)$. Pour k=3 par exemple, on obtient ${\sigma }_k(n<2n$, meilleur que le résultat de Crochemore et. al.. Pour des alphabets de taille plus importante, les majorations sont $\rho (n,d)\le n-d$, et même $\rho (n,d)\le n-d-1$ si $n>2d$, où $\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 $\rho (n)>0,944575712n$. Ce qui donne l'encadrement : $0,944n<\rho (n)<0,957n$, la deuxième étant une approximation de 22/23.

Éléments de démonstration

La démonstration esquissée ci-dessous provient de l'exposé de Tomohiro I au colloque DLT 2018. 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 $w$ avait un bord $x$, ce mot $x$ est un préfixe de $w$, donc $x<w$, et un suffixe de $w$, donc $w<x$ parce qu'un mot de Lyndon est plus petit que ses suffixes.

Racine de Lyndon

Tout run de période $p$ contient en facteur un mot de Lyndon de longueur $p$. 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. La racine de Lyndon d'une répétition est unique.

Runs cubiques

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 cubiques n'ont pas de frontière commune : supposons au contraire que deux carrés de racines de Lyndon $x\cdot x$ et $y\cdot y$ ont la même frontière, et que $x$ est plus court que $y$ ; alors $x$ est suffixe de $y$ par la première occurrence et préfixe de $y$ par la deuxième occurrence, donc $x$ serait un bord de $y$, 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 $n$ ne peut avoir plus de $n$ runs cubiques. En fait, on peut améliorer cette borne en $n/2$; en considérant non seulement un ordre lexicographique donné mais aussi son ordre opposé (avec $x{<}^{R}y$ si et seulement si $y<x$). Ainsi, le mot

cbabacbabacbabac

a pour le préfixe le cube de cbaba qui, pour l'ordre opposé $c<b<a$, 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.

Cas général

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 $r=(i,j,p)$ composé du facteur w[i,j] et de période p, on note $S(r)$ l'ensemble des débuts des positions des racines de Lyndon globales, pour l'ordre < et son opposé, à l'exception de la position $i$. On a alors les deux propriétés :

$S(r)\ne \mathrm{\varnothing }$ et, si $r\ne r^{\prime }$, alors $S(r)\cap S(r^{\prime })=\mathrm{\varnothing }$.

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

Calcul des runs

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

Bibliographie

• Modèle:Article.
• Modèle:Article
• Modèle:Article.
• Modèle:Article.
• Modèle:Article
• Modèle:Chapitre
• Modèle:Article
• Modèle:Chapitre
• Modèle:Chapitre
• Modèle:Article
• Modèle:Chapitre.
• Modèle:Article

Articles liés

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