Strona główna » Algorytmy » Artykuły » Naiwne wyszukiwanie wzorca
 

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:

FragmentSzukany fragment
INNie
NFNie
FONie
ORNie
RMNie
MATak
ACNie
CJNie
JANie

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. bool czyWystepuje(char* tekst, char* wzorzec) {
  2.   for (int i = 0; tekst[i]; i++) {
  3.     int j = 0;
  4.     while (wzorzec[j] != '\0' && tekst[i + j] == wzorzec[j])
  5.       j++;
  6.     if (j > 0 && wzorzec[j] == '\0')
  7.       return true;
  8.   }
  9.   return false;
  10. }

(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. void czyWystepujeTEST(char* tekst, char* wzorzec) {
  2.   cout << "W tekscie \"" << tekst << "\" ";
  3.   cout << (czyWystepuje(tekst, wzorzec) ? "" : "nie ");
  4.   cout << "wystepuje \"" << wzorzec << "\"\n";;
  5. }

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

  1. int main () {
  2.   char* tekst = "ab abb aab aaabb";
  3.   czyWystepujeTEST(tekst, "a");
  4.   czyWystepujeTEST(tekst, "ab");
  5.   czyWystepujeTEST(tekst, " b");
  6.   system("pause");
  7.   return 0;
  8. }

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.

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.