Algorithmique du texte

L'algorithmique du texteest le domaine de l'algorithmiquedans lequel les objets à traiter sont des textes, c'est-à-dire deschaînes de caractèresou suites de symboles. On trouve aussi le termestringologie,venant du mot anglaisstringpour 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, larecherche de sous-chaîne,la comparaison de textes par l'alignement de séquenceset l'étude desmesures de similarité,la recherche de régularités locales. Selon les auteurs, le domaine peut être plus large et contenir notamment lestriset l'analyse syntaxique.

Les algorithmes font souvent appel à la construction et l'analyse de structures de données élaborées, comme lesarbres 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 lacombinatoire des motsqui é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, commegrepsousUnix,ouBLASTpour la comparaison de séquences biologiques.

Applications

Les méthodes de l'algorithmique du texte s'appliquent au traitement de lalangue naturelle,au traitement et à l'analyse des séquences génétiques enbioinformatique^[2],à l'analyse de séquences musicales, aux flux de données, à la gestion debases de donnéestextuelles, mais aussi trouvent aussi leur place dans letatouage numérique,ladétection de plagiats,l'analyse d'image,l'apprentissage automatique, ou l'exploration de données.

Lacryptographieet lacompression 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

Article détaillé:Algorithme de recherche de sous-chaîne.

La recherche d'une chaîne ou d'unmotifdans 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émotifet un mot $t$ appelétexte,on cherche une ou toutes lesoccurrencesde $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-Prattsont de la première classe: le motif est prétraité et le temps est linéaire en la taille du texte. L'arbre des suffixesest 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],laconstruction 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 finiqui 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^[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

Article détaillé:Recherche approximative.

Larecherche approximative,souvent appelée aussirecherche 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 dejokers.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é

Article détaillé:Mesure de similarité.

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

Les mesures de similarités sont

distance de Hamming,la plus ancienne des distances
distance de LevenshteinetDistance 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,unalgorithme phonétiqued'indexation de noms par leur prononciation.
mesure cosinusutilisée dans lafouille de textes
TF-IDFutilisée dans lafouille de textes

Lesdistancescourantes en mathématiques, comme ladistance de Manhattan,ladistance euclidienne,ladistance de Tchebychev.

Périodes locales

L'étude des répétitions locales dans les textes a des applications importantes, dans la recherche de motifs, lacompression de données,l'analyse musicale,l'analyse deséquences biologiques,etc. Un intérêt particulier a été porté à l'étude desrépétitions maximales,appeléesrunsen 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, lethéorème des répétitions maximalesétablit ce qui, pendant une quinzaine d'années, était appelée laconjecture 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 (deruns) dans un mot binaire de longueurnest 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

↑Par exemple dansJewels of stringology(2002).
↑Cour deMathieu Raffinot, «Introduction à l’algorithmique du texte pour la bioinformatique»,2010.
↑^aetbAlgorithmique du texte (2001)
↑Bannaiet. al.(arXiv).
↑Fischeret. al..

Bibliographie

Ouvrages

Maxime Crochemore,Christophe Hancart et Thierry Lecroq,Algorithmique du texte,Vuibert,2001,347p.(ISBN 978-2-7117-8628-2,lire en ligne).
(en)Maxime Crochemore, Christophe Hancart et Thierry Lecroq,Algorithms on strings,Cambridge University Press,2007,383p.(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,534p.(ISBN 978-0-521-58519-4)
(en)Maxime Crochemore et Wojciech Rytter,Jewels of stringology,World Scientific Publishing,2002,310p.(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^o9309),2015(ISBN 978-3-319-23825-8,DOI10.1007/978-3-319-23826-5_27,arXiv1502.04644.pdf),p.277-286
Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Kazuya Tsuruta, «The "Runs" theorem», surarXiv.org,juin 2015.

Conférences

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

Combinatorial Pattern Matching(CPM). La26^edes conférences annuelles a eu lieu en Italie du29 juinau1^erjuillet 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^o9133),2015(ISBN 978-3-319-19929-0,BNF44680034,DOI10.1007/978-3-319-19929-0,SUDOC186399472)
The Prague Stringology Conference
Symposium on String Processing and Information Retrieval(SPIRE);la28^econférence a lieu à Lille du 4-6 octobre 2021.

Annexes

Articles connexes

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.

[1] Par exemple dansJewels of stringology(2002).

[2] Cour deMathieu Raffinot, «Introduction à l’algorithmique du texte pour la bioinformatique»,2010.

[AdT-3] tbAlgorithmique du texte (2001)

[4] Bannaiet. al.(arXiv).

[5] Fischeret. al..

[1]

[2]

[3]

[4]

[5]

v·m Algorithmique du texte
Recherche de sous-chaîne	Algorithme de Knuth-Morris-Pratt Algorithme de Boyer-Moore Algorithme de Boyer-Moore-Horspool Algorithme de Raita Algorithme de Baeza-Yates-Gonnet Algorithme Z Algorithme de Rabin-Karp Algorithme d'Aho-Corasick
Alignement de chaînes	Algorithme de Needleman-Wunsch Algorithme de Smith-Waterman Transformée de Burrows-Wheeler
Mesure de similarité	Distance de Jaro-Winkler Distance de Levenshtein Distance de Hamming
Arbre des suffixes	Algorithmes de Weiner et de McCreight Algorithme d'Ukkonen Tableau des suffixes Tableau de Lyndon
Comparaisons	Plus longue sous-séquence commune Plus longue sous-chaîne commune Plus courte super-séquence commune

v·m Informatique théorique
Codage	Codage de l'information Compression de données Chiffrement Cryptanalyse Cryptographie Théorie de l'information
Modèles de calcul	Calculabilité Décidabilité et indécidabilité Ensemble récursif Problème de l'arrêt Ensemble récursivement énumérable Machine de Turing Thèse de Church Automate cellulaire Réseau de neurones artificiels Réduction polynomiale Problème NP-complet Principe de Church-Turing-Deutsch
Algorithmique	Algorithmique Algorithme glouton Algorithme probabiliste Algorithme génétique Complexité algorithmique Analyse d'algorithme Diviser pour régner Heuristique Programmation dynamique Géométrie algorithmique Algorithmes de tri Algorithmique du texte Exploration de données Science des données Apprentissage profond Test de primalité Structure de données Arbre enraciné Concurrence Parallélisme
Syntaxe	Réécriture Compilation Expression régulière Grammaire formelle Langage rationnel Ensemble rationnel Théorie des langages Théorie des automates Automate fini Automate sur les mots infinis Automate d'arbres Automate à pile Hiérarchie de Chomsky Linguistique informatique
Sémantique	Interprétation abstraite Méthodes formelles Vérification de modèles Sémantique des langages de programmation Sémantique dénotationnelle Sémantique axiomatique Sémantique opérationnelle
Logique mathématique	Assistant de preuve Calcul des prédicats Correspondance de Curry-Howard Fonction récursive Lambda-calcul Théorèmes d'incomplétude de Gödel Théorie des types
Mathématiques discrètes	Combinatoire Algorithme du simplexe Optimisation combinatoire Théorie des graphes Algorithmes de la théorie des graphes Recherche opérationnelle Théorie de la décision Analyse numérique