# 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 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.