Serwis Edukacyjny w I-LO w Tarnowie ![]() Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2022 mgr Jerzy Wałaszek |
ProblemW łańcuchu s należy wyznaczyć wszystkie wystąpienia wzorca p. |
Zadanie znajdowania wzorca w łańcuchu rozwiązuje algorytm opracowany przez J. H. Morrisa i V. R. Pratta w 1977 roku. Algorytm działa w czasie liniowym O ( n + m ), gdzie n jest długością przeszukiwanego łańcucha, a m jest długością poszukiwanego wzorca. W algorytmie Morrisa-Pratta (w skrócie algorytm MP) wykorzystuje się tablicę Π, której tworzenie opisane jest w rozdziale o wyszukiwaniu maksymalnego prefikso-sufiksu. Korzysta się przy tym z następującej własności łańcuchów tekstowych:
Załóżmy, iż poszukujemy pierwszego wystąpienie wzorca p w danym łańcuchu tekstowym s. W trakcie porównywania kolejnych znaków łańcucha ze znakami wzorca natrafiliśmy na sytuację, w której pewien prefiks wzorca p, o długości b znaków, pasuje do prefiksu okna w łańcuchu s przed pozycją i-tą, jednakże znak s [ i ] (oznaczony na rysunku symbolem A) różni się od znaku p [ b ] (oznaczony symbolem B ), który znajduje się we wzorcu tuż za pasującym prefiksem:
Algorytm N w takiej sytuacji przesuwa okno
wzorca o jedną pozycję w prawo względem przeszukiwanego tekstu i rozpoczyna od
początku porównywanie znaków wzorca p ze znakami okna nie
korzystając zupełnie z faktu zgodności części znaków. To marnotrawstwo prowadzi
w efekcie do klasy złożoności obliczeniowej O ( n 2 ).
Tymczasem okazuje się, iż wykorzystując fakt istnienia pasującego prefiksu,
możemy pominąć pewne porównania znaków bez żadnej szkody dla wyniku poszukiwań.
Otóż po stwierdzeniu niezgodności okno wzorca przesuwamy, tak aby przed znakiem
s [ i ] znalazł się maksymalny prefikso-sufiks prefiksu wzorca
p:
Dzięki temu podejściu pomijamy niepotrzebne porównania znaków oraz unikamy cofania się indeksu i (przesuwa się jedynie okno wzorca ).
Dla każdego prefiksu wzorca szerokość maksymalnego prefikso-sufiksu można wyznaczyć przed rozpoczęciem wyszukiwania – do tego właśnie celu generujemy tablicę Π algorytmem MP podanym w poprzednim rozdziale. Dla danej długości prefiksu b możemy z tej tablicy odczytać szerokość maksymalnego prefikso-sufiksu tego prefiksu. W naszym przypadku będzie to:
bb = Π [ b ]
Teraz porównujemy znak wzorca p [ bb ] (oznaczony na rysunku symbolem C) ze znakiem s [ i ] (symbol A ). Jeśli wciąż mamy niezgodność, to procedurę powtarzamy, aż do wyczerpania się prefikso-sufiksów – w takim przypadku okno wzorca oraz indeks i przesuwamy o jedną pozycję w prawo.
Jeśli otrzymamy zgodność, to pasujący prefiks zwiększa swoją długość o 1 znak. Przesuwamy również indeks i o 1, ponieważ znak na tej pozycji został już całkowicie wykorzystany przez algorytm MP.
Jeśli prefiks obejmie cały wzorzec (b = | s | ), to znaleziona zostanie pozycja wzorca w s i będzie ona równa i - b + 1. W przeciwnym razie poszukiwania kontynuujemy.
Zwróć uwagę, iż algorytm MP nigdy nie cofa indeksu i. Dzięki tej własności algorytm umożliwia przetwarzanie danych sekwencyjnych – np. wyszukiwanie położenia wzorca w dużym pliku, który fizycznie może nie mieścić się w pamięci operacyjnej komputera – każdy znak pliku jest odczytywany tylko jeden raz.
s | – | łańcuch znakowy |
p | – | poszukiwany wzorzec |
Kolejne pozycje wystąpienia wzorca w łańcuchu. Wartość -1 nie wskazuje żadnej pozycji wzorca i oznacza, iż wzorzec nie występuje w przeszukiwanym łańcuchu.
pp | – | zawiera wyznaczane pozycje wzorca, pp ∈ C |
i | – | pozycja porównywanego znaku w łańcuchu tekstowym s, i ∈ N, 0 ≤ i ≤ | s | |
b | – | długość prefiksu wzorca p pasującego do prefiksu okna wzorca w łańcuchu s, b ∈ N, 0 ≤ b ≤ | p | |
Π | – | tablica o indeksach od 0 do | p |, przechowująca długości maksymalnych prefikso-sufiksów kolejnych prefiksów wzorca p, Π ∈ C |
K01: | Wyznacz tablicę Π | wyznaczamy tablicę maksymalnych prefikso-sufiksów |
K02: | pp ← -1 | wstępna pozycja wzorca ustawiona na -1 |
K03: | b ← 0 | wstępną długość prefikso-sufiksu ustawiamy na 0 |
K04: | Dla i = 0, 1,
... | s | - 1: wykonuj kroki K05...K10 |
pętla wyznacza znaki łańcucha do porównania ze znakami wzorca |
K05: | Dopóki ( b
> -1 )
![]() wykonuj b ← Π [ b ] |
Szukamy we wzorcu p rozszerzalnego prefiksu pasującego do prefiksu okna wzorca. Pętlę K05 przerywamy, jeśli znajdziemy rozszerzalny prefiks lub napotkamy wartownika -1 |
K06: | b ← b + 1 | Rozszerzamy prefiks o 1 znak. Jeśli prefiks był wartownikiem, to otrzymuje wartość 0. |
K07: | Jeśli
b < |p|, to następny obieg pętli K04 |
Jeśli prefiks nie obejmuje całego wzorca, to kontynuujemy pętlę K04, czyli porównujemy znak p [ b ] z kolejnym znakiem łańcucha s. |
K08: | pp ← i - b + 1 | wyznaczamy pozycję wzorca p w łańcuchu s |
K09: | Pisz pp | wyprowadzamy tę pozycję |
K10: | b ← Π [ b ] | redukujemy b do długości prefikso-sufiksu wzorca |
K11: | Jeśli pp = -1, to pisz -1 |
jeśli wzorzec p nie występuje w s, wyprowadzamy -1 |
K12: | Zakończ |
Uwaga: Porównaj algorytm MP wyszukiwania wzorca z algorytmem wyznaczania tablicy Π [ 0 ] i wyciągnij wnioski.
Uwaga:
Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program generuje 79 znakowy łańcuch zbudowany z pseudolosowych kombinacji liter A i B oraz 5 znakowy wzorzec wg tego samego schematu. Następnie program wyznacza tablicę długości maksymalnych prefikso-sufiksów kolejnych prefiksów wzorca i wykorzystuje ją do znalezienia wszystkich wystąpień wzorca w łańcuchu. |
Pascal// Wyszukiwanie wzorca algorytmem MP // Data: 3.06.2008 // (C)2020 mgr Jerzy Wałaszek //----------------------------- program prg; const N = 79; // długość łańcucha s M = 5; // długość wzorca p var s, p : ansistring; PI : array [ 0..M ] of integer; i, b, pp : integer; begin randomize; // generujemy łańcuch s s := ''; for i := 1 to N do s := s + chr ( 65 + random ( 2 ) ); // generujemy wzorzec p := ''; for i := 1 to M do p := p + chr ( 65 + random ( 2 ) ); // dla wzorca obliczamy tablicę PI [ ] PI [ 0 ] := -1; b := -1; for i := 1 to M do begin while( b > -1 ) and ( p [ b + 1 ] <> p [ i ] ) do b := PI [ b ]; inc ( b ); PI [ i ] := b; end; // wypisujemy wzorzec p writeln ( p ); // wypisujemy łańcuch s write ( s ); // poszukujemy pozycji wzorca w łańcuchu pp := 0; b := 0; for i := 1 to N do begin while( b > -1 ) and ( p [ b + 1 ] <> s [ i ] ) do b := PI [ b ]; inc ( b ); if b = M then begin while pp < i - b do begin write ( ' ' ); inc ( pp ); end; write ( '^' ); inc ( pp ); b := PI [ b ]; end end; writeln; end. |
C++// Wyszukiwanie wzorca algorytmem MP // Data: 3.06.2008 // (C)2020 mgr Jerzy Wałaszek //----------------------------- #include <iostream> #include <string> #include <cstdlib> #include <time.h> using namespace std; const int N = 79; // długość łańcucha s const int M = 5; // długość wzorca p int main( ) { string s, p; int PI [ M + 1 ], i, b, pp; srand ( ( unsigned )time ( NULL ) ); // generujemy łańcuch s s = ""; for( i = 0; i < N; i++ ) s += 65 + rand( ) % 2; // generujemy wzorzec p = ""; for( i = 0; i < M; i++ ) p += 65 + rand( ) % 2; // dla wzorca obliczamy tablicę PI [ ] PI [ 0 ] = b = -1; for( i = 1; i <= M; i++ ) { while( ( b > -1 ) && ( p [ b ] != p [ i - 1 ] ) ) b = PI [ b ]; PI [ i ] = ++b; } // wypisujemy wzorzec cout << p << endl; // wypisujemy łańcuch s cout << s; // poszukujemy pozycji wzorca w łańcuchu pp = b = 0; for( i = 0; i < N; i++ ) { while( ( b > -1 ) && ( p [ b ] != s [ i ] ) ) b = PI [ b ]; if( ++b == M ) { while( pp < i - b + 1 ) { cout << " "; pp++; } cout << "^"; pp++; b = PI [ b ]; } } cout << endl; return 0; } |
Basic' Wyszukiwanie wzorca algorytmem MP ' Data: 3.06.2008 ' (C)2020 mgr Jerzy Wałaszek '----------------------------- Const N = 79 ' długość łańcucha s Const M = 5 ' długość wzorca p Dim As String s, p Dim As Integer PI ( M ), i, b, pp Randomize ' generujemy łańcuch s s = "" For i = 1 To N: s += Chr ( 65 + Cint ( Rnd ) ): Next ' generujemy wzorzec p = "" For i = 1 To M: p += Chr ( 65 + Cint ( Rnd ) ): Next ' dla wzorca obliczamy tablicę PI [ ] PI ( 0 ) = -1: b = -1 For i = 1 To M while( b > -1 ) And ( Mid ( p, b + 1, 1 ) <> Mid ( p, i, 1 ) ): b = PI ( b ): Wend b += 1: PI ( i ) = b Next ' wypisujemy wzorzec p Print p ' wypisujemy łańcuch s Print s; ' poszukujemy pozycji wzorca w łańcuchu pp = 0: b = 0 For i = 1 To N while( b > -1 ) And ( Mid ( p, b + 1, 1 ) <> Mid ( s, i, 1 ) ): b = PI ( b ): Wend b += 1 If b = M Then While pp < i - b Print " ";: pp += 1 Wend Print "^";: pp += 1 b = PI ( b ) End If Next Print End |
Wynik: |
BABBB AABABBBBABBBBABABAAABBBAABBBABABBABABBAABABBBBBAABAAAAAAABABBBABBBABAABBBBAAAAB ^ ^ ^ ^ ^ |
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2022 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.