Aho-Corasick-Algorithmus - LinkFang.de





Aho-Corasick-Algorithmus


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

Für das Beispiel nehmen wir an, dass die Suchwörtermenge S gleich {he,her,hers,she,them,his,us} ist.

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 Intrusion Detection Systems Snort und der Web Application Firewall ModSecurity.[1]

Quellen

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

Kategorien: Suchalgorithmus

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Aho-Corasick-Algorithmus (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.