Zaawansowane algorytmy i struktury danych/Wykład 1

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zaawansowane algorytmy tekstowe I


Algorytmy tekstowe są istotne w wielu dziedzinach informatyki, jak na przykład w edytorach tekstowych lub wyszukiwarkach. Tekst jest naturalnym typem informacji.

Formalnie tekst jest ciągiem symboli. Przyjmujemy, że jest on zadany tablicą , elementami której są symbole. Liczba jest długością (rozmiarem) tekstu. W większości naszych algorytmów jedyne operacje dopuszczalne na symbolach wejściowych to porównania dwóch symboli.

Podstawowym problemem tekstowem jest problem string matchingu, polegający na szukaniu wzorca w tekście . Elementami tablic są symbole. Na kursie z ASD przerabialiśmy algorytm Knutha-Morrisa-Pratt(w skrócie KMP) i jego wariacje. Zaprezentujemy bardziej zaawansowany algorytm dla tego problemu: algorytm Boyera-Moore'a (w skrócie BM). Pomimo tego, że jest jasne jak ten algorytm działa, to jednak jego pełna analiza (złożoność, preprocessing) jest zawansowana.

Algorytm Boyera-Moore'a

Algorytm przykłada do tekstu startując od pozycji -tej w . Sprawdzamy, czy . Pozycja wędruje ze strony lewej do prawej. Jednakże, w przeciwieństwie do algorytmu KMP, równość sprawdzamy od strony prawej do lewej. Zaczniemy od algorytmu naiwnego.

Algorytm Naiwny-BM



'while do
   ,br>    while and do
   if then return true;
   {zachodzi niezmiennik}
return false;

Jeśli zachodzi równość, to stwierdzamy, że znaleźliśmy wystąpienie i kończymy. W przeciwnym razie mamy niezmiennik:

oraz .

Korzystając z niezmiennika liczymy przesunięcie większe niż 1. Przesunięcie jest bezpieczne, gdy jesteśmy pewni, że w każdej sytuacji pomiędzy oraz nie zaczyna się żadne wystąpienie wzorca w tekście . Przypuśćmy, że zaczyna od pozycji (zobacz Rysunek 1, gdzie jest przedstawiony przypadek .)

Zachodzi wtedy następujący warunek:

warunek1(j,s): dla każdego k lub ,

warunek2(j,s): { własność niezgodności }.


Zasd 1.jpg
Rysunek 1: Przesunięcie w algorytmie BM. Przypadek gdy .


Definiujemy dwa rodzaje przesunięć. Każde z nich dotyczy sufiksu wzorca zaczynającego się od pozycji.

.

Definiujemy również

.

Algorytm {BM} jest wersją algorytmu Naiwny-BM, w którym przeunięcie o jeden zamieniamy na przesunięcie o , zobacz Rysunek 2.


Algorytm BM



while do
   ;    while and do;
   if then return true;
   { \} ;
return false;

Udowodnimy potem, że algorytm ten ma złożoność liniową. Jednakże w przeciwieństwie do łatwej analizy algorytmu KMP, w tym przypadku analiza jest skomplikowana. Mamy tu przykład algorytmu, którego poprawność jest dosyć oczywista, a analiza kosztu jest nietrywialna.

Zasd 2.jpg
Rysunek 2: Historia algorytmu BM na przykładowych tekstach .


Zasd 2.jpg
Rysunek 3: Działanie dwóch wersji algorytmu BM na przykładowych tekstach. Algorytm BM stosujący przesunięcie wykonuje 30 porównań symboli więcej (rysunek z lewej strony) niż normalny algorytm BM stosujący tablicę BM (rysunek prawej strony).

Algorytm BM ze słabszą tablicą przesunięć

Jeśli zastąpimy tablicę przez , wówczas czas algorytmu BM staje się kwadratowy. Przykładem tekstów, dla których osiągana jest wtedy złożoność kwadratowa są:

Pozostawiamy jako ćwiczenie podanie wzoru na liczbę porównań z tablicą dla tych tekstów.


Różnica między i wydaje się być podobna do tej między silnymi prefikso-sufiksami i prefikso-sufiksami w algorytmie KMP. W obu przypadkach różnica sprowadza się do wykorzystania jednego bitu informacji, niezgodności dwóch symboli. Podczas gdy nie robi to istotnej różnicy w pesymistycznej złożoności algorytmu KMP, w tym przypadku jest to znacząca różnica między czasem kwadratowym i liniowym. Porównajmy działanie algorytmu z przesunięciem i of na tekstach(patrz rysunek)

oraz .

Pewna własność kombinatoryczna tekstów

Okresem tekstu jest każda niezerowa liczba naturalna taka, że dla każdego , dla którego obie strony są zdefiniowane. Przez oznaczmy minimalny okres . Okres jest \mathit{ pełny} gdy jest dzielnikiem .

Jeśli jest własciwym (mniejszym od ) dzielnikiem , to nazywamy rozkładalnym, w przeciwnym przypadku nazywamy słowem pierwotnym (albo nierozkładalnym).

Na przykład jest rozkładalne, natomiast jest pierwotne.

Lemat Kombinatoryczna własność słów pierwotnych

Jeśli jest pierwotne to x nie ma wystąpienia wewnątrz xx.


Zasd 4.jpg
Rysunek 4: Jeśli tekst jest pierwotny, to taka sytuacja jest niemożliwa ( nie może występować wewnątrz tekstu .


Własność ta mówi, że nie może zajść sytuacja przedstawiona na Rysunku 4. Dowód własności korzysta z tzw. lematu o okresowości dla tekstów: jeśli ma okresy oraz to jest również okresem .

Popatrzmy na rysunek. Gdyby występował w , to miałby dwa okresy takie, że . Z lematu o okresowości wynika wtedy, że ma okres mniejszy od i będący dzielnikiem . Zatem słowo nie byłoby pierwotne, co jest sprzeczne z założeniem. \myskip Jako ćwiczenie pozostawiamy problem sprawdzania w czasie liniowym czy słowo jest pierwotne.

Analiza złożoności algorytmu BM

Dokładne oszacowanie na liczbę porównań w algorytmie BM wynosi około 3n. Dowód tego faktu jest jednak zbyt skomplikowany. Pokażemy tutaj oszacowanie górne 4n, dolne oszacowanie 3n pozostawiamy jako ćwiczenie.

Jeśli się głębiej zastanowić, to liniowy czas algorytmu BM jest zdumiewający. Algorytm zapomina, jaka część tekstu <mathy</math> pasowała do wzorca i sprawdza wielokrotnie te same fragmenty, które już poprzednio były sprawdzone z wynikiem pozytywnym. Zjawisko takie nie ma miejsca w algorytmie KMP, gdzie raz sprawdzony pozytywnie symbol w tekście nie jest już nigdy więcej sprawdzany.


Zasd 5.jpg
Rysunek 5: Segment tekstu jest aktualnym dopasowaniem, oznacza najkrótszy pełny okres sufiksu wzorca , jest również okresem aktualnego dopasowania. Zaciemniony obszar jest częścią tekstu, która nigdy wcześniej nie była odwiedzana (sprawdzana).


Załóżmy, że w danej nieterminalnej iteracji algorytm BM sprawdza segment tekstu , a następnie wykonuje przesunięcie , gdzie oraz. Przez aktualne dopasowanie rozumiemy aktualnie sprawdzany segment tekstu bez pozycji, na której występuje niezgodność symboli (patrz Rysunek 5).

Niech będzie najmniejszym pełnym okresem tekstu , a niech będzie słowem odpowiadającym temu okresowi. Inaczej mówiąc zakładamy, że mamy taką sytuację jak na Rysunku 5. Zauważmy, że rozważamy tu okresowość w dwóch aspektach: jako liczbę (długość) oraz jako słowo.

Zdefiniujmy własność pierwszego odwiedzenia:

  • pozycje w segmencie nie były sprawdzane w poprzednich iteracjach.

Udowodnimy następujący silny i całkowicie nietrywialny fakt.

Lemat

Własność pierwszego odwiedzenia zachodzi w każdej nieterminalnej iteracji algorytmu BM.

Dowód będzie polegał na zauważeniu kilku drobniejszych własności. Następująca własność wynika w sposób oczywisty z założeń: jest słowem-okresem aktualnego dopasowania oraz jest sufiksem wzorca.

Wprowadzimy kluczowe pojęcie pozycji krytycznej jako pozycji w aktualnym dopasowaniu , która jest odległa od końca aktualnego dopasowania o wielokrotność oraz od początku co najmniej o .

Mówimy, że poprzednie dopasowane kończyło się na pozycji w tekście , jeśli w pewnej poprzedniej iteracji koniec wzorca był przyłożony do pozycji w .

Własność 1 Żadne poprzednie dopasowanie nie kończy się na pozycji krytycznej w aktualnym dopasowaniu.

Dowód własności 1 Dowód ma charakter filozoficzny: gdyby własność 1 dla pewnej iteracji nie zachodziła, to nie byłoby tej iteracji. Gdyby poprzednia iteracja kończyła się na pozycji krytycznej, następnym końcem dopasowania byłaby pozycja . W ten sposób przeskoczylibyśmy aktualną iterację. Zatem własność 1 zawsze zachodzi.

Własność 2 Wielkość wspólnej częśc aktualnego dopasowania i danego poprzedniego dopasowania jest mniejsza od . Dowód własności 2. Z własności 1 wynika, że koniec poprzedniego dopasowania nie kończy się na pozycji krytycznej. Gdyby wspólna część była większa niż , to słowo pierwotne występowałoby wewnątrz słowa , co zaprzecza własności słów pierwotnych. Zatem musi zachodzić własność 2.

Własność 3 Jeśli poprzednie dopasowanie kończy się na pozycji wewnątrz aktualnego dopasowania i zawiera się całkowicie w aktualnym dopasowaniu, nie ma krytycznej pozycji na prawo od .

Dowód własności 3. Przypuśćmy, że jest pewna pozycja krytyczna na prawo od . Wówczas jest dobrym kandydatem na przesunięcie w Algorytmie BM. Ponieważ algorytm BM wybiera najmniejsze przesunięcie spośród kandydatów na przesunięcie, spełniających warunek 1. i warunek 2., otrzymamy nową pozycję jako koniec następnego dopasowania. Wynika stąd, że mamy sekwencję końcowych pozycji poprzednich dopasowań, z których każda jest mniejsza od . Wszystkie te liczby są różnymi liczbami naturalnymi. W pewnym momencie jedna z nich musi być równa . W tym momencie mamy poprzednie dopasowanie, kończące się na pozycji krytycznej . Przeczy to własności 2. Zatem własność 3 musi zachodzić.

Dowód własności pierwszego odwiedzenia. Trzy własności, przed chwilą udowodnione, wystarczają do tego, żeby uzasadnienie własności pierwszego odwiedzenia było proste. Dowód jest przez zaprzeczenie. Przypuśćmy, że w pewnej poprzedniej iteracji odwiedziliśmy "zabroniony" obszar aktualnego dopasowania (zacienioną część tekstu na Rysunku 5). Niech będzie końcem tego poprzedniego dopasowania. Zatem nie jest pozycją krytyczną. Na prawo od niej jest pewna pozycja krytyczna. Jest to sprzeczne z własnością 3. Kończy to dowód własności pierwszego odwiedzenia.

Możemy teraz przystąpić do ostatecznej analizy algorytmu BM.

Theorem 3.1 [Analiza algorytmu BM]

Algorytm BM wykonuje co najwyżej porównań symboli do momentu znalezienia pierwszego wystąpienia wzorca lub zakończenia szukania z wynikiem negatywnym. Algorytm działa w czasie , współczynnik kosztu nie zależy od rozmiaru alfabetu.

Z własności pierwszego odwiedzenia wynika bezpośrednio: jeśli jest przesunięciem w nieterminalnej iteracji, to co najwyżej pozycji tekstu sprawdzanych w tej iteracji było sprawdzane w poprzednich iteracjach.

Koszt każdej nieterminalnej iteracji można rozdzielić na dwie części.

(1) Koszt odwiedzenia symboli w tekście po raz pierwszy, (2) Potrojone przesunięcie.

Sumaryczna liczba porównań symboli typu (1) wynosi co najwyżej , sumaryczna liczba porównań typu (2)wynosi co najwyżej, ponieważ suma przesunięć nie przekracza . Dodatkowo może dojść porównań w terminalej iteracji. Zatem w sumie liczba porównań jest ograniczona przez:


Tablica Prefikso-Prefiksów

W fazie preprocessingu algorytmu BM (obliczanie tablicy ) potrzebny będzie algorym liczenia dodatkowej tablicy tzw. prefikso-prefiksów. Jest ona modyfikacją tablicy prefikso-sufiksów: jest długością najdłuższego prefiksu tekstu , którego wystąpienie rozpoczyna się na pozycji . Bardziej formalnie:

jest prefiksem \}.
Zasd 6.jpg
Rysunek 6: Typowa sytuacja w algorytmie Prefikso-Prefiksu. Liczymy PREF dla nowej pozycji j, zakładając, że znamy wartości tablicy PREF dla pozycji wcześniejszych.

Przykład

Dla mamy:

Jako ćwiczenie pozostawiamy redukcję problemu liczenia tablicy do liczenia tablicy (tablica ta była liczona na wykładzie z ASD).

Przedstawimy niezależny interesujący algorytm liczenia tablicy . W algorytmie liczymy tablicę PREF przeglądając tekst od lewej do prawej. Załóżmy, że przetwarzamy pozycję -tą (gdzie ). Zachodzi wtedy następujący niezmiennik (patrz Rysunek 6)

wartości dla są już policzone

jest pozycją maksymalizującą .

Dodajemy specjalny znacznik końca tekstu na pozycji w . Korzystamy z dodatkowej prostej funkcji :

= takie, że .


Jeśli nie ma takiego to . Wartość PREF[1] nie jest dla nas interesująca.


Algorytm Prefikso-Prefiksy


; ;
for to do
   ; ;
   if then
      ;
      if then ;
   else if then
      
   else
      ;
      ;;


Najważniejszą częścią algorytmu jest przekopiowywanie, w pewnych sytuacjach, wartości wcześniej policzonych na . Dzieje się to wtedy, gdy jest duże i jest małe ( jest wartością przeskalowaną względem ).

Obliczanie tablicy BMShift

Pokażemy, że czas konstrukcji tablicy jest liniowy, podstawową częścią będzie obliczanie tablicy . Używając algorytmu liczenia , obliczamy w czasie liniowym symetryczną tablicę sufisko-sufiksów: jest długością maksymalnego sufiksu tekstu , który kończy się na pozycji. Tablica odpowiada tablicy obliczonej dla odwróconego wzorca .

Algorytm Sufikso-sufiksy


odwrócony wzorzec ;

oblicz tablicę dla tekstu ;

for each {} do ;


Zasd 7.jpg
Rysunek 7: Przypadek gdy . Dla , oraz przykładowego tekstu rozmiaru , mamy . Otrzymujemy , zatem . Dla ,mamy , zatem .


Obserwacja. Jeśli , to .


Przykład

Dla i przykładowego wzorca x na Rysunku 7 mamy:

, oraz .


Gdy korzystamy z powyższej obserwacji, przesunięcia w algorytmie BM obliczane są następująco. Inicjalizujemy dla każdego .


Algorytm Oblicz-BMShift


for to do
   ;


Dla przypadku, gdy po wykonaniu powyższego algorytmu, otrzymane wartości nie muszą być poprawne. W tym przypadku heurystyka niezgodności na jednej pozycji jest ignorowana i sprowadzamy obliczenie do prefikso-sufiksów całego wzorca . Załóżmy, że , niech będzie długością maksymalnego prefiksu wzorca, który jest sufiksem całego wzorca, oraz . Przyjmujemy wtedy