Implementation en C de l'algo de aho corasick Résolu/Fermé

Question

bonjour à tous
j'ai un petit projet d'implementation de l'algo de Aho corasick sur la recherche d'un ensemble de mots dans un texte en languageC .Franchement ça me foux les boules car l'algo est trop abstrait ,il m'est difficile de l'implementer en C.
Si vous l'avez dejà fait ,svp file moi le code pour que je puis m'en inspirer.
merci d'avance

mamiemando · Answer

Tu peux peut être nous donner le pseudo code ?
Si tu as le choix peut être que ça se fait facilement en C++ avec la STL.

Bonne chance

anawak · Answer

Bonjour 
Comme suggeré par mamiemando,voici le pseudo code de l'algo :

X:ensemble des mots à chercher
k:nombre de mot à chercher
y:le texte dans le quel chercher ces mots
n:taille du texte

Algo Aho_corasick(X,k,y,n) 
  e<---pre_aho_corasick(x,k)   /*pretraitement*/
pour j=0 à n-1 faire
    tant que transition(e,y[j]) est non definie faire
          e<--suppliance(e);
   ftantque

   e<--transition(e,y[j]);
   si sortie(e) est non vide alors
       signaler une occupation
   fsi
fpour
falgo

/*la fonction de pretraitement*/
Algo pre_aho_corasick(X,k)
    créer l'etat qo
   pour i=0 à k-1 faire
      ENTRER(x[i],qo);
 fpour
 
 pour a appartenant à l'alphabet telque transition(qo,a) est non   
            definie faire
   transition(qo,a)<---qo;
 fpour

 completer(qo);

 Retour qo

fAlgo

Algo Entrée(x,qo)
     i<---o;
     tantque i<taille(x) et transition(e,x[i]) est definie faire
           e<--transition(e,x[i])
         i=i+1;
    ftantque
   
    tantque i<taille(x) faire
        créer un etat p;
       transition(e,x[i])<---p;
      e<---p;
   ftantque
   sortie(e)<----{x}
finAlgo

/*la fonction completer*/
Algo   completer(qo)
    f<--file vide
     l<---liste de toutes les transitions(qo,a,p) telleque p est       different de q
   
    Tantque L est non vide faire
           (r,a,p)<--premier(l);
          l<---suivant(l);
        enfiler(f,p);
      suppliance(p)<---qo;
    ftantque
      
    tantque f est non vide faire
         r<----defiler(f);
         l<---liste de toutes les transitions (r,a,p)
         tantque l est non vide faire
             (r,a,p)<----premier(l);
             l<---suivant(l);
            enfiler(f,p);

            tantque transition(s,a) est non definie faire
                 s<----suppliance(s);
           ftantque
    
           suppliance(p)<---transiton(s,a)
           sortie(p)<-----sortie(p) + sortie(suppliance(p))
       ftanrque
    ftantque
falgo.

Le travail consiste à l'implementer en language C en utilisant les  matrices ,liste d'adjacence ,et les deux à la fois.

merci d'avance

mamiemando · Answer

Est ce que tu peux indenter ton code, le mettre entre des balise code (cf le bouton code au dessus de la boite dans laquelle tu poste) et mettre les fonction dans l'ordre (les fonctions qui ne dépendent de rien au début, et les fonctions qui les utilisent ensuite).

Désolée de t'embêter mais j'ai un peu de mal à te relire.
Tu peux commencer à réfléchir au typage de chaque variable et paramètre.
Peux-tu me dire si c'est impérativement du C pur ou si tu peux faire du C++ ?

Bonne chance

mamiemando · Answer

Bon ecoute j'ai essayé de voir ce que ça donnait, et ça ne va pas.
Il y a plein de choses que tu n'as pas défini :
- la fonction suppliance
- la fonction transition
- la fonction signaler_occupation
- ...

Ensuite il faut définir les types de tex variables :
- par exemple x est une liste de mots, donc c'est par exemple un char **
- si e,qo, etc... sont des variables décrivant l'état de l'automate, tu dois créer une structure automate qui les encapsule. Exemple :

typedef struct automate{
    int e;
    int qo;
    int p;
    int r;
} automate_t;

- comment définis-tu un état ? que sont exactement qo,p,r ?


Dans un premier jet tu peux :
- implémenter une structure de liste chainée en C (qui servira à stocker les mots de X
- faire la partie saisie des données (lire le fichier d'entrée, les paramètres du programme principal etc...)
- clarifier les différents points que je t'ai soulevé.

Bonne chance

Implementation en C de l'algo de aho corasick

4 réponses

Discussions similaires