Aho-Corasick-Algorithmus
aus Wikipedia, der freien Enzyklopädie
Der Aho-Corasick-Algorithmus ist ein Algorithmus, der auf der Suche von Zeichenfolgen beruht und von Alfred V. Aho und Margaret J. Corasick 1975 entwickelt wurde.
Der Algorithmus ist eine Art Wörterbuch-Vergleich, der eine endliche Anzahl aus bekannten Mustern mit einem Eingabetext vergleicht. Einfach gesagt, baut der Algorithmus einen endlichen Zustandsautomaten auf und vergleicht diesen mit dem Eingabetext. Falls die Signatur bereits im Vorfeld bekannt ist (z.B. bei einer Anti-Viren-Datenbank), dann 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 und des IDS Snort.
