Aho-Corasick-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 Suchwörtern mit einem Eingabetext vergleicht. Die Grundidee des Algorithmus' ist, in der Eingabe parallel nach allen Suchwörtern Ausschau zu halten und dabei kein Zeichen des Eingabetexts mehr als einmal zu lesen. Das Verfahren ist dann besonders effizient, wenn die Suchwörter überlappen, d.h. in Präfix- und Suffix-Beziehungen stehen. Der Aho-Corasick-Algorithmus besteht aus zwei Phasen:

  1. Zunächst baut der Algorithmus auf der Basis der gegebenen Suchwörtermenge eine Trie-Struktur auf, also einen deterministischen azyklischen und nicht-reentranten Zustandsautomaten. Jedem Zustand wird eine Ausgabemenge zugeordnet, die zunächst leer ist. Für jeden Zustand, bei denen ein Suchwort endet, wird dieses Suchwort seiner Ausgabemenge hinzugefügt. Der Startzustand des Tries wird mit einer Schleife versehen, die Zeichen, mit denen kein Suchwort beginnt, in den Startzustand zurückführt.
  2. In der zweiten Phase wird der Trie mit einer Breitensuche verarbeitet und eine sog. failure-Funktion berechnet. Diese Funktion legt fest, in welchem Zustand die Verarbeitung fortgesetzt wird, wenn der Algorithmus in dem aktuellen Zustand mit dem aktuellen Eingabesymbol scheitert, also keinen Übergang mit diesem Symbol in einen Folgezustand finden kann.

Beispiel[Bearbeiten]

Für das Beispiel nehmen wir an, dass die Suchwörtermenge S gleich {he,her,hers,she,them,his,us} ist. Der Trie samt Ausgabemengen sieht aus wie in Abb. 1.

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), 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, des IDS Snort und der WAF ModSecurity[1].

Quellen[Bearbeiten]

  1. Breach Security Inc.: ModSecurity Reference Manual (PDF; 524 kB)