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 ${\displaystyle u}$ d'un mot ${\displaystyle x}$ rend compte de la nature répétitive d'un mot ${\displaystyle x}$, puisque ${\displaystyle x}$ est construit par la concaténation de copies du mot ${\displaystyle 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 ${\displaystyle x}$ est une facteur propre ${\displaystyle u}$ de ${\displaystyle x}$ tel que ${\displaystyle x}$ peut être construit à partir d'instances éventuellement chevauchantes de ${\displaystyle u}$.

Définitions

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

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

Couverture alignée

Étant donné un mot ${\displaystyle x}$, un facteur ${\displaystyle w}$ de ${\displaystyle x}$ tel que ${\displaystyle x}$ peut être construit par concaténation et superpositions de ${\displaystyle w}$ fournit une couverture alignée de ${\displaystyle x}$[1]. Le mot ${\displaystyle 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 ${\displaystyle x}$ est quasi-périodique.

Dans cette définition, le mot ${\displaystyle w}$ est à la fois préfixe et suffixe de ${\displaystyle x}$. Par exemple, le mot ${\displaystyle x=abaabababaaba}$ est quasi-périodique de mot couvrant ${\displaystyle w=aba}$ : ${\displaystyle 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 ${\displaystyle w=aabaa}$, les plus petits mots quasi-périodiques de période ${\displaystyle w}$ sont : ${\displaystyle aabaabaa}$,
${\displaystyle aabaaabaa}$,
${\displaystyle aabaabaabaa}$,
${\displaystyle aabaabaaabaa}$,
${\displaystyle aabaababaabaa}$. Le mot ${\displaystyle aabaabaaba}$ ne figure pas dans cette liste parce qu'il ne finit pas par ${\displaystyle w}$.

Un algorithme linéaire du calcul du mot couvrant le plus court est donné par Apostolico, Farach et Iliopoulos[2]. Un algorithme de calcul en ligne est de Dany Breslauer[3]. Apostolico et Ehrenfeucht[4] considèrent le calcul du plus long mot ouvrant ; ils décrivent un algorithme en ${\displaystyle O(n\log ^{2}n)}$ pour calculer tous les mots couvrants maximaux d'un mot de longueur ${\displaystyle 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 ${\displaystyle x=abaabaab}$ est périodique de période 3 et est quasi-périodique de germe ${\displaystyle abaab}$ ; de même ${\displaystyle x=abcabcabca}$ est quasi-périodique de période ${\displaystyle abca}$ : ${\displaystyle 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 ${\displaystyle x}$ est une couverture alignée d'un sur-mot (superstring) ${\displaystyle y}$ de ${\displaystyle x}$, c'est-à-dire d'un mot ${\displaystyle y}$ qui a ${\displaystyle x}$ en facteur. Par exemple, ${\displaystyle w=abca}$ est un germe de ${\displaystyle x=abc.abca.abc}$. Le mot ${\displaystyle w}$ est un germe (seed) de ${\displaystyle x}$. Un germe de longueur minimale n'est pas forcément unique ; ainsi ${\displaystyle abababa}$ a les deux germes ${\displaystyle ab}$ et ${\displaystyle ba}$. Un mot est quasi-périodique s'il possède une couverture dont le germe est un facteur strict du mot[4].

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

Exemples

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

Pour le mot ${\displaystyle 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 ${\displaystyle abaababaa}$ de longueur 9 a le bord ${\displaystyle abaa}$ de longueur 4, et n'a pas de couverture alignée, alors que ${\displaystyle abaab}$ est le germe d'une ouverture non alignée[5].

Table des bords et table des couvertures des préfixes de ${\displaystyle 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[6],[7] donnent un algorithme pour calculer toutes les couvertures d'un mot. Illiopoulos, Moore et Park[1] présentent un algorithme en ${\displaystyle O(n\log n)}$ pour trouver tous les germes d'un mot de longueur ${\displaystyle n}$. Une présentation générales et donnée dans Christou et al[8]. Les couvertures optimales ont été étudiées par Mhaskar et Smyth[9].

Caractérisation

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

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

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

où le morphisme ${\displaystyle f}$ est défini par ${\displaystyle f(a_{1})=aaba}$, ${\displaystyle f(a_{2})=aab}$, ${\displaystyle 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 ${\displaystyle w}$, en considérant les suffixes ${\displaystyle v_{i}}$ qui complètent un bord : ${\displaystyle w=b_{i}v_{i}}$. Pour ${\displaystyle w=aabaa}$, les suffixes sont ${\displaystyle w}$ lui-même, ${\displaystyle abaa}$ et ${\displaystyle baa}$, et la factorisation est

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

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

Variantes

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

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[12],[13] qui a suscité plusieurs travaux subséquents[14],[15],[16],[13].

L'exposant critique d'un mot infini quasi-périodique a été étudié par Gwenaël Richomme[17]. 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[18] 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 ${\displaystyle 2+\varepsilon }$ pour tout ${\displaystyle \varepsilon >0}$. Le plus petit exposant critique d'un mot infini binaire quasi-périodique est 7/3[17], 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[19].

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 ${\displaystyle ababaabaaa}$ contient les runs ${\displaystyle ababa}$, ${\displaystyle aa}$, ${\displaystyle abaabaa}$ et ${\displaystyle 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 ${\displaystyle x}$ de longueur ${\displaystyle n}$ est la table ${\displaystyle B}$ à ${\displaystyle n}$ éléments donnant, pour chaque indice ${\displaystyle i}$, le plus long bord du préfixe de longueur ${\displaystyle i}$ du mot ${\displaystyle x}$. Par analogie, table des couvertures d'un mot ${\displaystyle x}$ de longueur ${\displaystyle n}$ est la table ${\displaystyle C}$ à ${\displaystyle n}$ éléments donnant, pour chaque indice ${\displaystyle i}$, la plus longue couverture alignée du préfixe de longueur ${\displaystyle i}$ du mot ${\displaystyle x}$, si ce préfixe possède un mot couvrant, et 0 sinon[5].

Par exemple[5], pour le mot ${\displaystyle x=abaababaabaababaabababa}$ de longueur 23, le préfixe ${\displaystyle abaababaa}$ de longueur 9 a le bord ${\displaystyle abaa}$ de longueur 4, et n'a pas de couverture alignée, alors que ${\displaystyle 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

Notes et références

1. Costas S. Iliopoulos, D. W. G. Moore et K. Park, « Covering strings », Algorithmica, vol. 16, n^o 3,‎ 1996, p. 288–297 (ISSN 0178-4617, DOI 10.1007/BF01955677).
2. Alberto Apostolico, Martin Farach et Costas S. Iliopoulos, « Optimal superprimitivity testing for strings », Information Processing Letters, vol. 39, n^o 1,‎ 1991, p. 17–20 (ISSN 0020-0190, DOI 10.1016/0020-0190(91)90056-N)
3. Dany Breslauer, « An on-line string superprimitivity test », Information Processing Letters, vol. 44, n^o 6,‎ 1992, p. 345–347 (ISSN 0020-0190, DOI 10.1016/0020-0190(92)90111-8).
4. Alberto Apostolico et Andrzej Ehrenfeucht, « Efficient detection of quasiperiodicities in strings », Theoretical Computer Science, vol. 119, n^o 2,‎ 1993, p. 247–265 (DOI 10.1016/0304-3975(93)90159-Q).
5. Yin Li et William F. Smyth, « Computing the cover array in linear time », Algorithmica, vol. 32, n^o 1,‎ 2002, p. 95-106 (ISSN 0178-4617, DOI 10.1007/s00453-001-0062-2)
6. Dennis W. G. Moore et William F. Smyth, « An optimal algorithm to compute all the covers of a string », Information Processing Letters, vol. 50, n^o 5,‎ 1994, p. 239–246 (ISSN 0020-0190, DOI 10.1016/0020-0190(94)00045-X).
7. Dennis W. G. Moore et William F. Smyth, « A Correction to "An Optimal Algorithm to Compute all the Covers of a String" », Information Processing Letters, vol. 54, n^o 2,‎ 1995, p. 101-103 (DOI 10.1016/0020-0190(94)00235-Q)
8. Michalis Christou, Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Bartosz Szreder et Tomasz Waleń, « Efficient Seeds Computation Revisited », Lecture Notes in Computer Science, vol. 6661,‎ 2011, p. 350–363 (ISSN 0302-9743, DOI 10.1007/978-3-642-21458-5_30)
9. Neerja Mhaskar et William F. Smyth, « String covering with optimal covers », Journal of Discrete Algorithms, vol. 51,‎ 2018, p. 26–38 (ISSN 1570-8667, DOI 10.1016/j.jda.2018.09.003)
10. Laurent Mouchard, « Normal forms of quasiperiodic strings », Theoretical Computer Science, vol. 249, n^o 2,‎ 2000, p. 313–324 (DOI 10.1016/S0304-3975(00)00065-7).
11. Tomáš Flouri, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Simon J. Puglisi, William F. Smyth et Wojciech Tyczyński, « Enhanced string covering », Theoretical Computer Science, vol. 506,‎ 2013, p. 102–114 (ISSN 0304-3975, DOI 10.1016/j.tcs.2013.08.013)
12. Solomon Marcus, « Quasiperiodic Infinite Words », Bulletin of the EATCS, n^o 82,‎ 2004, p. 170-174.
13. Florence Levé et Gwenaël Richomme, « On quasiperiodic morphisms », Proceedings of the 9th International Conference on Words,‎ 2013, p. 181-192 (DOI 10.1007/978-3-642-40579-2_20).
14. Amy Glen, Florence Levé et Gwénaël Richomme, « Quasiperiodic and Lyndon episturmian words », Theoretical Computer Science, vol. 409, n^o 3,‎ 2008, p. 578–600 (DOI 10.1016/j.tcs.2008.09.056).
15. Florence Levé et Gwenaël Richomme, « Quasiperiodic infinite words: some answers », Bulletin of the EATCS, n^o 84,‎ 2004, p. 128-138.
16. Florence Levé et Gwenaël Richomme, « Quasiperiodic Sturmian words and morphisms », Theoretical Computer Science, vol. 372, n^o 1,‎ 2007, p. 15–25 (DOI 10.1016/j.tcs.2006.10.034).
17. Gwenaël Richomme, « Minimal critical exponent of quasiperiodic words », Theoretical Computer Science, vol. 548,‎ 2014, p. 117–122 (DOI 10.1016/j.tcs.2014.06.039).
18. Dalia Krieger et Jeffrey Shallit, « Every real number greater than 1 is a critical exponent », Theoretical Computer Science, vol. 381, n^os 1-3,‎ 2007, p. 177–182 (DOI 10.1016/j.tcs.2007.04.037)
19. Juhani Karhumäki et Jeffrey Shallit, « Polynomial versus exponential growth in repetition-free binary words », Journal of Combinatorial Theory, Series A, vol. 105, n^o 2,‎ 2004, p. 335–347 (DOI 10.1016/j.jcta.2003.12.004).

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