Pattern Matching wird in der Informatik und vielen anderen Bereichen häufig eingesetzt. Mustervergleichsalgorithmen werden verwendet, um nach Mustern innerhalb eines größeren Text- oder Datensatzes zu suchen. Einer der beliebtesten Algorithmen für den Mustervergleich ist der Boyer-Moore Algorithmus, der erstmals 1977 veröffentlicht wurde. In diesem Artikel werden wir Mustervergleichsalgorithmen in C und ihre Funktionsweise besprechen.
Was ist ein Mustervergleichsalgorithmus?
Mustervergleichsalgorithmen werden verwendet, um Muster in einem größeren Daten- oder Textsatz zu finden. Diese Algorithmen funktionieren, indem sie ein Muster mit einem größeren Datensatz oder Text vergleichen und feststellen, ob das Muster vorhanden ist oder nicht. Mustervergleichsalgorithmen sind wichtig, weil sie es uns ermöglichen, schnell nach Mustern in großen Datenmengen zu suchen.
Vicky Kaushal Alter
Brute-Force-Mustervergleichsalgorithmus:
Brute Force Pattern Matching ist der einfachste Mustervergleichsalgorithmus. Dabei werden die Zeichen des Musters nacheinander mit den Zeichen des Textes verglichen. Wenn alle Zeichen übereinstimmen, gibt der Algorithmus die Startposition des Musters im Text zurück. Wenn nicht, geht der Algorithmus zur nächsten Position im Text und wiederholt den Vergleich, bis eine Übereinstimmung gefunden wird oder das Ende des Textes erreicht ist. Die Zeitkomplexität des Brute-Force-Algorithmus beträgt O(MXN) , Wo M bezeichnet die Länge des Textes und N bezeichnet die Länge des Musters.
Naiver Mustervergleichsalgorithmus:
Der Naive Pattern Matching-Algorithmus ist eine Verbesserung gegenüber dem Brute Force-Algorithmus. Es vermeidet unnötige Vergleiche, indem einige Stellen im Text übersprungen werden. Der Algorithmus beginnt an der ersten Position, das Muster mit dem Text zu vergleichen. Wenn die Zeichen übereinstimmen, geht es zur nächsten Position und wiederholt den Vergleich. Stimmen die Zeichen nicht überein, geht der Algorithmus zur nächsten Position im Text und vergleicht das Muster erneut mit dem Text. Die zeitliche Komplexität des Naive-Algorithmus ist ebenfalls O(MXN) , ist aber in den meisten Fällen schneller als der Brute-Force-Algorithmus.
Knuth-Morris-Pratt-Algorithmus:
Der Knuth-Morris-Pratt (KMP) Der Algorithmus ist ein fortgeschrittener Mustervergleichsalgorithmus. Es basiert auf der Beobachtung, dass bei einer Nichtübereinstimmung einige Informationen über den Text und das Muster verwendet werden können, um unnötige Vergleiche zu vermeiden. Der Algorithmus berechnet vorab eine Tabelle, die Informationen über das Muster enthält. Die Tabelle bestimmt, wie viele Zeichen des Musters übersprungen werden können, wenn eine Nichtübereinstimmung auftritt. Die zeitliche Komplexität der KMP Algorithmus ist O(M+N) .
Der Boyer-Moore-Algorithmus:
Einer der beliebtesten Pattern-Matching-Algorithmen ist der Boyer-Moore Algorithmus. Dieser Algorithmus wurde erstmals 1977 von Robert S. Boyer und J Strother Moore veröffentlicht. Der Boyer-Moore Der Algorithmus vergleicht ein Muster mit einem größeren Daten- oder Textsatz von rechts nach links statt von links nach rechts, wie bei den meisten anderen Mustervergleichsalgorithmen.
Der Boyer-Moore Der Algorithmus besteht aus zwei Hauptkomponenten: der Regel für schlechte Zeichen und der Regel für gute Suffixe. Die Regel für fehlerhafte Zeichen vergleicht das Zeichen im Muster mit dem entsprechenden Zeichen in den Daten oder im Text. Wenn die Zeichen nicht übereinstimmen, verschiebt der Algorithmus das Muster nach rechts, bis er ein übereinstimmendes Zeichen findet. Die gute Suffixregel vergleicht das Suffix des Musters mit dem entsprechenden Suffix der Daten oder des Textes. Wenn die Suffixe nicht übereinstimmen, verschiebt der Algorithmus das Muster nach rechts, bis er ein passendes Suffix findet.
Der Boyer-Moore Der Algorithmus ist für seine Effizienz bekannt und wird in vielen Anwendungen häufig eingesetzt. Er gilt als einer der schnellsten verfügbaren Mustervergleichsalgorithmen.
Implementierung des Boyer-Moore-Algorithmus in C:
Um das umzusetzen Boyer-Moore Algorithmus in C können wir mit der Definition der Regel für schlechte Zeichen beginnen. Wir können ein Array verwenden, um das letzte Vorkommen jedes Zeichens im Muster zu speichern. Dieses Array kann bestimmen, wie weit wir das Muster nach rechts verschieben müssen, wenn eine Nichtübereinstimmung auftritt.
Hier ist ein Beispiel, wie wir die Regel für schlechte Zeichen in C implementieren können:
Kajal Aggarwal
C-Code:
void bad_character_rule(char *pattern, int pattern_length, int *bad_char) { int i; for (i = 0; i <no_of_chars; i++) bad_char[i]="-1;" for (i="0;" i < pattern_length; bad_char[(int) pattern[i]]="i;" } pre> <p>In this example, we first initialize the array to -1 for all characters. We then iterate through the pattern and update the array with the last occurrence of each character in the pattern.</p> <p>Next, we can implement the good suffix rule. We can use an array to store the length of the longest suffix of the pattern that matches a suffix of the data or text. This array can be used to determine how far we need to move the pattern to the right.</p> <hr></no_of_chars;>