Loading AI tools
Aus Wikipedia, der freien Enzyklopädie
Der Aho-Corasick-Algorithmus ist ein String-Matching-Algorithmus, der von Alfred V. Aho und Margaret J. Corasick 1975 entwickelt wurde.[1]
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. h. in Präfix- und Suffix-Beziehungen stehen (z. B. {„Igel“, „Geld“, „Eldorado“}). Der Aho-Corasick-Algorithmus besteht aus zwei Phasen:
Einfach gesagt baut der Algorithmus einen endlichen Zustandsautomaten auf und vergleicht diesen mit dem Eingabetext. Falls die Signatur bereits im Vorfeld bekannt ist (zum Beispiel bei einer Anti-Viren-Datenbank), kann der Aufbau auch vor dem Start des Programms off-line erfolgen und zur späteren Benutzung abgespeichert werden.
Der Aho-Corasick-Algorithmus ist die Basis des UNIX-Kommandos fgrep,[2] des Intrusion Detection Systems Snort[3], der Web Application Firewall ModSecurity[4] und des Malware-Signatur Frameworks YARA[5].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.