Implementation en C de l'algo de aho corasick
Résolu/Fermé
anawak
Messages postés
53
Date d'inscription
samedi 19 mars 2005
Statut
Membre
Dernière intervention
1 août 2010
-
7 déc. 2006 à 14:48
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 - 11 déc. 2006 à 20:48
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 - 11 déc. 2006 à 20:48
A voir également:
- Implementation en C de l'algo de aho corasick
- Telecharger algo pour pc - Télécharger - Édition & Programmation
- Implémentation cbase non disponible - Forum SQL Server
- Ccf algo bts sio ✓ - Forum Études / Formation High-Tech
- Algo poker - Forum Algorithmes / Méthodes
- Algo de Huffman en C - Forum C
4 réponses
mamiemando
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
7 déc. 2006 à 22:26
7 déc. 2006 à 22:26
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
Si tu as le choix peut être que ça se fait facilement en C++ avec la STL.
Bonne chance
anawak
Messages postés
53
Date d'inscription
samedi 19 mars 2005
Statut
Membre
Dernière intervention
1 août 2010
9
8 déc. 2006 à 11:48
8 déc. 2006 à 11:48
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
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
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
9 déc. 2006 à 11:23
9 déc. 2006 à 11:23
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
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
anawak
Messages postés
53
Date d'inscription
samedi 19 mars 2005
Statut
Membre
Dernière intervention
1 août 2010
9
11 déc. 2006 à 10:41
11 déc. 2006 à 10:41
<code><code>/*e,qo,p,r:indique les etats de l'automate
a:indique l'alphabet utilisé dans le mot à chercher
X:ens des mots à chercher
y:texte dans le quel effectué la recherche
N.B :le language C est imposé*/
/*fonctions independantes utilisées dans pre_aho_corasick*/
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
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.
/*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 principal*/
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</code></code>
mamiemando
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
11 déc. 2006 à 20:48
11 déc. 2006 à 20:48
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 :
- 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
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
