Naiwne wyszukiwanie wzorca

Algorytm

Naiwne wyszukiwanie wzorca jest najprostszą metodą sprawdzania czy w przeszukiwanym tekście można znaleźć określone wyrażenie. Jego prosta idea jest wystarczająca, aby wykonać zadanie, ale w przypadku większych danych algorytm ten może okazać się mało efektywny.

Zasada działania

Przypuśćmy, że mamy tekst o długości n oraz wzorzec o długości m. Dla każdej i-tej litery należy sprawdzić m kolejnych znaków czy są zgodne z znakami we wzorcu. Oczywiście porównania są wykonywane dopóki jest sens czyli istnieje kolejne m liter począwszy od i-tego indeksu. Złożoność tego algorytmu w najgorszym przypadku wynosi Θ(n·m) kiedy w każdym sprawdzanym zakresie nie zgadza się tylko ostatni znak. Zazwyczaj jednak algorytm można porównywać z liniowym Θ(n), ponieważ zazwyczaj w każdy fragmencie nie zgadza się już pierwszy znak.

Poniżej znajduje się lista kroków algorytmu:

1. Wczytaj tekst i wzorzec
2. Przypisz m długość tekst i n długość wzorzec
3. Dla każdego indeksu i z [0, n - m + 1]:
   • Wybierz ciąg [i, i + m] z tekstu i porównaj z wzorzec
   • Jeśli są identyczne zwróć, że wzorzec istnieje, w przeciwnym razie kontynuuj pętle
4. Jeśli program wcześniej nie zwrócił wyniku to zwróć, że wzorzec nie występuje

Przykład działania

Weźmy tekst "INFORMACJA" i wyszukajmy tekst "MA" kolejno należy porównywać następujące fragmenty:

Szukany wzorzec został odnaleziony. W zależności od przeznaczenia algorytmu można go kontynuować w celu zliczenia wszystkich wystąpień wzorca, albo przerwać po znalezieniu pierwszego wystąpienia wzorca.

Implementacja

Przypuśćmy, że funkcja czyWystepuje() będzie przyjmować dwa argumenty tablicy znaków: tekst i wzorzec. Wynikiem działania funkcji jest wartość logiczna czy w zmiennej tekst występuje wzorzec. Poniżej znajduje się gotowy kod realizujący to zadanie:

1. def czyWystepuje(tekst, wzorzec):
2.   for i in range(0, len(tekst)):
3.     j = 0;
4.     while (j < len(wzorzec) and tekst[i + j] == wzorzec[j]):
5.       j += 1
6.     if (j > 0 and j == len(wzorzec)):
7.       return True
8.   return False

(2.) Dla każdego znaku w tekście: (3.) sprawdzamy czy kolejnego znaki tekstu od i-tej pozycji są identyczne jak we wzorcu. (5.) Po zakończeniu pętli możliwe są dwa przypadki: wzorzec pasuje i wtedy indeks j będzie większy od zera i będzie wskazywał we wzorcu znak końca danych. W takim przypadku (6.) należy zwrócić prawdę, ponieważ tekst występuje (nieważne ile razy i nieważne gdzie). W przeciwnym razie należy kontynuować pętle for. Jeśli po sprawdzeniu wszystkich znaków wzorzec nie został odnaleziony to (8.) należy zwrócić fałsz.

Powyższy algorytm można zoptymalizować nie sprawdzając ostatnich m - 1 indeksów w tekst, ponieważ dalszy fragment jest krótszy od długości wzorca m. Niemniej należy pamiętać, że w ten algorytm oszczędza czas nie szukając długości tekst i wzorzec.

Testowanie funkcji

W celu przetestowania funkcji najlepiej jest zapisać dodatkową funkcję testującą, która dla podanych parametrów wyświetli zrozumiałe dla człowieka dane:

1. def czyWystepujeTEST(tekst, wzorzec):
2.   print('W tekście \'' + tekst + '\' ', end='')
3.   print('' if czyWystepuje(tekst, wzorzec) else 'nie ', end='')
4.   print('występuje \'' + wzorzec + '\'')

Z kolei w funkcji main() można przetestować działanie funkcji tak jak w kodzie poniżej.

1. tekst = 'ab abb aab aaabb'
2. czyWystepujeTEST(tekst, 'a')
3. czyWystepujeTEST(tekst, 'ab')
4. czyWystepujeTEST(tekst, ' b')

Testowanie można wykonać bez pisania dodatkowej funkcji testującej, ale w ten sposób łatwiej jest zapanować nad sprawdzanymi przypadkami i ujednolicić tekst na konsoli.

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz funkcję o nagłówku ileWystapien(), która będzie przyjmować tablice znaków tekst i wzorzec, następnie zwróci liczbę całkowitą oznaczającą ilość wystąpień wzorzec w tekst. Przetestuj działanie funkcji.

Przykładowo dla tekst "tartak" i wzorca "ta" program ma zwrócić 2. Z kolei dla "informacja" i "pl" zwróci 0.

• Kod źródłowy Zadanie 1