Wyszukiwanie tekstu w tekście


Zadanie: znajdź wzorzec w podanym ciągu znaków

Mamy tekst A o długości N, zawierający K różnych znaków. Mamy również szukany wzorzec B o długości M znaków, M<N. Znajdź pozycję, na której w tekście A znajduje się wzorzec B.

Przykład: szukamy wzorca „NSAENFCVSBGIJTU” w zadanym tekście: „AAAAABBBCCCSVMSOVLNSAENFCVSBGIJTUYHFDYDRRRRRHNFJMGTDR”

Algorytm naiwny

Problem wydaje się banalny. Porównujemy wzorzec z tekstem i gdy natrafimy na pierwszą różnicę, wówczas przesuwamy wzorzec o jedną pozycję. Taki naiwny algorytm możemy zaimplementować następująco:

Uzyskujemy złożoność:

Nie alokujemy pamięci zależnej od długości danych wejściowych, więc mamy złożoność pamięciową stałą. W kwestii złożoności obliczeniowej sprawa jest oczywista, dwie zagnieżdżone pętle iterujące po tekście i wzorcu dają nam złożoność równą iloczynowi długości argumentów.

  O(mn)\\  M(1)\\

Bardziej wydajne algorytmy szukania wzorca w tekście

Poniżej przedstawiam implementacje dwóch spośród bogatego zbioru algorytmów dedykowanych przedstawionemu problemowi.

Porównanie algorytmów

Wszystkie algorytmy poza naiwnym składają się z dwóch faz: przetworzenia tekstu i wyszukiwania wzorca. Dlatego złożoność czasowa została przedstawiona osobno dla każdego z etapów przetwarzania.

Złożoność obliczeniowa
pre-procesing
Złożoność obliczeniowa
wyszukiwania
Algorytm naiwny   O(1)   O(mn)
Algorytm Knuth Morris Pratt   O(m)   O(n)
Algorytm Boyer Moore  O(m+k)   od\hspace{2mm}O(\frac{n}{m}) \hspace{2mm}do\hspace{2mm}O(n)

 

Oznaczenia:

 mdługość wzorca
 ndługość tekstu
krozmiar alfabetu (ilość możliwych znaków)

Linki

Dodaj komentarz

Twój adres email nie zostanie opublikowany.