Algorithmique du texte

domaine de l'algorithmique dans lequel les objets à traiter sont des textes.

L'algorithmique du texte est le domaine de l'algorithmique dans lequel les objets à traiter sont des textes, c'est-à-dire des chaînes de caractères ou suites de symboles. On trouve aussi le terme stringologie, venant du mot anglais string pour chaîne de caractères[1].

Parmi les problèmes importants du domaine, on compte par exemple la localisation de motifs textuels, l’indexation de données textuelles, la recherche de sous-chaîne, la comparaison de textes par l'alignement de séquences et l'étude des mesures de similarité, la recherche de régularités locales. Selon les auteurs, le domaine peut être plus large et contenir notamment les tris et l'analyse syntaxique.

Les algorithmes font souvent appel à la construction et l'analyse de structures de données élaborées, comme les arbres des suffixes, des automates finis spécifiques, ou des structures à accès direct comme les tables de préfixes ou des suffixes.

En amont se place la combinatoire des mots qui étudie les propriétés combinatoires de chaînes de caractères; en aval, on trouve des algorithmes intégrés dans des systèmes, comme grep sous Unix, ou BLAST pour la comparaison de séquences biologiques.

Applications

modifier

Les méthodes de l'algorithmique du texte s'appliquent au traitement de la langue naturelle, au traitement et à l'analyse des séquences génétiques en bioinformatique[2], à l'analyse de séquences musicales, aux flux de données, à la gestion de bases de données textuelles, mais aussi trouvent aussi leur place dans le tatouage numérique, la détection de plagiats, l'analyse d'image, l'apprentissage automatique, ou l'exploration de données.

La cryptographie et la compression de données, qui pourraient relever de la définition, sont généralement considérées comme des domaines autonomes.

Localisation de motifs textuels

modifier

La recherche d'une chaîne ou d'un motif dans un texte est parmi les plus anciens, et des plus fouillés, des problèmes de l'algorithmique du texte. Étant donné un mot   appelé motif et un mot   appelé texte, on cherche une ou toutes les occurrences de   dans  . Par exemple, le motif   apparaît deux fois dans  , à la position 2 et 4.

On distingue deux grandes classes de situations : le motif est connu et le texte ne l'est pas, ou au contraire le texte est connu et le motif cherché ne l’est pas. Selon les cas, c'est le motif ou le texte qui se prête à un prétraitement qui permet ensuite des gains de temps et de place. Les algorithmes comme l'algorithme de Knuth-Morris-Pratt sont de la première classe : le motif est prétraité et le temps est linéaire en la taille du texte. L'arbre des suffixes est une structure de données qui permet de stocker le texte, et de trouver le ou les occurrences d'un motif en temps linéaire en fonction de la taille du motif. Alors que la première classe d'algorithmes est la recherche d'un motif plus proprement, la deuxième est appelée, dans l'ouvrage de Crochemore et. al. par exemple[3], la construction de lexiques. Les algorithmes les plus anciens et les plus connus sont :

On trouve aussi la notion plus théorique d'automate des occurrences. C'est l'automate fini qui reconnaît le langage formel   des mots sur l'alphabet   qui se terminent par le motif  . Cet automate a   états (où   est la longueur du motif  ), et possède au plus   transitions avant (des transitions qui ne retournent pas vers l'état initial). Il se construit en temps linéaire et prend donc une place linéaire[3].

Deux variantes importantes de la recherche de motifs existent : la recherche approchée et la recherche dans des données compressées.

Recherche approximative

modifier

La recherche approximative, souvent appelée aussi recherche approchée, consiste, comme son nom l'indique, à trouver les occurrences approximatives d'un motif dans un texte, comme dans l'algorithme de Baeza-Yates-Gonnet. Le problème se découpe naturellement en deux sous-problèmes: trouver les occurrences proches d'un motif dans un texte, et trouver les occurrences approximatives d'un motif dans une base de textes. Dans le premier cas, on autorise des variations sur le motif, dans le deuxième des variations sur les segments de texte.

Une première notion d'approximation est la présence de jokers. Un joker est un symbole qui représente l'alphabet tout entier, et qui s'accorde à toute lettre. Ainsi, il y a occurrence d'un motif dans un texte si les lettres coïncident, aux jokers près. Les jokers peuvent figurer dans le motif ou dans les textes.

Une deuxième est basée sur une mesure de similarité.

Mesures de similarité

modifier

Comme leur nom l'indique, ce sont des outils permettant d'évaluer la distance qui sépare deux chaînes. Elles servent à la fouille de textes, où à la comparaison entre mots.

Les mesures de similarités sont

Alignement de séquences

modifier

Les distances courantes en mathématiques, comme la distance de Manhattan, la distance euclidienne, la distance de Tchebychev.

Périodes locales

modifier

L'étude des répétitions locales dans les textes a des applications importantes, dans la recherche de motifs, 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, le théorème des répétitions maximales é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 binaire de longueur n est au plus n-3[4]. Avec la même technique et en utilisant des calculs en machine, ce résultat a été affiné[5] Le nombre est asymptotiquement au plus (22/23)n <0.957n.

Notes et références

modifier

Bibliographie

modifier
Ouvrages
  • Maxime Crochemore, Christophe Hancart et Thierry Lecroq, Algorithmique du texte, Vuibert, , 347 p. (ISBN 978-2-7117-8628-2, lire en ligne).
  • (en) Maxime Crochemore, Christophe Hancart et Thierry Lecroq, Algorithms on strings, Cambridge University Press, , 383 p. (ISBN 978-0-521-84899-2) — Traduction revue et corrigée du livre en français
  • (en) Dan Gusfield, Algorithms on strings, trees, and sequences : Computer science and computational biology, Cambridge University Press, , 534 p. (ISBN 978-0-521-58519-4)
  • (en) Maxime Crochemore et Wojciech Rytter, Jewels of stringology, World Scientific Publishing, , 310 p. (ISBN 978-981-02-4782-9)
Articles cités
  • 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, Kazuya Tsuruta, « The "Runs" theorem », sur arXiv.org, .

Conférences

modifier

Des conférences régulières sur l'algorithmique du texte sont organisées, notamment :

Annexes

modifier

Articles connexes

modifier

Liens externes

modifier