Porównanie algorytmów wyszukujących wzorzec w tekście

Abstract

W pracy zaprezentowano 4 algorytmy umożliwiające wyszukiwanie wzorców tekstu. W celu umożliwienia badania własności algorytmów i ich porównania zaprojektowano i zaimplementowano komputerowy system eksperymentalny.
Autor: Grzegorz SAJ

1. SFORMUŁOWANIE PROBLEMU.

Problemem, który często pojawia się w programach do redagowania tekstów, jest znajdowanie miejsca wystąpienia wzorca w tekście. W typowych sytuacjach tekstem jest redagowany dokument, natomiast wzorcem jest konkretne słowo podane przez użytkownika. Algorytmy wyszukiwania wzorca są również używane przy szukaniu specjalnych wzorców w sekwencjach DNA.

Problem wyszukiwania wzorca możemy sformułować następująco. Zakładamy, że tekst jest tablicą T[1...n] długości n, a wzorzec jest tablicą P[1…m] długości m. Ponadto zakładamy, że elementami tablic T i P są symbole należące do pewnego skończonego alfabetu ∑. Może to być na przykład: ∑={0,1} lub ∑={a,b,…,z}.

Mówimy, że wzorzec P występuje z przesunięciem s w tekście T (lub równoważnie, że wzorzec P występuje począwszy od pozycji s+1), gdy 0 ≤ s ≤ n-m oraz T[s+1…s+m]= P[1…m] (tzn. gdy T[s+j]=P[j] dla 1 ≤ j ≤ m). Jeżeli P występuje z przesunięciem s w T, to s nazywamy poprawnym przesunięciem; w przeciwnym razie nazywamy niepoprawnym przesunięciem. Problem wyszukiwania wzorca w tekście polega na znajdowaniu wszystkich poprawnych przesunięć danego wzorca P w ustalonym tekście T. Na rys. 1 pokazano przykład.



W przykładzie celem było znalezienie wszystkich wystąpień wzorca P=ABAA w tekście T=ABCABAABCABAC. Wzorzec występuje dokładnie raz, z poprawnym przesunięciem s=3.