Jak odnaleźć wzorzec w tekście?

Rozważmy następujący problem. Mamy ciąg znaków: jedno słowo (np. „kot”) lub kilka wyrazów – np. zdanie „ala ma kota” (dla uproszczenia pomijamy wielkości liter). Problem wyszukania wzorca w tekście polega na odnalezieniu takiej liczby, która określa, ile początkowych znaków tekstu należy usunąć, aby rozpoczynał się on właśnie od wzorca. W przytoczonym przykładzie taką cyfrą będzie 7. Po usunięciu z ciągu „ala ma kota” 7 początkowych znaków, zostaniemy z wyrażeniem „kota”. Wówczas łatwo zauważyć, że wzorzec „kot” pasuje do początku zdania.

W jaki sposób odbywa się szukanie wzorca w tekście? Pomocna jest tzw. metoda naiwna, określana często mianem brute forcebrute forcebrute force.

Polega ona na wykonywaniu porównania wzorca z początkiem tekstu dla każdej liczby znaków, które z niego usuniemy. Takie wyszukiwanie w podanym przykładzie będzie wyglądało następująco:

R1PPQUTSZhpVo

Ilustracja przedstawia szukanie wzorca słowa: kot, w zdaniu: ala ma kota.
Na samej górze umieszczono zdanie: ala ma kota.
Poniżej znajduje się 10 linii gdzie słowo: kot przesuwane jest o jedną literę względem zdania.
W liniach od 1 do 7 nie znaleziono wzorca i literka k podświetla się na czerwono.
W linii ósmej literka k słowa kot wyrównało się z literka k ze zdania i podświetla się na zielono.
W linii 9 na zielono podświetla się litera: o, a w linii 10: t.

Podstawową wadą tej metody jest to, że nie jest ona optymalna. Nie nadaje się do poszukiwania długich wzorców w długich tekstach. Istnieją algorytmy, które dużo efektywniej radzą sobie w podobnych sytuacjach. Jednym z takich algorytmów jest algorytm Knutha‑Morrisa‑Pratta.

Co to jest metoda naiwna?

Metoda naiwna polega na sprawdzaniu każdego możliwego miejsca w tekście, w którym wzorzec mógłby się zaczynać, i porównywaniu znak po znaku, czy wzorzec pasuje do fragmentu tekstu.

Nie jest to algorytm szczególnie wydajny, ale jego prostota sprawia, że jest idealnym punktem wyjścia do nauki bardziej zaawansowanych technik.

Idea działania

Załóżmy, że mamy tekst T o długości n i wzorzec P o długości m. Algorytm:

1. Przesuwa wzorzec od początku tekstu aż do pozycji n - m.

2. Na każdej pozycji sprawdza, czy znaki wzorca pasują do odpowiadających znaków tekstu.

3. Jeśli wszystkie znaki pasują – mamy dopasowanie.

4. Jeśli choć jeden znak się różni – przesuwamy wzorzec o jedną pozycję dalej.