Mot quasi-périodique

En combinatoire, et plus particulièrement en combinatoire des mots, un mot quasi-périodique est un mot fini ou infini qui peut être construit par concaténations ou superpositions d'un de ses facteurs propres. La notion de mot quasi-périodique généralise celle de mot périodique.

Motivation

Les régularités dans les chaînes de caractères sont étudiées dans divers domaines scientifiques, comme la combinatoire, le codage et la compression, la théorie des automates, la biologie moléculaire, les langages formels, la théorie des systèmes. Une structure typique de régularité est la répétition dans une mot ; la période $u$ d'un mot $x$ rend compte de la nature répétitive d'un mot $x$, puisque $x$ est construit par la concaténation de copies du mot $u$. On généralise cette notion en permettant de chevauchement entre des occurrences du segment répété. Une quasi-période d'un mot $x$ est une facteur propre $u$ de $x$ tel que $x$ peut être construit à partir d'instances éventuellement chevauchantes de $u$.

Définitions

Un mot est $x=a_{1}\cdots a_{n}$ est périodique s'il existe un entier $p$, avec $0<p<n$ tel que $a_{i}=a_{i+p}$ pour $1\leq i<i+p\leq n$ ; le plus petit entier $p$ avec cette propriété est la période minimale, ou la période tout court ; un facteur de longueur $p$ est un motif périodique, appelé aussi lui-même une période du mot. Par exemple, le mot $x=abaabaab=aba.aba.ab$ est périodique de période 3.

Si $s=uv$ et $t=vw$ sont deux mots, alors le mot $uvw(=sw=ut)$ est une superposition de $s$ et $t$. On est intéressé par des superpositions d'un même facteur dans un mot : si $s=t$, le mot$uvw=sw=ut$ peut être vu comme le produit du préfixe $u$ de $s$ par le mot $s$ lui-même, ou comme produit de $s$ par le suffixe $w$ de $s$. Ainsi pour $s=aba$, le mot $ababa$ s'écrit $ab\cdot aba=aba{\cdot }ba$.

Couverture alignée

Étant donné un mot $x$, un facteur $w$ de $x$ tel que $x$ peut être construit par concaténation et superpositions de $w$ fournit une couverture alignée de $x$. Le mot $w$ est lui-même appelé un mot couvrant, ou germe (seed en anglais), le mot couvrant le plus court est appelé la quasi-période, et le mot $x$ est quasi-périodique.

Dans cette définition, le mot $w$ est à la fois préfixe et suffixe de $x$. Par exemple, le mot $x=abaabababaaba$ est quasi-périodique de mot couvrant $w=aba$ : $x=aba.ab.ab.aba.aba$. Dans cette écriture, on factorise le mot en préfixes du mot couvrant. La factorisation commence et finit par le mot couvrant tout entier : ainsi la factorisation est « alignée » sur les extrémités du mot, ce qui justifie la terminologie. Un mot est super-primitif s'il ne possède pas de couverture alignée.

Pour le mot $w=aabaa$, les plus petits mots quasi-périodiques de période $w$ sont : $aabaabaa$,
$aabaaabaa$,
$aabaabaabaa$,
$aabaabaaabaa$,
$aabaababaabaa$. Le mot $aabaabaaba$ ne figure pas dans cette liste parce qu'il ne finit pas par $w$.

Un algorithme linéaire du calcul du mot couvrant le plus court est donné par Apostolico, Farach et Iliopoulos. Un algorithme de calcul en ligne est de Dany Breslauer. Apostolico et Ehrenfeucht considèrent le calcul du plus long mot ouvrant ; ils décrivent un algorithme en $O(n\log ^{2}n)$ pour calculer tous les mots couvrants maximaux d'un mot de longueur $n$.

Couverture

La définition ci-dessus fait qu'un mot qui est périodique n'a pas toujours une couverture alignée de même période. Par exemple, le mot $x=abaabaab$ est périodique de période 3 et est quasi-périodique de germe $abaab$ ; de même $x=abcabcabca$ est quasi-périodique de période $abca$ : $x=abc.abc.abca$, mais a période minimale 3.

C'est pourquoi on considère une notion plus générale : une couverture de $x$ est une couverture alignée d'un sur-mot (superstring) $y$ de $x$, c'est-à-dire d'un mot $y$ qui a $x$ en facteur. Par exemple, $w=abca$ est un germe de $x=abc.abca.abc$. Le mot $w$ est un germe (seed) de $x$. Un germe de longueur minimale n'est pas forcément unique ; ainsi $abababa$ a les deux germes $ab$ et $ba$. Un mot est quasi-périodique s'il possède une couverture dont le germe est un facteur strict du mot.

Dans cette notion plus générale, un mot périodique est aussi quasi-périodique de cette longueur.

Exemples

Pour $x=ababaababa$, les mots $aba$ et $ababa$ fournissent des couvertures alignées puisque $x=ab.aba.ab.aba=ababa.ababa$ ; les mots $aba,ababa,baaba$ et $baabab$ sont tous des germes de $x$ : les couvertures par $aba$ et $ababa$ sont celles de $x$ lui-même ; celle par $baaba$ est $baxaba=baaba.baaba.baaba$ et celle par $baabab$ est $baxabab$.

Pour le mot $x=abaababaabaababaabababa$ de longueur 23, la table ci-dessous donne, pour chaque préfixe, la longueur du plus long bord et la longueur de la plus petite couverture. Ainsi, le préfixe $abaababaa$ de longueur 9 a le bord $abaa$ de longueur 4, et n'a pas de couverture alignée, alors que $abaab$ est le germe d'une ouverture non alignée.

Table des bords et table des couvertures des préfixes de $x=abaababaabaababaabababa$

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23
x	a	b	a	a	b	a	b	a	a	b	a	a	b	a	b	a	a	b	a	b	a	b	a
B	0	0	1	1	2	3	2	3	4	5	6	4	5	6	7	8	9	10	11	7	8	2	3
C	0	0	0	0	0	3	0	3	0	5	6	0	5	6	0	8	9	10	11	0	8	0	3

Moore et Smyth donnent un algorithme pour calculer toutes les couvertures d'un mot. Illiopoulos, Moore et Park présentent un algorithme en $O(n\log n)$ pour trouver tous les germes d'un mot de longueur $n$. Une présentation générales et donnée dans Christou et al. Les couvertures optimales ont été étudiées par Mhaskar et Smyth.

Caractérisation

Un caractérisation des mots quasi-périodiques a été donnée par L. Mouchard.

Étant donné un mot $w$ qui jouera le rôle d'une quasi-période, soient $b_{1}=\varepsilon ,b_{2},\ldots ,b_{k}$ les bords de $w$ (un bord est un facteur qui est à la fois préfixe est suffixe); et soient $u_{1},\ldots ,u_{k}$ les préfixes de $w$ tels que $w=u_{i}b_{i}$. Alors tout mot $x$ quasi-périodique de période $w$ est l’image d’un mot sur un alphabet à $k$ lettres $a_{1},\ldots ,a_{k}$ par le morphisme qui envoie $a_{i}$ sur $u_{i}$. De manière équivalente, $x$ est produit des mots $u_{i}$. Par exemple, le mot $x=aabaaabaabaa$ est quasi-périodique de quasi-période $aabaa$. Il s’écrit comme produit

$x=aaba.aab.aabaa=f(a_{1}a_{2}a_{3})$,

où le morphisme $f$ est défini par $f(a_{1})=aaba$, $f(a_{2})=aab$, $f(a_{3})=aab$.

Une façon équivalente, un mot quasi-périodique peut s'écrire comme produit de suffixes d'une quasi-période $w$, en considérant les suffixes $v_{i}$ qui complètent un bord : $w=b_{i}v_{i}$. Pour $w=aabaa$, les suffixes sont $w$ lui-même, $abaa$ et $baa$, et la factorisation est

$x=aabaa.abaa.baa=g(a_{1}a_{2}a_{3})$,

où le morphisme $g$ est défini par $g(a_{1})=aabaa$, $g(a_{2})=abaa$, $g(a_{3})=baa$.

Variantes

Une couverture améliorée (enhanced en anglais) $u$ de $x$ est un bord de $x$ (c'est-à-dire un préfixe propre qui est aussi un suffixe) qui couvre un nombre maximal de positions en $x$, mais pas nécessairement toutes.

Mots infinis

Solomon Marcus a étendu la notion de mot quasi-périodique aux mots infinis et a posé à cette occasion diverses questions dans un article au bulletin de l'EATCS qui a suscité plusieurs travaux subséquents.

L'exposant critique d'un mot infini quasi-périodique a été étudié par Gwenaël Richomme. L'exposant critique d'un mot est le maximum des exposants des répétitions contenues dans le mot.

On sait, d'après un résultat de Dana Krieger et J. Shallit que tout nombre réel plus grand que 1 peut être l'exposant critique d'un mot infini. Un mot infini périodique a un exposant critique infini. Il n'en est pas ainsi pour les mots quasi-périodique : il existe des mots infinis quasi-périodiques dont l'exposant critique est $2+\varepsilon$ pour tout $\varepsilon >0$. Le plus petit exposant critique d'un mot infini binaire quasi-périodique est 7/3, et tout mot infini binaire contient une répétition d'exposant au moins 7/3. Ces résultats reposent sur des propriétés décrites par J. Karhumäki et J. Shallit.

On peut faire le lien entre l'exposant critique et la notion de run. Un run est une répétition maximale dans un mot, pourvu que l'exposant en soit au moins égal à 2. Par exemple, le mot $ababaabaaa$ contient les runs $ababa$, $aa$, $abaabaa$ et $aaa$ d'exposants 5/2, 2, 7/3 et 3 respectivement. L'exposant critique de ce mot est donc 3.

Table des couvertures

La table des couvertures est l'analogue, pour les quasi-périodes, de la table des bords d'un mot : la table des bords d'un mot $x$ de longueur $n$ est la table $B$ à $n$ éléments donnant, pour chaque indice $i$, le plus long bord du préfixe de longueur $i$ du mot $x$. Par analogie, table des couvertures d'un mot $x$ de longueur $n$ est la table $C$ à $n$ éléments donnant, pour chaque indice $i$, la plus longue couverture alignée du préfixe de longueur $i$ du mot $x$, si ce préfixe possède un mot couvrant, et 0 sinon.

Par exemple, pour le mot $x=abaababaabaababaabababa$ de longueur 23, le préfixe $abaababaa$ de longueur 9 a le bord $abaa$ de longueur 4, et n'a pas de couverture alignée, alors que $abaab$ est le germe d'une ouverture non alignée.

Table des bords et table des couvertures

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23
x	a	b	a	a	b	a	b	a	a	b	a	a	b	a	b	a	a	b	a	b	a	b	a
B	0	0	1	1	2	3	2	3	4	5	6	4	5	6	7	8	9	10	11	7	8	2	3
C	0	0	0	0	0	3	0	3	0	5	6	0	5	6	0	8	9	10	11	0	8	0	3

Articles liés

• Mot infini
• Mot sturmien
• Exposant critique
• Mot de Lyndon
• Répétitions dans un mot
• Algorithme de recherche de sous-chaîne
• Tableau des suffixes