Algorithmique du texte - L'automate de Aho-Corasik

Thèmes abordés

Algorithmique du texte, Aho-Corasik, algorithme, Python, codage, automate

Résumé du document

Le code fourni tp-aho.py donne une implémentation de la construction d'arbres lexicographiques (plus précisément de l'automate qui reconnaît le motif X).
Le but de ce TP est d'implémenter les fonctions additionnelles nécessaires pour l'automate d'Aho-Corasick.

Fichiers ressources disponibles auprès du service client

Extraits

[...] Donc il faut rajouter une boucle pour parcourir tous les caractères. Le reste du code est le même, mis à part que chaque fois qu'on rencontre un nouvel état on rajoute à son nombre d'occurrence ou on le créé égal à 1 si ce nombre n'existait pas. 11/12. buildFailure(self) Pour coder cette fonction, il y a deux parties. D'abord on construit la fonction de suppléance et ensuite on met à jour la fonction de sortie (stockée dans la liste output). [...]

[...] Algorithmique du texte - L'automate de Aho-Corasik 1. Préliminaires 1.1 Exemple du cours 1. Les identifiants associés à chaque mot du fichier sont : - ab : id = 0 - babb : id = 1 - bb : id = 2 Ces identifiants représentent l'indice du motif dans la liste X. On ne peut pas utiliser les mots comme identifiants car on n'a pas forcément unicité de ces mots, alors que c'est le cas pour les identifiants. Output = liste qui correspond à la fonction de sortie. [...]

[...] Première étape: on construit l'automate fini déterministe qui reconnaît X. La plupart du temps (c'est le cas dans cette exercice) l'automate "naturel" que l'on va construire sera directement déterministe, dans ce cas cette première étape est terminée. Sinon ne pas oublier de le déterminiser Deuxième étape: on construit l'automate fini non déterministe qui reconnaît SIGMA*X. On utilise l'étape précédente mais on rajoute une partie dans l'automate afin de reconnaître SIGMA* au début. Troisième étape: on déterminise l'automate précédent pour obtenir un automate fini déterministe qui reconnaît SIMGA*X. [...]

[...] Failure : P eps b a aa aab ab eps eps a ab b Output : P eps b a aa aab ab set() set() 2. Algorithme de Aho-Corasik 9. getTransition(p,c) On a tout d'abord codé pour la question 9 la fonction getTransition(p,c) qui nous retourne l'état obtenu à partir de l'état p par la lettre c. Pour se faire, il a juste fallu implémenter le bout de code à la page 19. Sauf qu'ici on a qu'un seul caractère c qui nous est fourni. [...]

[...] La deuxième partie du problème (Q12) ce que l'on veut faire est mettre à jour la liste output. Cependant, on ne peut pas mettre à jour les éléments dans n'importe quel ordre, il faut le faire dans un ordre de parcours en largeur (comme on l'a fait précédemment en fait) et pour cela (et je vous conseille de le retenir) on utilise une file pour stocker les éléments que l'on a parcouru. 13. On vérifie que le code fonctionne bien. 3. Un exemple plus conséquent 15. On utilise t.count(u). [...]