Romain Semler

L'algorithme d'Aho-Corasick est un algorithme de recherche de chaîne de caractères (ou motif) dans un texte dû à Alfred Aho et Margaret Corasick et publié en 1975. L'algorithme consiste à avancer dans une structure de données abstraite appelée dictionnaire qui contient le ou les mots recherchés en lisant les lettres du texte T une par une. La structure de données est implantée de manière efficace, ce qui garantit que chaque lettre du texte n'est lue qu'une seule fois.

Durant les cours sur les graphes, en licence 3 Informatique à la faculté, nous avons abordé les arbres. Nous avons donc vu dans quelles situations on peut les utiliser et comment ils fonctionnent de manière générale. La recherche de chaînes de caractères dans un texte faisait partie de ces différentes situations.

On nous a demandé, après une étude complète des arbres, de réaliser l'algorithme d'Aho-Corasick en implémentant un arbre et en réalisant différentes opérations pouvant faciliter la recherche (ajout des mots à chercher dans un champ, renvoi de la ligne où se trouve le mot dans le texte...). Le langage de programmation étant libre, mon coéquipier et moi avons choisi de le réaliser en Java.

Nous avons rendu notre travail accompagné d'une interface graphique (permettant de saisir les mots à chercher et le texte) mais aussi d'une documentation Java (que vous pouvez retrouver ici).