Notatnik techniczny

Wyszukiwanie tekstu w tekście

Zadanie, przed którym stajemy: 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ę na pozór 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 algorytmów - spośród bogatego zbioru - 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