Wyszukiwanie wzorca

11.12.2009
TrudnośćTrudność

Przypomnieliśmy sobie co to jest automat skończony oraz w jaki sposób można automat skończony może pomóc w znajdowaniu wystąpień wzorca.

Dla wzorca $ p=p_0 \ldots p_{m-1} $, automat taki ma $ m+1 $ stanów $ q_0,\ldots,q_m $.

Pokazaliśmy sobie, że dla stanu $ q_k $ dla $ k<m $ krawędź z literką $ p_{k} $ idzie zawsze do stanu $ q_{k+1} $. Na przykład ze stanu startowego $ q_0 $, krawędź z literką $ p_0 $ prowadzi do stanu $ q_1 $. Pokazaliśmy także, że inne krawędzie wychodzące z $ q_k $ są po prostu "przekopiowane" z jakiegoś innego stanu $ q_{\Pi[k]} $. Podobnie jest dla stanu $ q_m $, tyle, że z niego nie wychodzi żadna krawędź w przód.

Powiedzieliśmy sobie, że dla ustalonego $ k $ całkiem łatwo znaleźć $ \Pi[k] $. Przypomnijmy sobie, że $ \Pi[k] $ to ma być długość najdłuższego sufiksu prefiksu $ p $ o długości $ k $, który jest jednocześnie prefiksem $ p $. Wystarczy skreślić pierwszą literkę i wyszukać tak powstałe słowo w automacie. Czyli jeśli chcemy wiedzieć dla stanu $ q_k $, od kogo należy skopiować krawędzie, to wystarczy uruchomić automat na słowie $ p_1 \ldots p_{k-1} $ i zobaczyć w jakim stanie się zatrzyma.

Ustaliliśmy, że taka bezpośrednia implementacja wymagałaby $ \Theta(m*\sigma) $ komórek pamięci, gdzie $ \sigma $ to liczba liter w alfabecie, czyli na nasz użytek 256. A także, że konstrukcja automatu wymagałaby czasu $ \Theta(m^2 + m*\sigma) $. Pierwszy składnik sumy wynika z naiwnego podejścia do wyszukiwania $ \Pi[k] $, drugi wynika z przekopiowywania krawędzi. Wyszukiwanie wystąpień wzorca $ p $ w tekście $ w=w_1\ldots w_n $ trwa $ \Theta(n) $

Pokazaliśmy sobie, że znalezienie $ \Pi[k+1] $ można sobie znacząco uprościć, jeśli znaleźliśmy w poprzednim kroku $ \Pi[k] $. Wystarczy po prostu przejść krawędzią o etykiecie $ p_{k} $ ze znalezionego poprzednio wierzchołka $ q_{\Pi[k]} $. Pozwala to skrócić czas konstrukcji automatu do czasu zależnego od wypełnienia wielkości potrzebnej nam tablicy $ next[m+1][\sigma] $.

Stwierdziliśmy, że możemy w razie potrzeby zmniejszyć zużycie pamięci kosztem czasu działania wyszukiwania wzorca. Np. można myśleć o tym wszystkim na poziomie poszczególnych bitów zamiast bajtów i dzięki temu mieć tablicę o wielkości m*8*2, zamiast m*256, ale koszt jest taki, że algorytm będzie działał 8 razy wolniej.

Pod koniec zajęć doszliśmy do rozwiązania, które stara się symulować automat skończony nie pamiętając go. Podczas zabawy w konstruowanie automatu, odkryliśmy przecież, że w nim większość krawędzi jest skopiowana z innego miejsca. Trzymanie kopii informacji jest z reguły symptomem, że coś jest bardzo źle. Warto się zastanowić jak usunąć tego typu redundancję i tym samym skompresować dane.

Ciekawym rozwiązaniem, które przyszło mi właśnie do głowy jest aby automat reprezentować nie jako tablicę tylko jako obiekt. Tzn zamiast mieć tablicę $ next[m+1][\sigma] $ moglibyśmy mieć funkcję next(int k,char c). Oto ona w pseudokodzie:

1
2
3
4
5
6
7
8
9
int next(int k,char c){
  if(k<m && p[k]==c){
    return k+1;
  }else if(k==0){
    return 0;
  }else{
    return next(PI[k],c);
  }  
}

Jak widać do poprawnego działania tej funkcji potrzebna jest "tylko" tablica PI. To co jest fajne, to że tablicę PI można zbudować używając funkcji next:

1
2
3
4
5
PI[0]= 0;
PI[1]= 0;
for(int k=2;k<=m;++k){
  PI[k]=next(PI[k-1],p[k-1]);
}

Zauważmy, że do wyliczenia wartości PI[k], musimy wywołać funkcję next, która może potrzebować użyć tablicy PI. Jednak będzie potrzebować dostępu do komórki o numerze mniejszym niż $ k $, którą zdążyliśmy już poprawnie wyliczyć.

Na sam koniec powiedzieliśmy sobie, że powyższy algorytm jest dobrym przykładem na algorytm dynamiczny, oraz na algorytm o linijowej zamortyzowanej złożoności.

Dynamiczny, to znaczy, że wylicza poprawne wyniki dla większych danych w oparciu na spamiętane wcześniej poprawne wyniki dla mniejszych danych. Słowo "dynamiczny" bierze się stąd, że tego typu algorytmom łatwo w locie powiedzieć, że chcemy wyszukać jednak nieco dłuższy wzorzec. Np. ktoś wpisuje szukany wzorzec literka po literce, a my możemy na bieżąco, czyli dynamicznie aktualizować tablicę $ \Pi $.

Analiza zamortyzowanego kosztu, polega na tym, że algorytm stara się zakumulować trochę niewykorzystanego czasu w "skarbonce", aby móc go potem wykorzystać. W przykładzie podanym na zajęciach, widzieliśmy, że gdyby algorytm wyszukiwania wzorca deponował w skarpecie jedną jednostkę czasu ilekroć wykonuje inkrementację, to mógłby wtedy zapłacić tymi odłożonymi zasobami, za wykonywanie zmniejszania zmiennej w pętli while.

Czasem jednak analiza jest nieco bardziej skomplikowana, bo nie widać na pierwszy rzut oka, z jaką zmienną powiązać stan konta. Przykładowo napisany powyżej w pseudokodzie algorytm budowania tablicy PI, ma zamortyzowany czas działania liniowy względem rozmiaru wzorca, a jednak pokazanie tego wymaga nieco więcej finezji.

Powiedzieliśmy sobie wreszcie, że algorytm ten można poprawić tak, aby dawał gwarancję maksymalnego czasu spędzanego na pojedynczą literkę, czyli "zdeamortyzować" go. To będzie na następnych zajęciach. Wiemy też, że w bibliotece standardowej mamy dostępne strstr, które wyszukuje wzorzec w czasie $ O(n+m) $, jednak niekoniecznie musi używać tego samego algorytmu. O innych liniowych algorytmach, oraz algorytmach które starają się zbliżyć do $ O(n/m) $ opowiemy sobie na następnych zajęciach.

0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com