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.
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
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
format rar !???
imposible a unrarer sous debian
Bizarre c’est bien du rar pourtant…
le fichier rar est endommagé!!!
Je viens de l’ouvrir :
http://twitpic.com/48rj8
Ouvert avec 7-zip sous Windows.
ah..ok merci.. la problème est avec winrar. maintenant c’est résolu..vive le freeware!!
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??
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
Le lien pour les sources est mort 🙁
Ouep lien mort 🙁
Le bon lien est : https://spawnrider.net/downloads/aho-corasick.rar
Je vais mettre à jour l'article.
Merci à vous !
Le bon lien est : https://spawnrider.net/downloads/aho-corasick.rar
Je vais mettre à jour l'article.
Merci à vous !
Bonjour,
comment fais tu compiler puis executer le programme?
Merci
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…
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?
On a fait ce projet à deux.
Plusieurs versions ont évoluées en même temps…
Ah oui, et je voulais savoir pourquoi le file a été implémenté comme un tableau et non une liste chainée?
C'était un pré-requis et non un choix technique…
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
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 !
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 !
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 !
Barre latérale coulissante
A propos de moi
Spawnrider.Net, le blog de Yohann Ciurlik, blogueur high-tech, architecte solutions, fan d'innovation, photographe enthousiaste mais surtout gadgetophile Par l’intermédiaire de ce blog, j’espère vous faire découvrir mes passions et mes trouvailles issues du Net.
Réseaux sociaux
Récemment
Des idées cadeaux Geek pour Noël
15 décembre 2017Utilisez le cardio-fréquencemètre de sa montre Garmin sur un compteur vélo iGPSPORT IGS50E
2 décembre 2017Activer le verrouillage dynamique sous Windows 10 avec un smartphone Bluetooth
22 novembre 2017Portainer, une interface pour gérer vos containers Docker
19 octobre 2017Suivez-moi sur Twitter
Mes Tweets