Recherche de mots dans un texte – Aho-Corasick

L’algorithme Aho-corasick de recherche de mots dans un texte est l’algorithme utilisé dans des commandes UNIX telles que Grep. L’algorithme d’Aho-Corasick est un algorithme de recherche de chaîne de caractère (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. Généralement le dictionnaire est implanté à l’aide d’un trie ou arbre digital auquel on rajoute des liens suffixes. Une fois le dictionnaire implanté, l’algorithme a une complexité linéaire en la taille du texte T et des chaînes recherchées.

Lien vers wiki.

Vous trouverez les sources de mes trois versions d’aho-corasick et d’un générateur de texte aléatoire en langage C pour effectuer des tests.

Trois versions différentes:

  • Matrice de transitions
  • Liste d’adjacence
  • Matrice pour la racine et liste d’adjacence pour les noeuds de l’arbre

Aho-corasick.rar
Sources

N.B. 1: Les programmes sont pleins de petits bugs mais fonctionnels. Si vous avez des questions, n’hesitez pas à les poser sur mon forum.

N.B. 2: Vous remarquerez dans les sources que j’ai evité l’utilisation de la fonction realloc du C qui posée problèmes.J’ai donc utilisé des valeurs assez importantes dans les malloc pour éviter les réallocations mémoires. Je ne doute pas que cette façon de faire n’est pas la meilleur, cela dit, si vous le souhaitez, vous pouvez modifier les sources à votre convenance.

21 commentaires On Recherche de mots dans un texte – Aho-Corasick

Laisser un commentaire