6 sierpnia 2016

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

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 stałą złożoność pamięciową. Dwie zagnieżdżone pętle iterujące po tekście i wzorcu dają nam złożoność obliczeniową równą iloczynowi długości argumentów.

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
Knuth Morris Pratt
Boyer Moore
m długość wzorca
n długość tekstu
k rozmiar alfabetu

Linki