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 réponses à Recherche de mots dans un texte – Aho-Corasick

  1. nomrequis 17 septembre 2008 à 12:07 #

    format rar !???
    imposible a unrarer sous debian

  2. spawnrider 17 septembre 2008 à 12:26 #

    Bizarre c’est bien du rar pourtant…

  3. mte3bikri 30 avril 2009 à 1:54 #

    le fichier rar est endommagé!!!

  4. Yohann CIURLIK 30 avril 2009 à 1:58 #

    Je viens de l’ouvrir :
    http://twitpic.com/48rj8

    Ouvert avec 7-zip sous Windows.

  5. mte3bikri 30 avril 2009 à 2:21 #

    ah..ok merci.. la problème est avec winrar. maintenant c’est résolu..vive le freeware!!

  6. mte3bikri 3 mai 2009 à 18:07 #

    je suis sous windows, j’ai essayer de le faire fonctionner, mais ça ne marche pas ni sous code blocks ni dev c++, en fait toujours les mêmes erreurs: »undefined reference to WinMain@16″ et d’autres…seul le générateur qui a pu créer un fichier .exe (gen.exe), est ce que ce code ne marche que sous linux??

  7. Yohann CIURLIK 3 mai 2009 à 18:11 #

    Oui il faut un compilateur MniGW/GCC sous Windows sinon sous Unix/Linux aucun soucis.
    Utilise DevC++ avec MinGW pour compiler :
    http://www.bloodshed.net/dev/devcpp.html

  8. flashbulle 15 août 2009 à 18:47 #

    Le lien pour les sources est mort 🙁

  9. AlgoMan 27 novembre 2009 à 7:54 #

    Ouep lien mort 🙁

  10. spawnrider 27 novembre 2009 à 8:57 #

    Le bon lien est : http://spawnrider.net/downloads/aho-corasick.rar
    Je vais mettre à jour l'article.
    Merci à vous !

  11. spawnrider 27 novembre 2009 à 8:57 #

    Le bon lien est : http://spawnrider.net/downloads/aho-corasick.rar
    Je vais mettre à jour l'article.
    Merci à vous !

  12. 1101 3 janvier 2010 à 23:36 #

    Bonjour,
    comment fais tu compiler puis executer le programme?
    Merci

    • spawnrider 3 janvier 2010 à 23:48 #

      Tu te places dans un des répertoires et tu fais un gcc *.c
      Pour l'exécution, regarde l'utilisation des arguments dans le main, je ne me souviens plus trop mais il y à un fichier puis une liste de mots…

  13. 1101 4 janvier 2010 à 15:23 #

    Merci pour ta réponse rapide.
    ça a l'air de marcher. Par contre je me demande, pourquoi les fichiers file.c sont différents dans chaque dossier?

    • spawnrider 4 janvier 2010 à 16:35 #

      On a fait ce projet à deux.
      Plusieurs versions ont évoluées en même temps…

  14. 1101 4 janvier 2010 à 16:26 #

    Ah oui, et je voulais savoir pourquoi le file a été implémenté comme un tableau et non une liste chainée?

    • spawnrider 4 janvier 2010 à 16:35 #

      C'était un pré-requis et non un choix technique…

  15. 1101 5 janvier 2010 à 0:50 #

    Ah oui je comprends mieux. J'essaye de bien comprendre le code mais c'est pas évident, y a beaucoup de codes. Pourquoi y a t'il des fichiers matrices (matrice.c et matrice.h) dans le dossier liste par exemple? ça doit pas être simple de se replonger dans son code. en tout cas merci de ton aide

  16. Kha 23 mai 2012 à 10:02 #

    Bonjour,

    Merci pour ce super article ! J'ai un projet similaire à rendre et j'aimerais vous poser quelques questions en MP si possible.

    Merci d'avance !

  17. moi 5 décembre 2016 à 21:15 #

    salut;
    est ce que vous pouvez nous mettre un manuel sur l’execution de votre code
    ex : où on trouve le fichier genere
    en fait un manuel sur l’utilisation du code (execution et compilation
    merci d’avance !

  18. moi 5 décembre 2016 à 21:18 #

    salut;
    est ce que vous pouvez nous mettre un manuel sur l’execution de votre code
    ex : où on trouve le fichier genere
    car moi quand j’execte le code gen.c il s’arrete dans ici en affichant le deux messages
    if(argc<0) {
    printf("Generateur de motif dans le fichier fic.txt\n");
    printf("Usage : %s fic.txt taille(Mo) motif1 [motif2] [motif3] …\n",argv[0]);
    exit(1);
    }

    en fait un manuel sur l'utilisation du code (execution et compilation
    merci d'avance !

Laisser un commentaire

Time limit is exhausted. Please reload the CAPTCHA.