Westflische Wilhelms-Universitt Mnster

Ausarbeitung im Rahmen des Seminars Suchmaschinen und Suchalgorithmen

Textvergleich mit mehreren Mustern

Sandra Marcus

Themensteller: Prof. Dr. Herbert Kuchen Betreuer: Prof. Dr. Herbert Kuchen Institut fr Wirtschaftsinformatik Praktische Informatik in der Wirtschaft

Inhaltsverzeichnis1 2 Motivation.................................................................................................................. 3 Grundlagen des Textvergleichs ................................................................................. 4 2.1 2.2 2.2.1 2.2.2 3 3.1 3.1.1 3.1.2 3.2 3.2.1 3.2.2 3.2.3 3.3 3.3.1 3.3.2 4 Arten des Textvergleichs und Wissensgrundlagen ........................................... 4 Textvergleich mit Schlsselwrtern (Matching Keywords) ............................. 5 Naiver Ansatz ............................................................................................... 5 Knuth-Morris-Pratt Algorithmus .................................................................. 6 Textvergleich mit Keyword-trees ..................................................................... 7 Konstruktion von Keyword-trees.................................................................. 8 Verwendung von Keyword-trees zum Textvergleich................................... 9 Aho-Corasick-Algorithmus ............................................................................ 10 Pattern-Matching-Automat ......................................................................... 11 Konstruktion der Funktionen ...................................................................... 14 Anwendung des Aho-Corasick Algorithmus .............................................. 17 Erweiterte Anwendungen des Textvergleichs ................................................ 19 Textvergleich mit Wildcards ...................................................................... 19 Zweidimensionaler Textvergleich .............................................................. 21

Textvergleich mit mehreren Mustern ........................................................................ 7

Zusammenfassung ................................................................................................... 24

Literaturverzeichnis ........................................................................................................ 25

II

Kapitel 1: Motivation

1 MotivationDas Gebiet des Pattern-Matching besitzt in vielen wissenschaftlichen Bereichen eine hohe Relevanz. Aufgrund unterschiedlicher Einsatzgebiete sind auch Umsetzung und Anwendung des Pattern-Matching sehr verschieden. Die allen Anwendungen des Pattern-Matching inhrente Aufgabe besteht darin, in einer Vielzahl von Eingabedaten bestimmte Muster wieder zu erkennen. Dies ist auch der deutschen Bezeichnung Mustererkennung zu entnehmen. In der Medizin findet Pattern-Matching zum Beispiel bei der Untersuchung von Chromosomenstrngen auf bestimmte Folgen von Chromosomen Verwendung. Auf dem Gebiet der Bildverarbeitung knnen mit Hilfe des Pattern-Matching ganze Bilder verglichen oder einzelne Bildpunkte betrachtet werden, die durch ein Muster identifizierbar sind. Ein weiteres Einsatzgebiet des Pattern-Matching ist das Information-Retrieval, bei dem in gespeicherten Daten nach relevanten Informationen gesucht wird. Die Relevanz der zu suchenden Daten wird auch hier anhand eines Musters, zum Beispiel einem bestimmten Schlagwort, beurteilt. Ein vergleichbares Verfahren findet auch im Internet Anwendung. Internet-Benutzer, die mittels einer Suchmaschine nach bedeutsamen Informationen suchen, erhalten diese durch den Einsatz eines Pattern-Matching-Automaten. Die in diesem Zusammenhang an den Pattern-Matching-Automaten gestellten Anforderungen variieren mit der Suchanfrage, die an eine Suchmaschine gestellt wird. Eine solche Suchanfrage kann im einfachsten Fall aus genau einem Schlsselwort bestehen. Im komplexeren Fall enthlt die Anfrage mehrere Schlsselwrter. Dabei muss fr eine erfolgreiche Suche eine Konkatenation der in der Anfrage enthaltenen Wrter erfolgen. Zu Beginn dieser Arbeit wird in Kapitel 2 eine umfassende Einfhrung in die Thematik des Textvergleichs gegeben, wobei die Definition einiger grundlegender Begriffe vorgenommen wird. Anschlieend werden in Kapitel 3 Verfahren zum Textvergleich mit mehreren Mustern vorgestellt. Dabei wird zunchst ein einfaches Vorgehen erlutert, um einen Einsteig in das Thema des Textvergleichs mit mehreren Mustern zu erleichtern. Danach wird eine komplexe Methode des Textvergleichs vorgestellt und anhand von Beispielen verdeutlicht.

3

Kapitel 2: Grundlagen des Textvergleichs

2 Grundlagen des TextvergleichsZur Durchfhrung von Textvergleichen existieren unterschiedliche Methoden. Die Thematik dieses Kapitels befasst sich mit den Grundlagen des Textvergleichs unter Einsatz von festgelegten Mustern, welches hufig als String- oder Pattern-Matching bezeichnet wird.

2.1 Arten des Textvergleichs und WissensgrundlagenDem Gebiet des String-Matching knnen unterschiedliche Problemstellungen zugrunde gelegt werden. Ein Problemfeld ist das exakte String-Matching, bei dem ein Text-String bezglich des Auftretens eines Musters, im englischen Pattern, durchsucht wird. Dieses Muster besteht im einfachsten Fall aus nur einem Wort, dem so genannten Keyword. Ebenso knnen beim Textvergleich mehrere Keywords in einem Muster zusammengefasst werden, wobei der Text nach dem Vorkommen eines jeden Keywords dieses Musters durchsucht wird. Des Weiteren gibt es die Mglichkeit, in einem Text das Vorkommen von Pattern, die sich aus regulren Ausdrcken zusammensetzen, festzustellen. Das Matching regulrer Ausdrcke, ihre Konstruktion und ihre Verwendung [Aho75]. Im Folgenden wird vornehmlich der Textvergleich mit mehreren Mustern thematisiert. Zur Einfhrung in die Thematik des Textvergleichs werden zunchst naive Anstze des Matching erlutert, bevor das Vorgehen beim Textvergleich mit Keywords veranschaulicht wird. Um eine einheitliche Wissengrundlage zu schaffen, werden an dieser Stelle einige fr das weitere Vorgehen relevante Begriffe eingefhrt.

im

Bereich

des

Pattern-Matching

wird

hier

nicht

behandelt.

Weiterfhrende Informationen zum Matching regulrer Ausdrcke finden sich in

Ein Alphabet ist eine endliche Menge von Symbolen. bezeichnet die Kardinalitt von .

Ein String s ber einem Alphabet ist eine endliche Folge von Symbolen aus . |s| bezeichnet die Lnge von s.

bezeichnet den leeren String.

Wenn x und y Strings sind, dann bezeichnet xy die Konkatenation von x und y. 4

Kapitel 2: Grundlagen des Textvergleichs

s[i] bezeichnet das i-te Element eines Strings s.

Fr i gilt: 1 i s

s[ij] bezeichnet den String s[i]s[i+1]s[j] fr i > j gelte: s[ij] = wenn = xyz ein String ist, dann ist x ein Prfix und z ein Suffix von . Gilt x ( z ) , dann ist x (z) ein echtes Prfix (Suffix) von . Ein String x mit m = |x| heit Substring von y, wenn ein i existiert mit x = y[ii+m-1]. Bei einem Vergleich von zwei Symbolen spricht man von einem Match, wenn die Symbole identisch sind. Andernfalls handelt es sich um einen Mismatch [Gus97].

Die Datenstruktur des Strings wird sowohl in Mustern verwendet als auch in Texten, die auf das Vorkommen dieser Muster hin untersucht werden. bernimmt ein String die Funktion eines Musters, wird dieser mit P (Pattern) bezeichnet. Ein String, der als Text Verwendung findet, wird im Folgenden durch das Symbol T dargestellt.

2.2 Textvergleich mit Schlsselwrtern (Matching Keywords)2.2.1 Naiver AnsatzDer naive Ansatz des Textvergleichs berprft fr jede Position eines Textes T, ob das Muster P an eben dieser Position auftritt. Besteht das Muster aus mehr als nur einem Symbol, wird beginnend bei der aktuellen Position in Text T getestet, ob die Symbole des Musters in gleicher Abfolge auftreten. Die berprfung von T auf das Vorkommen dieses Musters, d. h. auf das Auftreten eines Matches, kann von rechts nach links oder auch von links nach rechts erfolgen. An dieser Stelle wird das naive Vorgehen beim Matching von links nach rechts erlutert, um den allgemeinen Ablauf des Textvergleichs aufzuzeigen. Gegeben ist ein Muster P, welches aus nur einem Keyword besteht, das sich aus mehreren Symbolen zusammensetzt, so dass P = p1p2pm gilt. Auerdem existiert ein Text T, der sich durch den String s = s1s2sn darstellen lsst. Hierbei bezeichnet pi das5

Kapitel 2: Grundlagen des Textvergleichs i-te Symbol in P und sj das j-te Symbol in s. Ist P in s als Substring enthalten, also s = xPy fr beliebiges x und y, existiert ein Match zwischen Text-String und Muster [Aho75]. Der Prozess der Suche nach einem Match zwischen Muster P und Text-String s luft wie folgt ab: Die Suche startet am linken Ende von Text-String und Pattern. Von dort ausgehend werden die Symbole in Text und Pattern sukzessive verglichen, bis das gesuchte Muster als Substring von T identifiziert ist oder bis ein Mismatch zweier Symbole aus T und P auftritt. Im Falle eines Mismatches wird das Muster im Verhltnis zum Text-String um ein Symbol nach rechts verschoben und der Test auf ein Match wird erneut durchgefhrt. Die Suche wird erfolglos beendet, sobald das rechte Ende des Musters ber das rechte Ende des Text-Strings hinausgeht. P ist dann definitiv kein Substring von T. Dieser Algorithmus bentigt im schlechtesten Fall eine Zeitkomplexitt von O (m n ) . Fr ein Pattern P = am-1 und einen Text-String T = an tritt P an den ersten n-m+1 Positionen von T auf. Der Algorithmus bentigt dann im schlechtesten Fall

(n m + 1) m = n m m 2 + m

Zeichenvergleiche bei der Suche nach P in T [Gus97].

Der naive Ansatz hat den Nachteil einer relativ hohen Zeitkomplexitt von O (m n ) im schlechtesten Fall. Diese Komplexitt resultiert aus der erneuten Durchsuchung des Text-Strings bei Vorliegen eines Mismatches nach Verschieben des Pattern-Strings. Das erneute Durchsuchen des gesamten Text-Strings ist erforderlich, weil der naive Algorithmus alle Symbole vergisst, die bereits zu einem Match gefhrt haben. Zur Reduzierung der Zeitkomplexitt ist es daher sinnvoll, den Aspekt der Gedchtnislosigkeit des Algorithmus bei nderungen zu beachten.

2.2.2 Knuth-Morris-Pratt AlgorithmusDer Algorithmus von Knuth, Morris und Pratt fhrt Textvergleiche in einer deutlich geringeren Zeit durch als der naive Algorithmus. Nach einem Mismatch wird hier nicht der gesamte Text-String erneut durchsucht, weil die bis zum Eintreten des Mismatches gewonnenen Informationen erhalten bleiben. Es werden somit in Abhngigkeit von der Lnge des Text-Strings nur n Vergleiche durchgefhrt. Ist zum Beispiel das Prfix p1p2pi-1 des Musters an den Positionen sj-i+1sj-i+2sj-1 des Text-Strings enthalten und 6

Kapitel 3: Textvergleich mit mehreren Mustern es kommt an Position sj zu einem Mismatch mit pi, so muss sj-i+1sj-i+2sj-1 nicht erneut durchsucht werden. Der Knuth-Morris-Pratt Algorithmus durchluft zwei Phasen, eine Vorlauf- und eine Suchphase. In der Vorlaufphase wird bei der Analyse des Musters in einer Tabelle h festgehalten, um wie viele Positionen das Muster bei Eintreten eine Mismatches nach rechts verschoben werden soll. Dieses Vorgehen bentigt eine Zeitkomplexitt von O (m ) [La05]. Im Anschluss an die Bestimmung der Schiebedistanzen wird in die Suchphase eingetreten, in der der Text-String bezglich des Musters durchsucht wird. Tritt ein Mismatch auf, wird das Pattern um die zuvor in Tabelle h gespeicherte Distanz im Verhltnis zum Text-String nach rechts verschoben. Dieses Vorgehen wiederholt sich, bis das Muster gefunden wird oder sein Vorkommen im Text-String ausgeschlossen werden kann. Die Suchphase des Knuth-Morris-Pratt Algorithmus bentigt insgesamt O (n ) Zeit, weil der gesamte Text-String mit Lnge n durchsucht wird. Die Vorlaufphase mit der Analyse des Musters und dem Erstellen der Tabelle kann unter Bercksichtigung der Lnge m des Musters in O (m ) Zeit durchgefhrt werden. Auerdem gilt m n, d.h., die Lnge des Musters ist kleiner oder gleich der Lnge des Text-Strings. Daraus ergibt sich fr den Knuth-Morris-Pratt Algorithmus eine Gesamtkomplexitt von O (m + n ) [La05]. Fr ausfhrliche Informationen zum Knuth-MorrisPratt Algorithmus empfiehlt sich [KMP77].

3 Textvergleich mit mehreren MusternDieses Kapitel thematisiert das Vorgehen beim Textvergleich mit Mustern, die aus mehr als einem Keyword bestehen. Ein Pattern P setzt sich von nun an in der Form P = {P1, P2,,Pm} aus mehreren Mustern zusammen. Als neue Datenstruktur wird der Keyword-tree eingefhrt und seine Verwendung beim Textvergleich erlutert. Des Weiteren wird mit dem Aho-Corasick Algorithmus eine Methode des Textvergleichs mit mehreren Mustern vorgestellt.

3.1 Textvergleich mit Keyword-treesDie in einem Muster enthaltenen Keywords werden mit Hilfe von Keyword-trees dargestellt. Anhand dieses Keyword-trees knnen Text-Strings auf das Vorkommen von Pattern durchsucht werden. 7

Kapitel 3: Textvergleich mit mehreren Mustern

3.1.1 Konstruktion von Keyword-treesDie Datenstruktur des Keyword-trees ist im Wesentlichen durch die folgenden drei Eigenschaften charakterisiert [Gus97, S. 52]: 1. Ein Keyword-tree K ist ein gerichteter Baum mit einer Wurzel r, dessen Kanten mit jeweils einem Zeichen aus einem Alphabet gekennzeichnet sind. 2. Kanten, die von einem Knoten des Baumes ausgehen, besitzen unterschiedliche Zeichen aus . 3. Ein Weg von der Wurzel bis zu einem Blatt des Baumes entspricht einem Muster Pi aus P.

Die Zeit fr das Aufstellen eines Keyword-trees ist abhngig von der Gesamtlnge aller Teil-Pattern von Muster P. Diese Gesamtlnge von P wird im Folgenden mit m bezeichnet, zuvor Bezeichnung fr die Lnge eines einzelnen Pattern. Die Lnge des Text-Strings wird weiterhin mit n gekennzeichnet. Der Keyword-tree kann somit aufgrund der Abhngigkeit von m in O(m) Zeit erstellt werden [Gus97, S.53]. Die Konstruktion eines Keyword-trees soll nun am Beispiel des Pattern P = {he, she,

his, hers} erlutert werden. Dabei bezeichnet Ki mit i = 14 den Keyword-tree nachEinfgen von Teil-Pattern i.

Schritt 1: Konstruktion von K1 durch Einfgen des Pattern P1 = he in den noch leerenBaum. Jede Kante des Pfades wird mit einem Zeichen des Pattern gekennzeichnet, so dass sich von der Wurzel bis zum Blattknoten gelesen das Pattern P1 ergibt. Die Ziffer 1 wird an das Ende des Pfades geschrieben, um das erste Pattern zu kennzeichnen.

Schritt 2: K2 wird durch Einfgen von P2 = she in K1 erzeugt. Dabei wird zunchst vomWurzelknoten ausgehend das lngste Prfix von P1 gesucht, das mit P2 bereinstimmt. Dieses Prfix ist im vorliegenden Fall nicht vorhanden. Somit wird eine Verzweigung des Baumes am Wurzelknoten erforderlich. Der Wurzelknoten erhlt einen zweiten Kindknoten, von dem aus der Pfad fr Pattern P2 zu Ende gefhrt wird. Ziffer 2 am Ende des Pfades markiert Teil-Pattern 2. Der Baum enthlt nun die Pfade 1 und 2 aus Abbildung 1.

Schritt 3: Einfgen von Teil-Pattern P3 = his in K2. Zunchst wird das lngste Prfix zuP3 = his gesucht, welches schon im Baum vorhanden ist Mit h, dem ersten Zeichen von 8

Kapitel 3: Textvergleich mit mehreren Mustern Pattern P1 = he, ist das lngste Prfix von P3 gefunden worden. Ausgehend vom PrfixEndknoten wird der Baum neu verzweigt. Der Pfad erhlt die Ziffer 3.

Schritt 4: Pattern P4 = hers soll in K3 eingefgt werden. Der bereits bestehende BaumK3 enthlt einen Match fr die ersten beiden Zeichen aus P4, d.h., es kann ein Prfix gefunden werden, welches zu P4 passt. Dieses Prfix ist das Pattern P1 = he. Das Einfgen von P4 erfordert somit eine Verzweigung des Endknotens von Pattern P1. Entlang dieses Pfades ergibt sich P4. K4 bezeichnet den vollstndigen Keyword-tree fr das oben genannte Muster P = {he, she, his, hers} [AC75].

Abbildung 1: Vollstndiger Keyword-tree

3.1.2 Verwendung von Keyword-trees zum TextvergleichNachdem in Kapitel 3.1.1 die Konstruktion von Keyword-trees erlutert wurde, soll nun die Anwendung beim Textvergleich aufgezeigt werden. Die Verwendung von Keyword-trees beim Textvergleich orientiert sich am zuvor in Abschnitt 2.2.1 beschriebenen naiven Ansatz. Angenommen ein Text-String T liege vor, welcher auf das Vorkommen von Pattern untersucht werden soll. Die Pattern sind im aktuell betrachteten Problemfeld des Textvergleichs mit mehreren Mustern Bestandteile eines Set of Pattern, welches die Form P = {P1,, Pm} besitzt. Das Set of Pattern wird in einem ersten Schritt vorverarbeitet und gem dem zuvor beschriebenen Vorgehen in einem Keyword-tree erfasst. Ist diese Vorverarbeitung abgeschlossen, kann mit dem Textvergleich begonnen werden. 9

Kapitel 3: Textvergleich mit mehreren Mustern Der Textvergleich beginnt an der ersten Position des Text-Strings, von der aus die Zeichen des Text-Strings mit den im Keyword-tree erfassten Pattern verglichen werden. Dazu wird entlang eines jeden Pfades untersucht, ob es zu einem Match zwischen den Zeichen des Textes T und den Zeichen des entlang dieses Pfades erfassten Pattern kommt. Gelingt ein Match zwischen Text-String und Pattern, so dass ein mit i gekennzeichneter Blattknoten erreicht wird, ist ein Vorkommen von Pattern Pi in T gefunden. Kommt es whrend des Vergleichs zweier Zeichen zu einem Mismatch, wird die vorherige Startposition um eine Stelle nach rechts verschoben und der Vergleich zwischen Text T und Keyword-tree wird erneut durchgefhrt. Wrde die Startposition nicht verschoben, knnten nur die Pattern in T entdeckt werden, die von Position 1 des Text-Strings ausgehen. Die Verschiebung ermglicht auch ein Auffinden solcher Muster in T, deren Startposition an einer beliebigen Stelle des Text-Strings liegt. Der Textvergleich unter Einsatz von Keyword-trees erfordert analog zum naiven Algorithmus eine relativ hohe Zeitkomplexitt. Die Suche entlang eines einzelnen Pfades im Keyword-tree bentigt eine Zeitkomplexitt von O (max( Pi ) ) , weil im schlechtesten Fall entlang des lngsten Pfades gesucht werden muss, bis ein Match auftritt oder ein Vorkommen von Pi in T ausgeschlossen werden kann. Die sukzessive Verschiebung der Startposition in T bentigt eine Komplexitt proportional zur Lnge des Text-Strings n, also O (n ) . Der Textvergleich mit Keyword-trees erfordert somit insgesamt eine Zeit von O (m n ) [Gus97].

3.2 Aho-Corasick-AlgorithmusDer Textvergleich mit mehreren Mustern bentigt eine hohe Zeitkomplexitt, wenn er mit Hilfe von Keyword-trees durchgefhrt wird. Die einfachste Form eines Textvergleichs mit mehreren Mustern ist die wiederholte Anwendung eines Algorithmus, der fr den Textvergleich mit nur einem Keyword konzipiert wurde. Fr diese Anwendung wrde sich der in Abschnitt 2.2.2 beschriebene Knuth-Morris-Pratt Algorithmus eignen, der den Textvergleich mit einem Keyword in einer vergleichsweise geringen Zeitkomplexitt von O (m + n ) durchfhrt. Der Knuth-Morris-Pratt

Algorithmus msste im aktuellen Zusammenhang einmal auf jedes Pattern Pi des Set of 10

Kapitel 3: Textvergleich mit mehreren Mustern

Pattern P angewendet werden. Dadurch wrde sich eine Zeitkomplexitt vonO (m + k n ) ergeben [Aho75]. Im Folgenden wird ein Algorithmus beschrieben, der speziell fr den Textvergleich mit mehreren Mustern entwickelt wurde und der die fr den Textvergleich bentigte Zeitkomplexitt reduziert. Der Aho-Corasick-Algorithmus ist im Gegensatz zum Knuth-Morris-Pratt Algorithmus auf mehrere Muster anwendbar und verwendet zum Textvergleich einen PatternMatching-Automaten. Dieser Automat wird aus dem Set of Pattern gebildet und ist nach seiner Erstellung in der Lage, einen Text simultan nach allen Keywords zu durchsuchen [Aho75, S 273]. Die folgenden Abschnitte erlutern die Erstellung eines PatternMatching-Automaten und die Konstruktion der vom Aho-Corasick-Algorithmus verwendeten Funktionen.

3.2.1 Pattern-Matching-AutomatEin Pattern-Matching-Automat wird auf Basis eines vorgegebenen Set of Pattern erstellt. Bei der Suche nach dem Vorkommen der Pattern in einem Text-String T wird dieser Text-String als Input fr den Automaten verwendet. Als Output des Automaten ergeben sich die Positionen, an denen Matches zwischen Pattern und Text-String gefunden wurden [AC75, S. 1]. Der Pattern-Matching-Automat besteht aus verschiedenen fr seine Konstruktion und Funktion relevanten Komponenten. Die Konstruktion des Automaten und das Vorgehen bei der Suche nach vorgegebenen Mustern in einem Text-String hneln der Strategie bei der Verwendung von Keyword-trees. Der Keyword-tree bildet nur eine Grundlage fr die aktuelle Problemstellung, weshalb einige Vernderungen vorgenommen wurden, damit er im vorliegenden Fall anwendbar ist. Ein Pattern-Matching-Automat besteht aus verschiedenen Zustnden und kann deshalb als Zustandsautomat verstanden werden. Ein Aho-Corasick Pattern-Matching-Automat lsst sich durch das 6-Tupel = (Q, , g , f , output , q0 ) formal beschreiben. Das 6-Tupel enthlt folgende Komponenten:

Eine endliche Menge Q von Zustnden. Ein endliches Eingabe-Alphabet . Eine Goto-Funktion g:Qx Q { fail} , die jedem Paar (Zustand,

Eingabezeichen) einen Folgezustand oder fail zuordnet. 11

Kapitel 3: Textvergleich mit mehreren Mustern

Eine Fehler-Funktion f: Q Q { fail} , die jedem Zustand einen Folgezustand oder fail zuordnet.

Eine Output-Funktion output: Q (*) , die einem Zustand eine Ausgabe zuordnet.

Einen Startzustand q 0 Q .

Jeder Zustand des Automaten wird zur eindeutigen Identifizierung mit einer Ziffer versehen. Der Automat hat drei Funktionen: die Goto-Funktion, die Fehler-Funktion und die Output- Funktion. Er liest als Input den Text-String T ein und durchsucht diesen unter Anwendung der genannten Funktionen auf das bei der Konstruktion des Automaten zugrunde gelegte Muster. Ein Aho-Corasick Pattern-Matching-Automat kann mittels folgender Methode, hier in Pseudocode dargestellt, implementiert werden [AC75]:{s 0 for i 1 until n do { while g(s, ai) = fail do s f(s), s g(s, ai) if output(s) empty then { print i, print output(s)}}}

Als Input bentigt diese Methode einen Text-String und die drei wesentlichen Funktionen des Automaten, die im weiteren Verlauf beschrieben werden. Als Output werden alle Positionen ausgegeben, an denen Pattern gefunden werden konnten. Bevor im nachfolgenden Abschnitt auf die einzelnen Funktionen als Bestandteile des Aho-Corasick Pattern-Matching-Automaten eingegangen wird, soll im folgenden Beispiel die Funktionsweise des Automaten erlutert werden. Smtliche Verfahrensschritte des Aho-Corasick Algorithmus basieren hier auf dem Muster P = {he, she, his, hers}. Aus den Keywords dieses Musters lsst sich ein Keyword-tree konstruieren. Damit dieser den Eigenschaften des Automaten gengt, ist jeder Knoten des Trees mit einer Zustandsnummer zu versehen, die den aktuell erreichten Zustand im Tree und den damit verbundenen Output des Zustands angibt. Abbildung 2 zeigt den erweiterten Keyword-tree des Pattern-Matching-Automaten.

12

Kapitel 3: Textvergleich mit mehreren Mustern Diesem sind die erreichbaren Zustnde sowie die Zustandsbergnge mit ihren Anfangs- und Endzustnden zu entnehmen.

Abbildung 2: Goto-Graph [AC75]

Zustand 0 wird als Startzustand deklariert. Ein Zustand, der auf ein Keyword des Musters verweist, stellt einen als Match zu akzeptierenden Zustand dar. Im vorliegenden Fall sind dies die Zustnde 2, 5, 7 und 9. Dem Zustandsgraphen ist die Goto-Funktion des Automaten, die mit g bezeichnet wird, zu entnehmen. Die GotoFunktion gibt an, wie von einem beliebigen Zustand aus unter Verwendung eines Symbols des Text-Strings T ein anderer Zustand erreicht werden kann. Von Zustand 0 aus fhrt zum Beispiel g(0, h) zu Zustand 1. Von diesem Zustand aus kann ein Zustandsbergang nur unter Ausfhrung einer der Funktionen g(1, e) oder g(1, i) erfolgen. Der Vergleich von Baum und Text-String fhrt bei erfolgreicher Ausfhrung einer der Funktionen zu einem Match. Der erreichte Folgezustand unter Ausfhrung der Funktion g(1, e) ist Zustand 2. Die Funktion g(1, i) besitzt den Folgezustand 6. Tritt ein Mismatch auf, gelingt kein bergang in einen Folgezustand. An dieser Stelle liefert die Goto-Funktion das Ergebnis fail. In diesem Fall wird die Fehler-Funktion verwendet. Diese Funktion gibt an, bei welchem Zustand des Goto-Graphen der Vergleich 13

Kapitel 3: Textvergleich mit mehreren Mustern zwischen Text-String und Pattern fortgesetzt werden soll, wenn zuvor ein Mismatch aufgetreten ist. Die dritte Funktion des Automaten, die Output-Funktion, gibt zu jedem Zustand die in ihm erreichten Keywords des Pattern an [AC75]. Im vorliegenden Fall besitzt der Goto-Graph in Zustand 7 den Output {his}. Dieser wird nur dann ausgegeben, wenn die Symbole entlang des Pfades, der zu Zustand 7 fhrt, in gleicher Reihenfolge im Text-String aufgefunden wurden und folglich Zustand 7 als Endzustand erreicht werden konnte. Der beschriebene Automat durchluft fr jedes Symbol des Text-Strings den folgenden Zyklus: Im bestehenden Zustand wird eine Goto-Transition durchgefhrt, wenn es zu einem Match zwischen dem Symbol des Text-Strings und dem zum Folgezustand fhrenden Symbol des Graphen kommt. Andernfalls kommt es zu Fail und eine Fehler-Transition muss angewandt werden. Dieses Vorgehen wird in Abschnitt 3.2.2 ausfhrlich erlutert.

3.2.2 Konstruktion der FunktionenDie Konstruktion der Funktionen erfolgt in zwei Schritten. Zunchst werden die Zustnde und die Goto-Funktion des Aho-Corasick-Algorithmus festgelegt, bevor in einem zweiten Schritt mit der Bestimmung der Fehler-Funktion eines jeden Zustands begonnen werden kann. Die Goto-Funktion wird mit Hilfe eines erweiterten Keywordtrees erstellt, der als Goto-Graph bezeichnet wird. Der Goto-Graph ist ein gerichteter Graph und besteht aus Zustandsknoten und mit Symbolen der Keywords bezeichneten Kanten. Wie in Abschnitt 3.1.1 bereits anhand von Keyword-trees erlutert wurde, werden im Goto-Graphen alle Keywords eines Musters erfasst, hier P = {he, she, his,

hers}. Neue Keywords werden in den Graphen eingefgt, so dass sich fr jedesKeyword vom Startzustand ausgehend ein Pfad im Graphen ergibt. Fr die Teil-Pattern P1 und P2 des betrachteten Musters P = {he, she, his, hers} ergbe sich anhand des oben beschriebenen Vorgehens der folgende Goto-Graph:

Abbildung 3: Goto-Graph fr Pattern 1 und 2 [AC75]

14

Kapitel 3: Textvergleich mit mehreren Mustern Dem Graphen kann entnommen werden, dass das Keyword he in Zustand 2 des Graphen endet. Daher wird he als Output fr Zustand 2 verstanden. Fr Zustand 5 ergibt sich auf die gleiche Weise der Output she. Ebenso wird mit den anderen Teil-Pattern des Musters verfahren. Nach vollstndiger Konstruktion unter Bercksichtigung aller Teil-Pattern von P ergibt sich der Graph, der bereits in Abbildung 2 dargestellt wurde. Die Output-Funktion dieses Goto-Graphen lautet: i output(i) 2 {he} 5 {she, he} 7 {his} 9 {hers} sonst {}

Tabelle 1: Output-Funktion [AC75]

Der Goto-Graph in Abbildung 2 enthlt zur Darstellung einer vollstndigen GotoFunktion eine Kante, die von Zustand 0 zu Zustand 0 fhrt. Diese ist fr alle InputSymbole auer fr die direkt auf den Startzustand folgenden Symbole h und s von Bedeutung. Die Goto-Funktion kann mittels folgender Methode implementiert werden [AC75]:

{newstate 0; for i 1 until k do enter (yi) for all a such that g(0, a) = fail do g(0, a) 0 } procedure enter (a1, a2, , am):{ s 0; j 1 while g(s, aj) fail do { s g(s, aj); j j + 1} for p j until m do { newstate newstate + 1 g(s, ap) newstate; s newstate} output(s) {a1, a2, , am}}

Bei der Erstellung der Fehler-Funktion f(s) wird auf die Goto-Funktion zurckgegriffen, wobei s einen beliebigen Zustand bezeichnet. Die Tiefe d eines Zustands in einem Baum lsst sich fr jeden Zustand innerhalb eines Goto-Graphen als Entfernung dieses Zustands zum Startzustand bestimmen. Der Startzustand besitzt somit die Tiefe 0 und die Zustnde 1 und 3 besitzen die Tiefe 1. Die Fehler-Funktion wird nacheinander fr die verschiedenen Tiefen des Graphen bestimmt. Somit kann die Fehler-Funktion der Tiefe 3 auf die bereits festgelegte Fehler-Funktion von Zustnden der Tiefen 1 und 2

15

Kapitel 3: Textvergleich mit mehreren Mustern zurckgreifen. Die Implementierung der Fehler-Funktion kann mit Hilfe folgender Methode erfolgen [AC75]:{queue empty for each a such that g(0, a) = s 0 do { queue queue {s}; f(s) 0} while queue empty do { let r be the next state in queue queue queue {r} for each a such that g(r, a) = s fail do { queue queue {s}; s f(r) while g(s, a) = fail do s f(s); f(s) g(s, a) output(s) output(s) output(f(s))}}}

Der Fehler-Funktion der Zustnde auf Tiefe 1 des Graphen wird der Wert 0 zugewiesen, d.h., f(s) = 0. Die Bestimmung der brigen Fehler-Funktionen in Abhngigkeit von den Funktionen der Tiefe 1 wird zunchst am Beispiel-Graphen aus Abbildung 2 erlutert. Die Fehler-Funktion der Zustnde 1 und 3 lautet im vorliegenden Fall f(1) = f(3) = 0. Zustnde der Tiefe 2 des Graphen sind 2, 6 und 4. Zur Bestimmung der Fehler-Funktion f(2) fr Zustand 2 wird auf f(1) = 0 zurckgegriffen, da Zustand 2 auf Zustand 1 folgt. Von Zustand 2 aus fhrt ein Pfad zu Zustand 3 ber das Symbol e. Tritt beim Vergleich der Symbole aus Keyword und Text-String an dieser Stelle ein Mismatch auf, wird untersucht, ob ein Pfad mit eben diesem Symbol vom Startzustand ausgehend existiert. Hier ergibt sich unter Ausnutzung der zustzlichen Kante von Zustand 0 zu Zustand 0 die Goto-Funktion g(0, e) = 0. Auch die Fehler-Funktion von Zustand 1 verweist auf Zustand 0. Im Fall eines Mismatches bei Zustand 2 ergibt sich daraus die Fehler-Funktion f(2) = 0, d.h., es wird zu Zustand 0 zurckgesprungen. Dieses Vorgehen ist dadurch zu begrnden, dass sich ausgehend von Zustand 0 kein Prfix finden lsst, das das Suffix des Keywords beinhaltet, welches bis Zustand 2 gefunden wurde. Als Fehler-Funktion fr Zustand 4 ergibt sich f(4) = 1. Dabei ist f(3) = 0 bekannt. Tritt ein Mismatch bei Zustand 4 auf, wird zu Zustand 0 zurckgesprungen und die Goto-Funktion g(0, h) = 1 kann ausgefhrt werden. Im Falle eines Mismatches kann somit von Zustand 4 direkt zu Zustand 1 gesprungen werden, weil h das Symbol ist, welches zu Zustand 4 gefhrt hat. Allgemein mssen zur Bestimmung der FehlerFunktion zwei Schritte durchgefhrt werden:

16

Kapitel 3: Textvergleich mit mehreren Mustern 1. Bei einem Mismatch auf Tiefe d fr ein beliebiges Symbol wird, ausgehend von Zustand 0, das lngste Suffix gesucht, welches gleichzeitig das Prfix jenes Pattern darstellt, bei dem der Mismatch aufgetreten ist. Kann ausgehend von Zustand 0 dieses lngste Suffix nicht gefunden werden, so gibt es keine weiteren Schritte. Die Fehler-Funktion besitzt den Wert 0. 2. Kann im Falle eines Mismatches fr ein beliebiges Symbol eine Goto-Funktion in Zustand 0 des Graphen ausgefhrt werden, wird der Graph ausgehend vom Folgezustand weiter durchsucht, solange g(s, Symbol) fail gilt. S bezeichnet hierbei den jeweils aktuellen Zustand. Die Fehler-Funktion des Zustandes, bei dem der Mismatch ursprnglich aufgetreten ist, erhlt als Wert den Zustand, bei dem unter Ausfhrung der Funktion g(s, Symbol) fail das lngste Suffix gefunden wurde, d.h., f(s) = g(s, Symbol). Der Graph wird daher nach dem lngsten Suffix des aktuellen Keywords durchsucht, das auf ein Prfix eines anderen im Graphen erfassten Keyword passt [AC75]. Fr den Beispiel-Graphen ergeben sich diese Werte fr die Fehler-Funktion: i f(i) 1 0 2 0 3 0 4 1 5 2 6 0 7 3 8 0 9 3

Tabelle 2: Fehler-Funktion [AC75]

3.2.3 Anwendung des Aho-Corasick AlgorithmusDie Anwendung des Aho-Corasick-Algorithmus unter Einsatz der in Abschnitt 3.2.2 bestimmten Funktionen zur Untersuchung eines Text-Strings soll anhand eines Beispiels demonstriert werden. Der hierzu verwendete Goto-Graph ist weiterhin Abbildung 2 zu entnehmen. Als Input-String wird die Symbolfolge ushers gewhlt. Der Algorithmus startet in Zustand 0 und versucht g(0, u) auszufhren. Da dieser Schritt nicht mglich ist, wird nach Durchqueren der Kante von Zustand 0 zu Zustand 0 in eben diesem verweilt. Als nchstes wird die Goto-Funktion g(0, s) erfolgreich ausgefhrt. Der aktuelle Zustand ist Zustand 3, weil von Zustand 0 eine mit dem Symbol s gekennzeichnete Kante zu Zustand 3 fhrt. Die Funktion g(3, h) lsst sich aufgrund der Existenz einer mit h gekennzeichneten Kante von Zustand 3 nach Zustand 4 erfolgreich durchfhren; aktueller Zustand wird Zustand 4. Von Zustand 4 aus fhrt eine Kante des Graphen ber das Symbol e zu Zustand 5. Die Goto-Funktion g(4, e) kann erfolgreich ausgefhrt werden. In der Output-Funktion, die Tabelle 1 zu entnehmen ist, existiert ein Eintrag fr Zustand 5. Der fr Zustand 5 vom Algorithmus ausgegebene output(5) 17

Kapitel 3: Textvergleich mit mehreren Mustern bedeutet, dass die Keywords she und he im Text-String gefunden wurden. Bei dem Versuch, einen Folgezustand von Zustand 5 zu erreichen, scheitert der Algorithmus. Die Funktion g(5, r) ergibt fail. Dies fhrt zu einem Aufruf der Fehler-Funktion f(5), die den Wert 2 besitzt. he bildet das lngste Suffix von she, welches mit den Symbolen h und e bereinstimmt, die zu Zustand 2 fhren. Folglich setzt der Algorithmus in Zustand 2 des Graphen die Suche nach dem Vorkommen von Keywords im Text-String fort. Die Funktion g(2, r) ergibt 8, somit wird zu Zustand 8 bergegangen [AC75]. Nachdem auch Zustand 9 unter Durchfhrung der Goto-Funktion g(8, s) erreicht werden konnte, wird output(9) = {hers} ausgegeben. Danach bricht der Algorithmus ab, weil er am Ende des Text-Strings angelangt ist. Bei diesem Textvergleich werden somit output(5) = {she, he} und output(9) = {hers} ausgegeben. Weitere Keywords konnten nicht gefunden werden [Ki04].

Abbildung 4: Ablauf beim Match des Input-Strings ushers [Ki04]

Der Aho-Corasick Algorithmus bentigt zur Durchfhrung eines Textvergleichs mit mehreren Mustern eine lineare Zeitkomplexitt. Diese ergibt sich wie folgt: Der GotoGraph kann wie ein Keyword-tree in Abhngigkeit von der Gesamtlnge m des Musters in O (m ) Zeit erstellt werden. Whrend der Suchphase wird die Goto-Funktion unter Bercksichtigung von der Lnge n des Text-String hchstens n-mal ausgefhrt [Gus97]. Zustzlich wird whrend der Suchphase k-mal die Output-Funktion verwendet. Das Symbol k gibt hierbei an, wie hufig Pattern aus P in T gefunden wurden. Daraus ergibt sich fr die Vorlaufphase eine Komplexitt von O (m ) und fr die Suchphase eine

18

Kapitel 3: Textvergleich mit mehreren Mustern Komplexitt von O (n + k ) , was zu einer Gesamtkomplexitt von O (m + n + k ) fhrt [Gus97, S. 61].

3.3 Erweiterte Anwendungen des TextvergleichsDas Verfahren des Textvergleichs mit mehreren Mustern kann erweitert werden, um auch auf vernderte Problemstellungen anwendbar zu sein. Zwei weitere Anwendungsmglichkeiten werden im Folgenden erlutert.

3.3.1 Textvergleich mit WildcardsEin Zeichen , das angewandt auf ein einzelnes beliebiges Zeichen eines Alphabets

einen Match ergibt, wird als Wildcard bezeichnet. Beim Matching mit Wildcardswird zunchst vereinfachend angenommen, dass der Text-String keine Wildcards enthlt. Das Muster hingegen hat die Form: P = ...P1 ....P2 ...Pk ... . Die Pi stellen Teil-Muster von P dar, die nicht durch Wildcards unterbrochen werden. Um einen Text auf Pattern untersuchen zu knnen, die Wildcards enthalten, mssen einige Definitionen vorgenommen werden:

Die Menge P* = {P1, P2, , Pk} bezeichnet die Menge aller Substrings von P, die keine Wildcards enthalten.

Der Vektor l = (l1, l2, , lk) enthlt die Positionen in P, an denen die in P* verzeichneten Substrings aus P beginnen. Ist z.B. P = abc , dann enthlt die Menge P* der Substrings von P die Elemente P1 = ab und P2 = c. Der Vektor l beinhaltet in diesem Fall die Elemente l1 = 1 und l2 = 5 [Gus97].

Ein Vektor C, der die gleiche Lnge besitzt wie der Text-String T, wird mit einer Folge von Nullen initialisiert [Gus97, S. 62].

Unter Einsatz der definierten Vektoren wird die Untersuchung des Text-Strings auf Matches mit P* durchgefhrt. Tritt beginnend bei Position j des Text-Strings ein Pattern Pi auf, wird an Position j l i + 1 in Vektor C durch Inkrementierung dieser Position um 1 ein mgliches Vorkommen des vollstndigen Musters P assoziiert. Nach 19

Kapitel 3: Textvergleich mit mehreren Mustern Durchsuchung des gesamten Text-Strings kann anhand des Vektors C ein Vorkommen des Pattern P in T erkannt werden. Ist P in T enthalten, muss eine der Positionen in C kmal, also so hufig wie Substrings in P* vorhanden sind, inkrementiert worden sein. Jeder in T gefundene Substring hat somit auf die gleiche mgliche Anfangsposition des Pattern P in T verwiesen. Kann in C eine Position gefunden werden, deren Wert k ist, so ist beginnend bei dieser Position ein Vorkommen von P in T bewiesen [Gus97]. Das Vorgehen bei der Untersuchung eines Text-Strings auf Matches mit einem Pattern, welches Wildcards enthlt, wird an einem Beispiel verdeutlicht. Das verwendete Pattern lautet P = abc . Der zu untersuchende Text-String wird gewhlt als:

a a a a a b b a c b a b b b c a b b a a a c a a Die Pfeile kennzeichnen Startpositionen der Teil-Pattern im Text-String, welche whrend des Textvergleichs gefunden werden. Der Vektor C ist zu Beginn mit Nullen initialisiert:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Beim Durchsuchen des Text-Strings wird an Position j = 1 gestartet, die durch das Symbol a besetzt ist. Das Symbol a liefert einen Match mit dem Pattern P, jedoch kann kein vollstndiges Teil-Pattern Pi identifiziert werden. Deshalb wird der Vergleich des Text-String mit dem Pattern an der nchsten Position j = 2 vorgesetzt. Dieser Ablauf wiederholt sich, bis beginnend an Position j = 5 das Teil-Pattern P1 = {ab} gefunden wird. In Folge dieses Auffindens muss ein Eintrag in C inkrementiert werden, um eine mgliche Startposition des vollstndigen Pattern, bestehend aus P1, P2 und P3, fr das weitere Vorgehen zu kennzeichnen. Hierzu ist der Wert des Vektors C an Position j li + 1 um eins zu inkrementieren. Es ergibt sich mit j = 5 und mit l1 = 1 die zu inkrementierende Position in C zu 5 1 + 1 = 5 . Der modifizierte Vektor C lautet jetzt: 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Damit ist Position 5 als mgliche Startposition des vollstndigen Pattern P gekennzeichnet und die Untersuchung des Text-Strings kann fortgesetzt werden. An Position 9 des Text-Strings tritt wiederum ein Match mit dem Pattern auf, hier TeilPattern P2 = c. Der Wert an Position j li + 1 muss inkrementiert werden. Mit j = 9 und l2 = 5 ergibt sich 9 5 + 1 = 5 als Startposition des vollstndigen Pattern P in T. Wiederum wird also Position 5 in C inkrementiert und man erhlt den neuen Vektor C:20

Kapitel 3: Textvergleich mit mehreren Mustern 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Im weiteren Verlauf des Textvergleichs werden noch andere Teil-Pattern gefunden. Diese werden hier unter zustzlicher Berechnung der zu inkrementierenden Position in C aufgefhrt. Die Ergebnisse werden in der folgenden Tabelle veranschaulicht: j 11 15 16 22 Teil-Pattern P1 = {ab} P2 = {c} P1 = {ab} P2 = {c} li l1 = 1 l2 = 5 l1 = 1 l2 = 5 zu inkrementierende Position in C 11 1 + 1 = 11 15 5 + 1 = 11 16 1 + 1 = 16 22 5 + 1 = 18

Tabelle 3: Suchergebnisse beim Matching mit Wildcards

Nach vollstndiger Untersuchung des Text-String liegt C in der folgenden Form vor: 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 1 0 1 0 0 0 0 0 0 In C sind nun alle mglichen Startpositionen des Pattern P gekennzeichnet und die tatschlichen Startpositionen knnen abgelesen werden. Das Pattern P mit allen TeilPattern ist an den Positionen in T gefunden, auf die in C k-mal verwiesen wurde, nmlich genau so oft, wie Teil-Pattern existieren. Im vorliegenden Fall besitzt k den Wert 2, der in C an den Positionen 5 und 11 gefunden werden kann. Die Positionen 16 und 18 besitzen lediglich den Wert 1. Dies bedeutet, dass nur ein Teil-Pattern, nicht jedoch das gesamte Pattern P lokalisiert wurde. Das Pattern P = abc kommt somit beginnend bei den Positionen 5 und 11 im Text-String vor.

a a a a a b b a c b a b b b c a b b a a a c a a

Auf diese Weise knnen alle Pi in T entdeckt werden. Matching mit Wildcards kann auch durchgefhrt werden, wenn sowohl Pattern als auch Text-String Wildcards enthalten. Dieses Verfahren wird in [Gus97, S. 199] ausfhrlich erlutert.

3.3.2 Zweidimensionaler TextvergleichBisher basierten die Ausfhrungen bezglich des Textvergleichs mit mehreren Mustern auf linearen Strukturen. Die zuvor beschriebenen Methoden des Pattern-Matching knnen auch bei nicht-linearen Mustern und Texten Anwendung finden. Um einen

21

Kapitel 3: Textvergleich mit mehreren Mustern Einblick in diese Art des Textvergleichs zu vermitteln, wird im Folgenden der Textvergleich anhand zweidimensionaler Strukturen erlutert. Beim Textvergleich werden zur Darstellung von Text-String und Muster

zweidimensionale Arrays verwendet. Das Text-Array wird auf Sub-Arrays untersucht, die mit einem Muster bereinstimmen. Auch beim zweidimensionalen Matching ist der Aho-Corasick-Algorithmus anwendbar. Als Ausgabe des Algorithmus ergibt sich hier ein separates Array von Zustnden. Dies sind die Zustnde des Aho-Corasick Automaten, die in Abhngigkeit von dem in Zeile i und Spalte j des Text-Arrays eingetragenen Symbols erreicht worden sind [Gus97, S. 64]. Das Vorgehen beim zweidimensionalen Matching unter Verwendung des Aho-Corasick-Algorithmus wird anhand der folgenden Arrays erlutert.a b a b a b b

a a a Es sei: P: b b a a a b

a a a a b b b

und

T:

b b b a a a b a a a b b a a b b a a a b b a a b a a a a

Die Spalten des Pattern P werden als eindimensionale Strings verstanden, die sich als Zustnde des Goto-Graphen eines Aho-Corasick Automaten abbilden lassen. Fr P ergibt sich das eindimensionale Pattern P = {aba, aab}. Aus den Strings des eindimensionalen Pattern kann folgender Automat erstellt werden:

Abbildung 5: Automat und Fehler-Funktion

Als Output des Automaten ergeben sich die Zustnde 3 und 5. Entlang der Pfade, die zu diesen Zustnden fhren, lassen sich output(3) = {aba} fr Spalte 1 und 2 des Pattern sowie output(5) = {aab} fr Spalte 3 des Pattern ablesen. Werden diese Endzustnde konkateniert, bildet sich der String 335. 22

Kapitel 3: Textvergleich mit mehreren Musterna a b a 3 a a b 5

{aba} 3 {aab} 5

b a 3

Das Text-Array T wird nun unter Verwendung des in Abbildung 5 dargestellten Automaten untersucht. Fr jedes Symbol des Text-Arrays an Position (i, j) ergibt sich ein Zustand an eben dieser Position in einer Zustandsmatrix S. Dabei bezeichnet i die Spalten und j die Zeilen des Arrays. Bei der Bestimmung der Werte der Zustandsmatrix wird spaltenweise vorgegangen. Die Spalten des Text-Arrays werden wie zuvor die Spalten des Pattern als Strings verstanden. Somit ergibt sich zum Beispiel fr die erste Spalte des Text-Arrays der eindimensionale Text-String {aababa}. Anhand dieses Strings wird der Goto-Graph untersucht und der bei jedem Symbol auftretende Zustand wird in der Zustandsmatrix vermerkt. Die Funktionen, die bei Anwendung des GotoGraphen auf den Text-String {aababa} ausgefhrt werden, sind die folgenden: 1. g(0, a) = 1, Eintrag in S an Position (0,0) ist 1 2. g(1, a) = 4, Eintrag in S an Position (0,1) ist 4 3. g(4, b) = 5, Eintrag in S an Position (0,2) ist 5 4. g(5, a) = fail f(5) = 2 g(2, a) = 3, Eintrag in S an Position (0,3) ist 3 5. g(3, b) = fail f(3) = 1 g(1, b) = 2, Eintrag in S an Position (0,4) ist 2 6. g(2, a) = 3, Eintrag in S an Position (0,5) ist 3 Die Durchfhrung dieser Funktionen fhrt zur ersten Spalte der Zustandsmatrix.1 0 1 0 1 0 0 4 1 4 1 2 0 0 5 2 5 4 3 1 0 3 3 3 5 2 4 1 2 2 4 3 3 5 2 3 3 5 4 4 3 3

S lautet im vorliegen Fall:

Die Zustandsmatrix kann nun nach Vorkommen des aus den Spalten des Pattern konkatenierten String 335 untersucht werden. Das Auftreten dieses String ist in S kenntlich gemacht. Das rechte Ende des Strings markiert die untere rechte Ecke des Pattern P in T. Unter Einsatz dieses Verfahrens knnen alle Vorkommen eines Pattern P 23

Kapitel 4: Zusammenfassung in einem Text T auch beim Vorliegen zweidimensionaler Datenstrukturen gefunden werden. Die zweidimensionalen Pattern, die mit Hilfe der Zustandsmatrix lokalisiert wurden, sind in T hervorgehoben. unter Weitergehende auch bei Ausfhrungen zum zweidimensionalen Matching, anderem nicht-rechtwinkligen

Datenstrukturen, finden sich in [AF92] und [AF91].

4 ZusammenfassungDas im Rahmen dieser Arbeit vorgestellte Pattern-Matching kann in vielen Bereichen angewandt werden. Bei den in diesem Zusammenhang mglichen Verfahren ist zwischen dem Textvergleich mit einem und mit mehreren Mustern zu unterscheiden. Der Aho-Corasick-Algorithmus wird zum Textvergleich mit mehreren Mustern verwendet. Der Algorithmus erstellt in Abhngigkeit von einem dem Textvergleich zugrunde liegenden Muster einen Pattern-Matching-Automaten. Dieser Automat untersucht einen vorliegenden Text-String auf mgliche Vorkommen des Musters. Dabei werden die Funktionen des Automaten, die Goto-, Fehler- und Output-Funktion, angewandt. Der Aho-Corasick-Algorithmus kann auch bei zweidimensionalen Pattern und Text-Strings verwendet werden. Dazu werden die zweidimensionalen Strukturen in eindimensionale Pattern und Text-Strings umgewandelt, bevor der Aho-Corasick Algorithmus in der in dieser Arbeit vorgestellten Ausprgung Anwendung findet. Mit Hilfe der vorgestellten Methoden knnen auch Textvergleiche durchgefhrt werden, bei denen die Muster Wildcard-Symbole enthalten. Hierbei wird unter Zuhilfenahme eines zustzlichen Vektors auf die Positionen im Text-String verwiesen, an denen Substrings des Pattern gefunden werden konnten. Ein Einsatzgebiet fr die Anwendung des Textvergleichs mit mehreren Mustern sind die im Internet vertretenen Suchmaschinen. Durch die Filterung der im Internet vorhandenen Informationen anhand eines oder mehrerer Suchbegriffe wird mit Hilfe des Pattern-Matching mit mehreren Mustern ein sehr gutes Ergebnis erzielt. Bei einer detaillierten Betrachtung der vorgestellten Verfahren ist vielfach eine hohe Laufzeit zu beobachten. Diese wird insbesondere durch die Anzahl der Verarbeitungsschritte des angewandten Verfahrens bestimmt. Um die Laufzeit und auch die Speicherbelegung gering zu halten, sollten Muster angewandt werden, die einen eindeutigen Beitrag zur Identifizierung relevanter Informationen leisten.

24

Literaturverzeichnis[Aho75] Alfred V. Aho: Algorithms for Finding Patterns in Strings, 1975, In: J. van Leeuwen: Handbook of Theoretical Computer Science Vol. A, Elsevier Science Publishers B.V., 1990, S. 256-300. Alfred V. Aho, Margaret J. Corasick: Efficient String Matching: An Aid to Bibliographic Search, Communications of the ACM, Vol. 18 No.6, 1975, S. 333-340. Amihood Amir, Martin Farach: Efficient 2-dimensional Approximate Matching of Non-rectangular Figures, 1991. In: Proc. Of 2nd Symposium on Discrete Algorithms, San Francisco, CA, Jan 1991. Amihood Amir, Martin Farach: Two Dimensional Dictionary Matching, 1992. http://www.cs.rutgers.edu/~farach/pubs/2DDict.pdf. Abrufdatum 2005-02-28. Dan Gusfield: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge Universitiy Press, 1997. M. Kirner, C. Gugimaier, W. Haas: Pattern Matching mit Key-Word-Trees und dem Aho-Corasick Verfahren, 2004. http://www.ads.tuwien.ac.at/teaching/ws04/EffAlg/UE2-Bsp3aGruppeA.pdf. Abrufdatum 2005-03-02.

[AC75]

[AF91]

[AF92]

[Gus97] [Ki04]

[KMP77] D. E. Knuth, J. H. Morris, V.R. Pratt: Fast pattern matching in strings, SIAM Journal on Computing Vol.6, 1977, S. 323-350. [La05] H.W.Lang: Knuth-Morris-Pratt-Algorithmus, Flensburg, 2005. http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/kmp.htm. Abrufdatum 2005-03-04.