Algorithmique du texte

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.

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

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, à 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

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 $x$ appelé motif et un mot $t$ appelé texte, on cherche une ou toutes les occurrences de $x$ dans $t$. Par exemple, le motif $x=010$ apparaît deux fois dans $t=001010$, à 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, la construction de lexiques. Les algorithmes les plus anciens et les plus connus sont :

• Algorithme d'Aho-Corasick
• Algorithme de Boyer-Moore et sa variante, l'algorithme de Boyer-Moore-Horspool
• Algorithme de Knuth-Morris-Pratt
• Algorithme de Rabin-Karp

On trouve aussi la notion plus théorique d'automate des occurrences. C'est l'automate fini qui reconnaît le langage formel $A^{*}x$ des mots sur l'alphabet $A$ qui se terminent par le motif $x$. Cet automate a $m+1$ états (où $m$ est la longueur du motif $m$), et possède au plus $2m$ 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.

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

Recherche approximative

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é

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

• distance de Hamming, la plus ancienne des distances
• distance de Levenshtein et Distance de Damerau-Levenshtein, la distance d'édition et la distance d'édition avec transposition
• distance de Jaro-Winkler

Alignement de séquences

• Algorithme de Needleman-Wunsch
• Algorithme de Smith-Waterman
• transformée de Burrows-Wheeler
• Soundex, un algorithme phonétique d'indexation de noms par leur prononciation.
• mesure cosinus utilisée dans la fouille de textes
• TF-IDF utilisée dans la fouille de textes

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

Périodes locales

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 qui 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. Avec la même technique et en utilisant des calculs en machine, ce résultat a été affiné Le nombre est asymptotiquement au plus (22/23)n <0.957n.

Bibliographie

Ouvrages

• Maxime Crochemore, Christophe Hancart et Thierry Lecroq, Algorithmique du texte, Vuibert, 2001, 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, 2007, 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, 1997, 534 p. (ISBN 978-0-521-58519-4)
• (en) Maxime Crochemore et Wojciech Rytter, Jewels of stringology, World Scientific Publishing, 2002, 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 » (n^o 9309), 2015 (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, juin 2015.

Conférences

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

• Combinatorial Pattern Matching (CPM). La 26^e des conférences annuelles a eu lieu en Italie du 29 juin au 1^er juillet 2015 : Ferdinando Cicalese, Ely Porat et Ugo Vaccaro (éditeurs), Combinatorial Pattern Matching : 26th Annual Symposium, CPM 2015, Ischia, Italy, Springer-Verlag, coll. « Lecture Notes in Computer Science » (n^o 9133), 2015 (ISBN 978-3-319-19929-0, BNF 44680034, DOI 10.1007/978-3-319-19929-0, SUDOC 186399472)
• The Prague Stringology Conference
• Symposium on String Processing and Information Retrieval (SPIRE) ; la 28^e conférence a lieu à Lille du 4-6 octobre 2021.

Annexes

Articles connexes

• Plus longue sous-séquence commune
• Plus longue sous-chaîne commune
• Plus courte super-séquence commune
• Théorème des répétitions maximales

Liens externes

• Construction d'Arbres de Suffixes. Introduction à la construction et à l'utilisation d'arbres de suffixes, présentation et comparaison des algorithmes de Ukkonen et de Hunt avec l'approche TDD.
• (en) Algorithmes de recherche de chaine – programmes.
• (en) StringSearch – high-performance pattern matching algorithms in Java – implémentations des algorithmes BNDM, Boyer-Moore-Horspool, Boyer-Moore-Horspool-Raita et Shift-Or en Java.