Notatnik techniczny

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:

text = "AAAAABBBCCCSVMSOVLNSAENFCVSBGIJTUYHFDYDRRRRRHNFJMGTDR"
pattern = "NSAENFCVSBGIJTU"
 
def fing_pattern_naive_algorithm(text, pattern):
    text_len = len(text)
    pattern_len = len(pattern)
    for i in range(text_len - pattern_len):
        pattern_match = True
        for j in range(len(pattern)):
            if text[i + j] != pattern[j]:
                pattern_match = False
                break
        if pattern_match:
            return i
    return -1
 
result = fing_pattern_naive_algorithm(text, pattern)

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) O(mn)\ M(1)\

Bardziej wydajne algorytmy szukania wzorca

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(1) O(mn)O(mn)
Algorytm
Knuth Morris Pratt
O(m)O(m) O(n)O(n)
Algorytm
Boyer Moore
O(m+k)O(m+k) odO(nm)doO(n)od\hspace{2mm}O(\frac{n}{m}) \hspace{2mm}do\hspace{2mm}O(n)
m długość wzorca
n długość tekstu
k rozmiar alfabetu

Linki