Metraipolis › archive › dc_53357eacd201
Algorithme d'Aho-Corasick — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Algorithme_d%27Aho-Corasick
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-17T11:27:40.636Z
- SHA-256 of the archived text
0d9904b8adb7d1cbef4d34db2768fb8516dcf0c557184c284065b15e2d590473- Stable URL of this page
https://metraipolis.com/documento/dc_53357eacd201
How to cite
Algorithme d'Aho-Corasick — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_d%27Aho-Corasick (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_53357eacd201 (Metraipolis archive dc_53357eacd201, sha256 0d9904b8adb7d1cbef4d34db2768fb8516dcf0c557184c284065b15e2d590473)
BibTeX
@misc{dc53357eacd201,
title = {Algorithme d'Aho-Corasick — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Algorithme_d%27Aho-Corasick},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_53357eacd201; sha256 0d9904b8adb7d1cbef4d34db2768fb8516dcf0c557184c284065b15e2d590473},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_d%27Aho-Corasick. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
L'algorithme d'Aho-Corasick est un algorithme de recherche de chaîne de caractères (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 implémenté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'une trie ou arbre préfixe 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 pour un dictionnaire a, aa, aaa, aaaa et un texte aaaa. Le motif a apparaît à quatre reprises, le motif aa à trois reprises, etc. L'algorithme d'Aho-Corasick généralise l'algorithme de Knuth-Morris-Pratt (voir p. 367, Section 10.3 dans). Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico). Fonte: Wikipedia in francese, voce «Algorithme d'Aho-Corasick» — https://fr.wikipedia.org/wiki/Algorithme_d%27Aho-Corasick Wikidata Q402342 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q402342 Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Algorithme_d%27Aho-Corasick?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 233046013, consultata il 2026-10-17T11:07:33.314Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 02123497cff1dbdb2f7ccc4aade00661c254b9e3ecca8c7343c7ceaac7c5a405