DE 
EnglishStandard
Українська
Polski🔍 Aho-Corasick — Mehrmuster-Textsuche
Bauen Sie einen Trie aus mehreren Mustern samt Fehlerlinks auf, durchsuchen Sie dann Text in einem einzigen O(n)-Durchlauf und beobachten Sie, wie der Automat Fehlerlinks folgt und alle Treffer auf einmal meldet.
Über Aho-Corasick
Der Aho-Corasick-Algorithmus, 1975 von Alfred V. Aho und Margaret J. Corasick bei den Bell Laboratories erfunden, löst das Mehrmuster-Textsuchproblem: Gegeben ein Wörterbuch von Mustern und ein Text, finde jedes Vorkommen jedes Musters in einem einzigen linearen Durchlauf. Er verallgemeinert den Knuth-Morris-Pratt-Algorithmus (KMP) von einem Muster auf viele, indem alle Muster zu einem gemeinsamen Trie zusammengeführt und Fehlerlinks per Breitensuche berechnet werden.
Häufig gestellte Fragen
Wie unterscheidet sich Aho-Corasick vom einfachen mehrfachen Ausführen von KMP?
Das separate Ausführen von KMP für k Muster über einen Text der Länge n kostet im schlimmsten Fall O(k·n), da jedes Muster einen eigenen Durchlauf benötigt. Aho-Corasick führt alle Muster zu einem Automaten zusammen und durchsucht den Text genau einmal, mit Kosten von O(n + m + z).
Was genau ist ein Fehlerlink, und warum wird er benötigt?
Ein Fehlerlink von Knoten v zeigt auf den Trie-Knoten, der das längste echte Suffix des Strings von v repräsentiert, das noch Präfix eines Musters ist. Wenn der Automat den aktuellen Treffer nicht mit dem nächsten Zeichen erweitern kann, folgt er Fehlerlinks statt von der Wurzel neu zu starten.
Kann Aho-Corasick überlappende Treffer finden?
Ja. Da jeder Trie-Knoten eine zusammengeführte Ausgabemenge speichert, die durch Verfolgen der Fehlerlinks bis zur Wurzel gesammelt wird, kann ein einzelner Zustand mehrere Muster melden, die Suffixe voneinander sind oder einfach an derselben Textposition enden.
Wo wird Aho-Corasick in der Praxis eingesetzt?
Über seine ursprüngliche Verwendung im Unix-Werkzeug fgrep hinaus treibt es Antivirus-Engines an, die Dateien mit großen Signaturdatenbanken abgleichen, Netzwerk-Einbruchserkennungssysteme, Spam- und Inhaltsfilter sowie Bioinformatik-Werkzeuge zur Suche nach kurzen Motiven in DNA-Sequenzen.