Naiver String-Matching-Algorithmus in Python: Beispiele, Featured & Pros & Cons

Wenn es notwendig ist, ein Eingabemuster in einer Zeichenkette zu finden, verwenden Codierer und Programmierer den String-Matching-Algorithmus. Im Falle einer kurzen Zeichenfolge bevorzugen Python-Programmierer normalerweise den naiven Ansatz, bei dem das Programm jede Position in der Eingabezeichenfolge auf das Abfragemuster überprüft. Bei Übereinstimmung erfolgt eine Ausgabe mit der Positionsnummer.

Einer der Hauptgründe, warum der naive String-Matching-Algorithmus verwendet wird, ist, dass er schnell ist und ziemlich genaue Ergebnisse liefert. Außerdem ist keine Vorverarbeitung erforderlich. In jedem Fall werden wir diese Vorteile später in diesem Beitrag besprechen. Lassen Sie uns zuerst den Algorithmus für die Mustersuche mit dem naiven Ansatz verstehen.

Naiver Mustersuchalgorithmus

Bei der naiven Zeichenfolgenmustersuche testet das Programm die Position des Eingabemusters P [1……i] in einer Zeichenkette T [1…..m].

Beachten Sie, dass die Länge des Eingabetexts oder der Zeichenfolge immer größer oder gleich der Länge des Musters ist.

Hier ist der naive Mustersuchalgorithmus für verschiedene Programmiersprachen.

Start

pat = Mustergröße

str = Zeichenfolgengröße

für i = 0 bis (str – pat), do

für j = 0 zu pat, do

wenn Text[i+j] ≠ Muster[j], dann

die Schleife unterbrechen

fertig

wenn j == pat, dann

die Position von i als gefundenes Muster anzeigen

fertig

Ende

Dieser Algorithmus ist in der Informatik ziemlich wichtig, da er dabei hilft, Suchergebnisse als Ausgabe bereitzustellen.

Lesen Sie: Arten von KI-Algorithmen, die Sie kennen sollten

Beispiele für Naive String Matching auf Python

Hier ist ein Beispiel, in dem der Ansatz der naiven Mustersuche in einem Python-Code verwendet wird.

# Python-Programm für Naive String Matching

# Suchalgorithmus

def -Suche (P, T):

X = len(P)

Y = len(T)

# Eine Schleife, um P[] einzeln zu verschieben */

für i im Bereich (X – Y + 1):

j = 0

# Prüfen Sie für den aktuellen Index i

# für Musterübereinstimmung */

für j im Bereich (0, X):

if (txt[i + j] ! = P[j]):

brechen

wenn (j == X – 1):

print („Muster an Position gefunden“, i)

# Fahrercode

if __name__ == '__main__':

T = „UPGRADEDUBUPGRAABUPGRADEDU“

P = „AKTUALISIEREN“

Suche (P, T)

Ausgang :

Muster an Position 0 gefunden

Muster an Position 17 gefunden

Erläuterung: Die erste Position ist die 0 -te Position. Da das Muster „UPGRAD“ hier zuerst entdeckt wurde, zeigte die Ausgabe, dass das Muster an Position 0 gefunden wurde.

In ähnlicher Weise wurde das nächste Muster an Position 17 gefunden.

Bester Fall der naiven Mustersuche

Es gibt nur einen besten Fall für den naiven Mustersuchalgorithmus, im Gegensatz zu den beiden schlimmsten Fällen.

Der beste Fall tritt auf, wenn das erste Zeichen im Mustertext nirgendwo in der Eingabezeichenfolge enthalten ist.

Beispiel:

T [] = „UPGRADEDUHIJKLUPGRA“;

P [] = „TUPGRA“;

Und daher ist der Fall der Anzahl übereinstimmender Muster O(n).

Der schlimmste Fall einer naiven Mustersuche

Es gibt zwei schlimmste Fälle bei der naiven Zeichenfolgensuche.

1. Wenn alle Zeichen im Muster mit denen in der Eingabezeichenfolge übereinstimmen.

T [] = „EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE für

P[] = „EEE“;

1. Wenn sich nur das letzte Zeichen im Muster von der Eingabezeichenfolge unterscheidet.

T [] = „EEEEEEEEEEED“;

P [] = „EEEED“;

In solchen Fällen ist die Anzahl der Vergleiche O(m*(n-m+1)).

Merkmale des naiven String-Matching-Algorithmus

Der String-Matching-Algorithmus dient zum Auffinden aller Vorkommen eines bestimmten Musters in einem Text.

Hier sind die wichtigsten Funktionen des Algorithmus.

1. Es ist die einfachste Methode, nach Mustern in einem Eingabetext zu suchen. Es überprüft nacheinander alle Zeichen in der angegebenen Zeichenkette.
2. Es findet die exakten Zeichenfolgenübereinstimmungen – seien es mehr oder genauere Vorkommen des Musters.
3. Es wird eher verwendet, wenn kleiner Text vorhanden ist. Darüber hinaus sind keine Vorverarbeitungsphasen erforderlich.
4. Diese Suchmethode nimmt keinen zusätzlichen Platz ein, um zu arbeiten und nach Mustern in der Zeichenfolge zu suchen.

Lesen Sie auch: Datenstruktur und Algorithmus in Python

Vorteile der naiven Mustersuche

1. Beim Naive-Search-Ansatz sind keine Vorverarbeitungsphasen erforderlich, da seine Laufzeit gleich der Matching-Zeit ist.
2. Es wird kein zusätzlicher Betriebsraum benötigt.
3. Die Vergleiche der Muster mit den Strings können in beliebiger Reihenfolge erfolgen.

Nachteile von Naive String Matching

Es gibt nur einen Nachteil des naiven String-Matching-Ansatzes, nämlich dass er ineffizient ist. Dies liegt daran, dass es, wenn es eine Position gefunden hat, diese nicht erneut verwendet, um die andere Position zu finden. Es geht zurück zum Ausgangspunkt und sucht erneut nach dem Muster. Daher werden die Informationen aus der vorherigen Schicht nicht erneut verwendet.

Fazit

Der naive String-Matching-Algorithmus ist aus verschiedenen Gründen wie keine Vorverarbeitungsanforderungen, kein zusätzlicher Platz für Operationen usw. der am meisten bevorzugte Ansatz, um die Positionen dieser Muster in einem bestimmten Text zu finden. Er kann jedoch nicht für größere Texte verwendet werden, weil seiner Ineffizienz, um große Operationen schneller durchzuführen.

Wir hoffen, dass Ihnen dieser Beitrag einen guten Eindruck vom Ansatz der naiven Mustersuche in Python vermittelt hat. Um mehr über die Verwendung dieses Ansatzes zu erfahren und ein breiteres Verständnis des Themas zu erhalten, wenden Sie sich an die Experten von upGrad. Wir haben speziell konzipierte Kurse für Personen, die ihre Fähigkeiten erweitern möchten. Kontaktieren Sie uns noch heute!

Wenn Sie mehr über KI und maschinelles Lernen erfahren möchten, schauen Sie sich das PG-Diplom in maschinellem Lernen und KI von IIIT-B & upGrad an, das für Berufstätige konzipiert ist und mehr als 450 Stunden strenge Schulungen, mehr als 30 Fallstudien und Aufgaben bietet. IIIT-B Alumni-Status, mehr als 5 praktische Schlusssteinprojekte und Arbeitsunterstützung bei Top-Unternehmen.