Voir la source de Algorithmique du texte

{{Confusion|texte=Ne pas confondre avec [[traitement de texte]]}}
L''''algorithmique du texte''' est le domaine de l'[[algorithmique]] dans lequel les objets à traiter sont des textes, c'est-à-dire des [[chaîne de caractères|chaînes de caractères]] ou suites de symboles. On trouve aussi le terme ''stringologie'', venant du mot anglais ''{{lang|en|string}}'' pour chaîne de caractères<ref>Par exemple dans {{harvsp|''Jewels of stringology'' (2002)|id=Jewels}}.</ref>.

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

Les algorithmes font souvent appel à la construction et l'analyse de [[Structure de données|structures de données]] élaborées, comme les [[Arbre des suffixes|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 [[Langage naturel|langue naturelle]], au traitement et à l'analyse des séquences génétiques en [[bioinformatique]]<ref>Cour de {{lien web|url=http://www.liafa.jussieu.fr/~raffinot/ftp/cours-M1-Bioinfo-2010-2011.pdf|titre=Introduction à l’algorithmique du texte pour la bioinformatique|auteur=Mathieu Raffinot|date=2010}}.</ref>, à l'analyse de séquences musicales, aux flux de données, à la gestion de [[Base de données|bases de données]] textuelles, mais aussi trouvent aussi leur place dans le [[tatouage numérique]], la [[Détection du plagiat|détection de plagiats]], l'[[analyse d'image]], [[Apprentissage automatique|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 ==
{{article détaillé|Algorithme de recherche de sous-chaîne}}
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 <math>x</math> appelé ''motif'' et un mot <math>t</math> appelé ''texte'', on cherche une ou toutes les ''occurrences'' de <math>x</math> dans <math>t</math>. Par exemple, le motif <math>x=010</math> apparaît deux fois dans <math>t=001010</math>, à 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<ref name="AdT"/>, 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 <math>A^*x</math> des mots sur l'alphabet <math>A</math> qui se terminent par le motif <math>x</math>. Cet automate a <math>m+1</math> états (où <math>m</math> est la longueur du motif <math>m</math>), et possède au plus <math>2m</math> ''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<ref name="AdT">{{harvsp|Algorithmique du texte (2001) |id=AdT}}</ref>.

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}}
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é ==
{{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 à 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. 
* [[Similarité cosinus|mesure cosinus]] utilisée dans la [[fouille de textes]]
* [[TF-IDF]] utilisée dans la [[fouille de textes]]
Les [[distance (mathématiques)|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équence biologique|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''<ref>{{harvsp|Bannai ''et. al.'' (arXiv)|id=Bannai|p=}}.</ref>. Avec la même technique et en utilisant des calculs en machine, ce résultat a été affiné<ref>{{harvsp|Fischer ''et. al.''|id=Fischer|p=}}.</ref> Le nombre est asymptotiquement au plus  (22/23)n <0.957n.

== Notes et références ==
{{Références}}

== Bibliographie ==
;Ouvrages
* {{Ouvrage |id=AdT |langue=fr |auteur1=[[Maxime Crochemore]] |auteur2=Christophe Hancart |auteur3=Thierry Lecroq |titre=Algorithmique du texte |éditeur=Vuibert |année=2001 |pages totales=347 |isbn=978-2-7117-8628-2 |isbn10=2-7117-8628-5 |lire en ligne=http://igm.univ-mlv.fr/~mac/CHL/CHL-2011.pdf}}.  
* {{Ouvrage |langue=en |auteur1=Maxime Crochemore |auteur2=Christophe Hancart |auteur3=Thierry Lecroq |titre=Algorithms on strings |éditeur=Cambridge University Press |année=2007 |pages totales=383 |isbn=978-0-521-84899-2}} {{Commentaire biblio SRL|Traduction revue et corrigée du livre en français}}
* {{Ouvrage|langue=en|auteur1=[[Dan Gusfield]]|titre=Algorithms on strings, trees, and sequences|sous-titre=Computer science and computational biology|éditeur=Cambridge University Press|année=1997|pages totales=534|isbn=978-0-521-58519-4}}
* {{Ouvrage|id=Jewels|langue=en|auteur1=Maxime Crochemore|auteur2=Wojciech Rytter|titre=Jewels of stringology|éditeur=World Scientific Publishing|année=2002|pages totales=310|isbn=978-981-02-4782-9}}
;Articles cités
*{{chapitre | auteur1=Johannes Fischer |auteur2=  Štěpán Holub |auteur3=Tomohiro I|auteur4= Moshe Lewenstein
|titre chapitre = Beyond the Runs Theorem|doi= 10.1007/978-3-319-23826-5_27|titre=Beyond the Runs Theorem
|titre ouvrage = String Processing and Information Retrieval
|auteurs ouvrage = Costas Iliopoulos, Simon Puglisi et Emine Yilmaz (éditeurs)
|passage = 277-286
|sous-titre ouvrage = 22nd International Symposium|isbn= 978-3-319-23825-8
|année=2015|collection = Lecture Notes in Computer Science|numéro dans collection = 9309 |arxiv=1502.04644.pdf|id=Fischer}}
*{{Lien web|url= https://arxiv.org/pdf/1406.0263v7.pdf
|titre= The "Runs" theorem
|auteur= Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Kazuya Tsuruta |mois= juin
|année= 2015 |site= arXiv.org |id= Bannai
}}.

== Conférences ==
Des conférences régulières sur l'algorithmique du texte sont organisées, notamment :
* ''Combinatorial Pattern Matching'' (CPM). La {{26e}} des conférences annuelles a eu lieu en Italie du {{date-|29 juin}} au {{date-|1 juillet 2015}} : {{Ouvrage| langue=| auteur1=Ferdinando Cicalese| auteur2=Ely Porat| auteur3=Ugo Vaccaro| responsabilité3=éditeurs| titre=Combinatorial Pattern Matching| sous-titre=26th Annual Symposium, CPM 2015| lieu=Ischia, Italy| éditeur=Springer-Verlag| collection=Lecture Notes in Computer Science| numéro dans collection=9133| année=2015| pages totales=| isbn=978-3-319-19929-0| bnf=446800341| doi=10.1007/978-3-319-19929-0| sudoc=186399472}}
* [http://www.stringology.org/ ''The Prague Stringology Conference'']
* [https://www.cristal.univ-lille.fr/spire2021/ ''Symposium on String Processing and Information Retrieval'' (SPIRE)] ; la {{28e}} 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 ===

* [http://www-ia.lip6.fr/~herpsonc/docs/ArbresDeSuffixes_SuffixTreeConstruction_Herpson_0308.pdf 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}} [http://www-igm.univ-mlv.fr/~lecroq/string/index.html Algorithmes de recherche de chaine] – programmes.
* {{en}} [http://johannburkard.de/software/stringsearch/ 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.
{{Palette|Algorithmes de manipulation de texte|Informatique théorique}}{{Portail|informatique théorique|Linguistique}}

[[Catégorie:Algorithmique]]
[[Catégorie:Bio-informatique]]
[[Catégorie:Arbre (structure de données)]]
[[Catégorie:Algorithme sur les chaînes de caractères]]