Quelltext der Seite Aho-Corasick-Algorithmus

Der '''Aho-Corasick-Algorithmus''' ist ein [[String-Matching-Algorithmus]], der von [[Alfred V. Aho]] und [[Margaret J. Corasick]] [[1975]] entwickelt wurde.<ref>{{Literatur |Autor=Alfred V. Aho, Margaret J. Corasick |Titel=Efficient string matching: An aid to bibliographic search |Sammelwerk=Communications of the ACM |Band=18 |Nummer=6 |Datum=1975-06 |Seiten=333–340 |Sprache=en |DOI=10.1145/360825.360855}}</ref>

Der [[Algorithmus]] führt eine Art [[Wörterbuch]]-Vergleich durch, bei dem die Eingabe effizient nach vorher festgelegten Signaturen durchsucht wird. Dabei wird kein Zeichen der Eingabe mehr als einmal gelesen.
Das Verfahren ist dann besonders effizient, wenn sich die Signaturen überlappen, d.&nbsp;h. in [[Präfix]]- und [[Suffix]]-Beziehungen stehen (z. B. {„Igel“, „Geld“, „Eldorado“}).
Der Aho-Corasick-Algorithmus besteht aus zwei Phasen:

# Zunächst erzeugt der Algorithmus auf Basis der gegebenen bzw. gewünschten Wörterbuchmenge eine [[Trie|Trie-Struktur]], die auch als endlicher [[Zustandsautomat]] interpretiert werden kann. Jedem Zustand wird eine Ausgabemenge zugeordnet, die zunächst leer ist. Für jeden Zustand, bei dem ein Suchwort endet, wird dieses Suchwort seiner Ausgabemenge hinzugefügt.
# In der zweiten Phase werden die Knoten oder Zustände des Tries paarweise disjunkt nummeriert und eine Fehlerfunktion berechnet. Die Funktion ist für jeden Knoten definiert und legt fest, in welchem Zustand die Verarbeitung fortgesetzt wird, falls das gerade gelesene Zeichen der Eingabe keinen regulär gültigen Zustandsübergang bewirkt. Dadurch wird es möglich, schnell zwischen bereits erkannten Teilsignaturen zu wechseln und die Erkennung fortzusetzen, ohne den Automaten neu starten zu müssen.

== Beispiel ==
[[Datei:Ahocorasick.svg|mini|Visualisierung eines mustererkennenden Automaten]]

Einfach gesagt baut der Algorithmus einen endlichen [[Zustandsautomat]]en auf und vergleicht diesen mit dem Eingabetext. Falls die [[Virensignatur|Signatur]] bereits im Vorfeld bekannt ist (zum Beispiel bei einer Anti-Viren-Datenbank), kann der Aufbau auch vor dem Start des [[Computerprogramm|Programms]] ''off-line'' erfolgen und zur späteren Benutzung abgespeichert werden.

Der Aho-Corasick-Algorithmus ist die Basis des [[UNIX]]-Kommandos [[Grep#fgrep|fgrep]],<ref>{{Internetquelle |url=https://git.savannah.gnu.org/cgit/grep.git/commit/src?id=a3d42de483a29c1da381f5c3dad87cbbc86a5c70 |titel=grep: use Aho-Corasick algorithm to search multiple fixed words |werk=grep: Git-Repository |datum=2016-06-02 |sprache=en |abruf=2017-12-17}}</ref> des [[Intrusion Detection System]]s [[Snort]]<ref>{{Literatur |Autor=Adir Gabai |Titel=Integrating Aho-Corasick based algorithm for Compressed Traffic (ACCH) Inside Snort |Datum=2015 |Sprache=en |Online={{Webarchiv |url=http://www.deepness-lab.org/pubs/acch_snort_project_paper.pdf |text=deepness-lab.org |wayback=20170113003351}} |Format=PDF |KBytes=466}}</ref>, der [[Web Application Firewall]] [[ModSecurity]]<ref>Breach Security Inc.: [https://github.com/SpiderLabs/ModSecurity/wiki/Reference-Manual-%28v2.x%29 ModSecurity Reference Manual]</ref> und des Malware-Signatur Frameworks [[YARA]]<ref>{{Internetquelle |url=https://virustotal.github.io/yara-x/docs/intro/yara-x-vs-yara/ |titel=YARA-X vs YARA |datum=2023-09-07 |sprache=en |abruf=2024-07-23}}</ref>.

== Weblinks ==
* [[Java (Programmiersprache)|Java]]-Implementierung: [https://github.com/robert-bor/aho-corasick]
* [[Python (Programmiersprache)|Python]]-Implementierung: [https://github.com/vi3k6i5/flashtext]
* [[C++]]-Implementierung: [https://github.com/cjgdev/aho_corasick]
* [[World Wide Web|Web]]-Visualisierung: [https://wiomoc.de/aho-corasick-viz/]

== Quellen ==
<references />

[[Kategorie:Suchalgorithmus]]