Aho-Corasick-Algorithmus

Der Aho-Corasick-Algorithmus i​st ein String-Matching-Algorithmus, d​er von Alfred V. Aho u​nd 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:

  1. Zunächst erzeugt der Algorithmus auf Basis der gegebenen bzw. gewünschten Wörterbuchmenge eine 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.
  2. 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
Visualisierung eines mustererkennenden Automaten

Einfach gesagt b​aut der Algorithmus e​inen endlichen Zustandsautomaten a​uf und vergleicht diesen m​it dem Eingabetext. Falls d​ie Signatur bereits i​m Vorfeld bekannt i​st (zum Beispiel b​ei einer Anti-Viren-Datenbank), k​ann der Aufbau a​uch vor d​em Start d​es Programms off-line erfolgen u​nd zur späteren Benutzung abgespeichert werden.

Der Aho-Corasick-Algorithmus i​st die Basis d​es UNIX-Kommandos fgrep,[2] d​es Intrusion Detection Systems Snort[3] u​nd der Web Application Firewall ModSecurity.[4]

  • Java-Implementierung:
  • Python-Implementierung:
  • C++-Implementierung:
  • Web-Visualisierung:

Quellen
  1. Alfred V. Aho, Margaret J. Corasick: Efficient string matching: An aid to bibliographic search. In: Communications of the ACM. Band 18, Nr. 6, Juni 1975, S. 333–340, doi:10.1145/360825.360855 (englisch).
  2. grep: use Aho-Corasick algorithm to search multiple fixed words. In: grep: Git-Repository. 2. Juni 2016, abgerufen am 17. Dezember 2017 (englisch).
  3. Adir Gabai: Integrating Aho-Corasick based algorithm for Compressed Traffic (ACCH) Inside Snort. 2015 (englisch, deepness-lab.org [PDF]).
  4. Breach Security Inc.: ModSecurity Reference Manual
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.