Naiwny algorytm dopasowywania ciągów znaków w Pythonie: przykłady, polecane, zalety i wady

Gdy zachodzi potrzeba znalezienia wzorca wejściowego w ciągu znaków, koderzy i programiści stosują algorytm dopasowywania ciągów. Zwykle w przypadku krótkiego ciągu programiści Pythona wolą stosować naiwne podejście, w którym program sprawdza każdą pozycję w ciągu wejściowym pod kątem wzorca zapytania. W przypadku, gdy pasuje, podaje wynik z numerem pozycji.

Jednym z największych powodów, dla których stosuje się naiwny algorytm dopasowywania ciągów, jest to, że jest szybki i daje dość dokładne wyniki. Co więcej, nie wymaga wstępnego przetwarzania. W każdym razie zalety te omówimy w dalszej części tego wpisu. Najpierw zrozummy algorytm wyszukiwania wzorców przy użyciu podejścia naiwnego.

Algorytm wyszukiwania wzorców naiwnych

W naiwnym wyszukiwaniu wzorców ciągów program testuje pozycję wzorca wejściowego P [1……i] w ciągu znaków T [1…..m].

Zauważ, że długość tekstu wejściowego lub ciągu znaków zawsze będzie większa lub równa długości wzorca.

Oto naiwny algorytm wyszukiwania wzorców dla różnych języków programowania.

Zaczynać

pat = wzór Rozmiar

str = rozmiar ciągu

dla i = 0 to (str – pat), do

dla j = 0 to poklepać, do

jeśli tekst[i+j] ≠ wzorzec[j], to

przerwać pętlę

gotowy

jeśli j == pat, to

wyświetl pozycję i jako znaleziony wzorzec

gotowy

Koniec

Algorytm ten jest dość ważny w informatyce, ponieważ pomaga podawać wyniki wyszukiwania jako dane wyjściowe.

Przeczytaj: Rodzaje algorytmów AI, które powinieneś znać

Przykłady naiwnego dopasowywania ciągów w Pythonie

Oto przykład, w którym naiwne podejście do wyszukiwania wzorców jest używane w kodzie Pythona.

# Program Pythona do naiwnego dopasowywania ciągów

# Algorytm wyszukiwania

wyszukiwanie definicji (P, T):

X = len(P)

Y = len(T)

# Pętla do przesuwania P[] jeden po drugim */

dla i w zakresie (X – Y + 1):

j = 0

# Dla bieżącego indeksu i, sprawdź

# dla dopasowania wzorca */

dla j w zakresie (0, X):

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

zepsuć

jeśli (j == X – 1):

print („Wzór znaleziony w pozycji”, i)

# Kod kierowcy

if __name__ == '__main__':

T = „UPGRADEDUBUPGRAABUPGRADEDU”

P = „AKTUALIZACJA”

szukaj(P, T)

Wyjście :

Wzór znaleziony w pozycji 0

Wzór znaleziony w pozycji 17

Wyjaśnienie: Pierwsza pozycja to pozycja 0 . Ponieważ wzorzec „UPGRAD” został tutaj po raz pierwszy zauważony, dane wyjściowe wykazały, że wzorzec znajduje się na pozycji 0.

Podobnie kolejny wzór został znaleziony na pozycji 17.

Najlepszy przypadek naiwnego wyszukiwania wzorców

Jest tylko jeden najlepszy przypadek naiwnego algorytmu wyszukiwania wzorców, w przeciwieństwie do dwóch najgorszych przypadków.

Najlepszy przypadek występuje, gdy pierwszego znaku w tekście wzorca nie ma nigdzie w ciągu wejściowym.

Przykład:

T [] = „UPGRADEDUHIJKLUPGRA”;

P [] = „TUPGRA”;

I dlatego liczba pasujących wzorców case wynosi O(n).

Najgorszy przypadek wyszukiwania wzorców naiwnych

Istnieją dwa najgorsze przypadki w naiwnym podejściu do wyszukiwania ciągów.

1. Gdy wszystkie znaki we wzorcu są takie same jak w ciągu wejściowym.

T [] = „EEEEEEEEEEEEEE”;

P [] = „EEE”;

1. Gdy tylko ostatni znak we wzorcu różni się od ciągu wejściowego.

T [] = „EEEEEEEEEEED”;

P [] = „EEEED”;

W takich przypadkach liczba porównań w O(m*(n-m+1)).

Cechy algorytmu naiwnego dopasowywania ciągów

Algorytm dopasowywania ciągów znaków służy do wyszukiwania wszystkich wystąpień danego wzorca w tekście.

Oto najważniejsze cechy algorytmu.

1. Jest to najprostsza ze wszystkich metoda wyszukiwania wzorców w tekście wejściowym. Sprawdza wszystkie znaki jeden po drugim w podanym ciągu znaków.
2. Znajduje dokładne dopasowania ciągów — czy to bardziej, czy dokładniejsze wystąpienia wzorca.
3. Jest bardziej używany, gdy jest mały tekst. Co więcej, nie wymaga żadnych etapów wstępnego przetwarzania.
4. Ta metoda wyszukiwania nie zajmuje dodatkowej przestrzeni do pracy i wyszukiwania wzorców w ciągu.

Przeczytaj także: Struktura danych i algorytm w Pythonie

Zalety wyszukiwania wzorców naiwnych

1. W podejściu wyszukiwania naiwnego nie są wymagane żadne etapy przetwarzania wstępnego, ponieważ jego czas działania jest równy czasowi dopasowania.
2. Nie jest potrzebna dodatkowa przestrzeń operacyjna.
3. Porównania wzorów z ciągami można wykonać w dowolnej kolejności.

Wady naiwnego dopasowywania ciągów

Naiwne podejście do dopasowywania ciągów ma tylko jedną wadę, a mianowicie jest nieefektywne. Dzieje się tak, ponieważ po znalezieniu pozycji nie używa jej ponownie do znalezienia innej pozycji. Wraca do punktu wyjścia i ponownie szuka wzoru. I tak nie wykorzystuje ponownie informacji z poprzedniej zmiany.

Wniosek

Naiwny algorytm dopasowywania ciągów znaków jest najbardziej preferowanym podejściem do znajdowania pozycji wspomnianych wzorców w danym tekście z różnych powodów, takich jak brak wymogu wstępnego przetwarzania, brak dodatkowego miejsca na operację itp. Nie można go jednak stosować w przypadku raczej większych tekstów, ponieważ jego nieefektywności w szybszym wykonywaniu dużych operacji.

Mamy nadzieję, że ten post dał ci zasadniczo dobry pomysł na naiwne podejście do wyszukiwania wzorców w Pythonie. Aby poznać zastosowania tego podejścia i lepiej zrozumieć temat, skontaktuj się z ekspertami z upGrad. Mamy specjalnie zaprojektowane kursy dla osób, które chcą poszerzyć swoje umiejętności. Skontaktuj się z nami już dziś!

Jeśli chcesz dowiedzieć się więcej o sztucznej inteligencji, uczeniu maszynowym, sprawdź dyplom PG IIIT-B i upGrad w uczeniu maszynowym i sztucznej inteligencji, który jest przeznaczony dla pracujących profesjonalistów i oferuje ponad 450 godzin rygorystycznych szkoleń, ponad 30 studiów przypadków i zadań, Status absolwentów IIIT-B, ponad 5 praktycznych praktycznych projektów zwieńczenia i pomoc w pracy z najlepszymi firmami.