Algorithme d'Aho-Corasick

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.

L'algorithme extrait toutes les occurrences des motifs. Il est donc possible que le nombre d'occurrences soit quadratique, comme par exemple pour un dictionnaire a, aa, aaa, aaaa et un texte aaaa. Le motif a apparaît à quatre reprises, le motif aa à trois reprises, etc.

Sommaire

Description

De manière informelle, l'algorithme génère un trie avec des liens entre les nœuds. Chaque nœud représentant une chaîne (par exemple abc) a un lien vers le nœud qui correspond au plus long suffixe disponible (dans le cas d'abc, il s'agit de bc s'il existe, autrement c ou encore la racine). De plus l'arbre maintient des liens entre un nœud donné et le nœud représentant le suffixe le plus long qui apparaît dans le dictionnaire. Les correspondances peuvent ainsi être énumérées en parcourant la liste chaînée. L'algorithme utilise ensuite l'arbre pendant l'exécution, se déplaçant progressivement dans le texte en entrée et en conservant la correspondance la plus longue. L'utilisation de l'arbre garantit une complexité linéaire. Pour chaque nœud présent dans le dictionnaire et tout lien dans la liste chaînée des suffixes du dictionnaire, une sortie est générée.

Quand les mots recherchés sont connus à l'avance (par exemple pour une base de données des signatures de virus informatiques ou la recherche d'une séquence particulière dans un génome), alors la construction de l'automate peut être exécutée au préalable et le résultat stocké pour une utilisation ultérieure. Dans ce cas, la complexité est linéaire en fonction de la longueur de l'entrée plus le nombre de correspondances trouvées.

L'algorithme d'Aho-Corasick fut initialement utilisé dans l'utilitaire grep disponible sous Unix.

Exemple de trie généré dans l'application d'un algorithme d'Aho-Corasick

Voir aussi

Source

  • Alfred V. Aho et Margaret J. Corasick, juin 1975, Efficient string matching: An aid to bibliographic search, Communications of the ACM, vol. 18, issue 6, pages 333–340, DOI 10.1145/360825.360855.

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme d'Aho-Corasick de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Algorithme De Recherche De Sous-chaîne — Un algorithme de recherche de sous chaine est un type d algorithme de recherche qui a pour objectif de trouver une chaîne de caractères à l intérieur d une autre. Un tel algorithme fournit la position du premier caractère de la sous chaîne… …   Wikipédia en Français

  • Algorithme de recherche de sous-chaine — Algorithme de recherche de sous chaîne Un algorithme de recherche de sous chaine est un type d algorithme de recherche qui a pour objectif de trouver une chaîne de caractères à l intérieur d une autre. Un tel algorithme fournit la position du… …   Wikipédia en Français

  • Algorithme De Knuth-Morris-Pratt — L algorithme de Knuth Morris Pratt (souvent abrégé par algorithme KMP) est un algorithme de recherche de sous chaîne, permettant de trouver les occurrences d une chaîne P dans un texte S. Sa particularité réside en un pré traitement de la chaîne …   Wikipédia en Français

  • Algorithme KMP — Algorithme de Knuth Morris Pratt L algorithme de Knuth Morris Pratt (souvent abrégé par algorithme KMP) est un algorithme de recherche de sous chaîne, permettant de trouver les occurrences d une chaîne P dans un texte S. Sa particularité réside… …   Wikipédia en Français

  • Algorithme de Knuth-Pratt-Morris — Algorithme de Knuth Morris Pratt L algorithme de Knuth Morris Pratt (souvent abrégé par algorithme KMP) est un algorithme de recherche de sous chaîne, permettant de trouver les occurrences d une chaîne P dans un texte S. Sa particularité réside… …   Wikipédia en Français

  • Algorithme de knuth-morris-pratt — L algorithme de Knuth Morris Pratt (souvent abrégé par algorithme KMP) est un algorithme de recherche de sous chaîne, permettant de trouver les occurrences d une chaîne P dans un texte S. Sa particularité réside en un pré traitement de la chaîne …   Wikipédia en Français

  • Algorithme De Boyer-Moore — L algorithme de Boyer Moore est un algorithme de recherche de sous chaîne particulièrement efficace. Il a été développé par Bob Boyer et J. Strother Moore en 1977. Sommaire 1 Présentation 2 Fonctionnement de l algorithme 2.1 Pré traitement …   Wikipédia en Français

  • Algorithme de boyer-moore — L algorithme de Boyer Moore est un algorithme de recherche de sous chaîne particulièrement efficace. Il a été développé par Bob Boyer et J. Strother Moore en 1977. Sommaire 1 Présentation 2 Fonctionnement de l algorithme 2.1 Pré traitement …   Wikipédia en Français

  • Algorithme de recherche de chaîne de caractères de Boyer-Moore — Algorithme de Boyer Moore L algorithme de Boyer Moore est un algorithme de recherche de sous chaîne particulièrement efficace. Il a été développé par Bob Boyer et J. Strother Moore en 1977. Sommaire 1 Présentation 2 Fonctionnement de l algorithme …   Wikipédia en Français

  • Algorithme de recherche de sous-chaîne de Boyer-Moore — Algorithme de Boyer Moore L algorithme de Boyer Moore est un algorithme de recherche de sous chaîne particulièrement efficace. Il a été développé par Bob Boyer et J. Strother Moore en 1977. Sommaire 1 Présentation 2 Fonctionnement de l algorithme …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”