Naiwny algorytm dopasowywania ciągów znaków w Pythonie: przykłady, polecane, zalety i wady
Opublikowany: 2020-05-14Gdy 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.
Spis treści
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.

- Gdy wszystkie znaki we wzorcu są takie same jak w ciągu wejściowym.
T [] = „EEEEEEEEEEEEEE”;
P [] = „EEE”;
- 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.

- 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.
- Znajduje dokładne dopasowania ciągów — czy to bardziej, czy dokładniejsze wystąpienia wzorca.
- Jest bardziej używany, gdy jest mały tekst. Co więcej, nie wymaga żadnych etapów wstępnego przetwarzania.
- 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
- W podejściu wyszukiwania naiwnego nie są wymagane żadne etapy przetwarzania wstępnego, ponieważ jego czas działania jest równy czasowi dopasowania.
- Nie jest potrzebna dodatkowa przestrzeń operacyjna.
- 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.
Co to jest naiwny algorytm dopasowywania ciągów znaków?
Naiwny algorytm dopasowywania ciągów to taki, który po prostu porównuje dwa ciągi znak po znaku. Ten naiwny algorytm jest używany przez wiele wczesnych programów komputerowych, które implementowały proste funkcje wyszukiwania plików. Innymi słowy, ciągi są porównywane znak po znaku, a algorytm zatrzymuje się po znalezieniu niezgodności. Jest to nieodpowiedni sposób dopasowywania ciągów znaków, ponieważ jest powolny i marnuje pamięć. Jest to bardzo nieefektywne, ponieważ liczba ciągów w tekście jest ogromna, ale zapytanie wyszukiwania ma tylko kilka znaków.
Jakie są ograniczenia naiwnych algorytmów dopasowywania ciągów znaków?
Niezaspokojenie 8-matek i powiązane problemy jako NP-zupełne pokazują, że naiwne algorytmy dopasowywania strun mają swoje ograniczenia. Naiwny algorytm dopasowywania ciągów nie da ci rozwiązania. W przypadku dopasowywania ciągów wymaga to czasu wykładniczego. Tak więc, jeśli masz n ciągów do dopasowania, ukończenie zajmie 2n czasu. Aby obejść ten problem, opracowano algorytm, który umożliwił wykonanie problemu z dopasowywaniem ciągów znaków. Algorytm ten, który jest algorytmem czasu wykładniczego, nazywa się algorytmem Aho-Corasick. Algorytm ten działa na zasadzie programowania dynamicznego.
Jak możemy zoptymalizować naiwne algorytmy dopasowywania ciągów znaków?
Optymalizacja naiwnych algorytmów dopasowywania ciągów odbywa się na dwa sposoby:
1) Wyszukiwanie w bazie danych ciągów: Jest to najlepsze rozwiązanie do wyszukiwania w bazie danych. Jest szybki, ale wymaga ogromnego budżetu.
2) Próby: są świetną alternatywą dla bazy danych, ponieważ można je tworzyć z pamięci, co sprawia, że są niskobudżetowe. Możesz łatwo przedstawić ciąg w postaci drzewa binarnego. Następnie po prostu przechodzisz przez drzewo i sprawdzasz wynik. Jeśli stwierdzisz, że jesteś na końcu drzewa, znalazłeś dobre dopasowanie. Nie ma potrzeby cofać się do początku drzewa. Ten algorytm jest szybki, ale nie pozwala na porównanie długich ciągów.