Wykład 1. Liniowe algorytmy tekstowe

 Lista zagadnień, które zostały omówione:

  1. Algorytm KMP. Zauważamy, że do wyszukania wzorca w tekście wystarcza nam wyznaczanie funkcji prefiksowej (najdłuższe właściwe prefikso-sufiksy dla wszystkich prefiksów słowa). Faktycznie, jeżeli to mamy, to liczymy funkcję prefiksową P dla słowa wzorzec#tekst, gdzie # jest specjalnym symbolem spoza alfabetu, i jako końce wystąpień wzorca uznajemy te spośród pozycji tekstu, dla których P[i]=|wzorzec|.
    Samą funkcję prefiksową wyznaczamy na podstawie dwóch (prostych!) lematów.
    Lemat 1: Jeżeli znamy funkcję prefiksową dla słowa s[1..n], to wszystkie prefikso-sufiksy tego słowa to: {n, P[n], P[P[n]], ...} (kończymy wypisywać, jak dojdziemy do zera). Wynika to z faktu, że prefikso-sufiks prefikso-sufiksu s jest również prefikso-sufiksem s.
    Lemat 2: Aby policzyć P[i+1], wystarczy znaleźć taki prefikso-sufiks t słowa s[1..i], który spełnia warunek s[t+1]=s[i+1], czyli taki, który można przedłużyć do prefikso-sufiksu s[1..i+1]. Uwaga: utożsamiamy prefikso-sufiksy słowa z ich długościami.

    Kod wyznaczania funkcji prefiksowej:

    P[1] = 0;
    int t = P[1];
    for (int i = 2; i <= n; i++) {
         // Niezmiennik: t=P[i-1]
         while (t > 0 && s[t + 1] != s[i]) t = P[t]; // poszukiwanie odpowiedniego prefikso-sufiksu
         if (s[t + 1] == s[i]) t++;
         P[i] = t;
    }

    KMP ma liniową złożoność czasową, bo liczba inkrementacji t jest O(n), a liczba obrotów wewnętrznej pętli while jest nie większa od liczby inkrementacji t (każde wykonanie instrukcji t = P[t] zmniejsza t).

  2. Związki między prefikso-sufiksami, okresami a pierwiastkami słowa (pierwiastek słowa to taki jego pełny okres). Prefikso-sufiksom jednoznacznie odpowiadają okresy słowa, a z natury tej odpowiedniości wynika, że najkrótszy okres odpowiada najdłuższemu prefikso-sufiksowi. Wreszcie pokazuje się, że pierwiastkiem pierwotnym słowa (najkrótszym pierwiastkiem) jest albo najkrótszy okres, albo całe słowo, tzn. jeżeli (n-P[n]) | n, to pierwiastek pierwotny ma długość n-P[n], a w przeciwnym przypadku -- n. W dowodzie tego faktu wykorzystuje się Lemat o okresowości: Jeżeli słowo s ma dwa okresy a i b, które spełniają a+b ≤ |s| (a w wersji mocnej Lematu a+b ≤ |s|+nwd(a,b)), to ma też okres długości nwd(a,b). Wreszcie z tego samego lematu wynika, że każdy pierwiastek słowa jest tak naprawdę wielokrotnością pierwiastka pierwotnego.
    To wszystko jest opisane dokładniej w opracowaniu zadania Palindromy z finału XIII Olimpiady Informatycznej (patrz Niebieska książeczka XIII OI). No dobra, może kiedyś wkleję tutaj jakąś parafrazę opisu z tamtej Niebieskiej.
  3. Wyznaczanie najkrótszego szablonu słowa (szablonem słowa s nazywamy takie słowo v, że -- niekoniecznie rozłącznymi -- wystąpieniami słowa v można pokryć wszystkie litery s, np. s=ababa, v=aba). Widać, że szablon jest zawsze prefikso-sufiksem słowa. Dla danego kandydata na szablon można sprawdzić jego szablonowość w czasie liniowym, zapuszczając najpierw KMP, a potem sprawdzając, czy jego wystąpienia rzeczywiście pokrywają s (do tego ostatniego trzeba użyć nieco sprytu). Niestety prefikso-sufiksów słowa może być potencjalnie O(n), więc taki algorytm bezpośredni daje czas O(n2).
    Zaradzić temu pozwala lemat: jeżeli p jest szablonem słowa, zaś q -- prefikso-sufiksem s, to jeżeli p/2 ≤ q ≤ p, to również q jest szablonem s. Wynika to stąd, że przy zachowaniu podanej nierówności, wystąpienia q na początku i na końcu p (oba są prefikso-sufiksami s!) pokrywają całe p, czyli pokrycie słowa s szablonem p można łatwo zamienić na pokrycie s słowem q. Stosując prawo logiczne transpozycji ((p → q) ↔ (~q → ~p)) dla sformułowania lematu mamy więc, że jeżeli q nie jest szablonem i zachodzą nierówności p/2 ≤ q ≤ p, to p także nie jest szablonem. Aby wykorzystać ten fakt, sortujemy wszystkie długości prefikso-sufiksów słowa niemalejąco i w tej kolejności wykonujemy poszukiwanie szablonu wśród nich; na mocy lematu, po nieudanym sprawdzeniu dla q pozwalamy sobie pominąć sprawdzenie dla tych p ≥ q, które są nie większe niż 2*q. Dzięki takim przeskokom wykonamy łącznie O(log(n)) sprawdzeń, co daje algorytm o złożoności czasowej O(n*log(n)).
    Wyznaczanie szablonu można także wykonać w czasie O(n); algorytm ten jest prosty w implementacji, lecz dosyć trudny do zrozumienia, dlatego pozwolimy sobie go pominąć. Opisy obydwu algorytmów można znaleźć w opracowaniu zadania Szablon z II etapu XII Olimpiady Informatycznej (patrz Niebieska książeczka XII OI).
  4. Algorytm Manachera. Mamy słowo s[1..n] i chcemy dla każdej pozycji i ∈ {1,...,n} wyznaczyć liczbę R[i], będącą promieniem największego palindromu parzystego, który ma środek w i. Dokładniej, R[i] to największa liczba całkowita nieujemna, dla której słowo s[i-R[i] .. i+1+R[i]] jest palindromem parzystej długości.
    Algorytm będzie działał mniej więcej tak: najpierw wyliczamy pierwszą z brzegu niewyliczoną wartość funkcji R (jakieś R[i]), a potem próbujemy w czasie stałym wyliczać wartości R[i+k] dla 1 ≤ k ≤ R[i], czyli te, które się mieszczą "pod parasolem" palindromu o promieniu R[i].
    Wykorzystujemy arcymagiczną obserwację: jeżeli k jest takie, jak opisane i R[i-k] ≠ R[i]-k, to R[i+k] = min(R[i-k], R[i]-k). Skąd to się w ogóle bierze? (czyli jak to udowodnić?) Otóż jeżeli R[i-k] < R[i]-k, to to oznacza, że cały palindrom zaczepiony w pozycji i-k siedzi pod daszkiem palindromu zaczepionego w i. Ze względu na palindromowość palindromu R[i], ów palindrom z pozycji i-k przenosi się żywcem na palindrom na pozycji i+k, co pokazuje, że w tym przypadku R[i+k]=R[i-k]. Jeżeli zaś R[i-k] > R[i]-k, to z kolei palindrom R[i-k] wystaje poza daszek palindromu R[i] (o R[i-k]-(R[i]-k) znaków). Ponownie wykorzystując palindromowość palindromu R[i], mamy już z tego, że R[i+k] ≥ R[i]-k. Pytanie: czemu nie może to być większe? Otóż z tego, że palindrom R[i-k] wystaje poza daszek wynika, że pierwsza literka przed daszkiem (czyli L1 = s[i-R[i]-1]) jest taka sama, jak literka L2 = s[i-k+(R[i]-k)+1]. Odbicie symetryczne tej drugiej literki względem środka palindromu R[i] (czyli coś koło L3 = s[i+k-(R[i]-k)-1]) jest jej równe, co wynika z palindromowości "dużego daszka". Ta literka jest z kolei pierwszą literką przed daszkiem długości R[i]-k nad pozycją i+k. Z kolei pierwszą literką za tym daszkiem (a tym samym za całym dużym daszkiem) jest L4 = s[i+1+R[i]+1]. Przypomnijmy co wiemy: L1 = L2 = L3, ale L1 ≠ L4, bo promień palindromu na pozycji i to R[i], ale nie więcej. To pokazuje wreszcie, że L3 ≠ L4, czyli innymi słowy to, że daszka długości R[i]-k z pozycji i+k nie da się rozszerzyć, czyli R[i+k]=R[i]-k. To kończy dowód arcymagicznej obserwacji. Ewidentnie w tym dowodzie brakuje rysunków. Jak się znajdzie jakiś wolontariusz, który pomoże mi to narysować, to już będą;-). Jak nie, to może kiedyś sam je narysuję.
    Jesteśmy już gotowi do zapisania kodu algorytmu Manachera:
    s[0] = '#'; s[n + 1] = '$'; // Strażnicy, żeby nie musieć wypisywać ifów w stylu "czy nie wyszliśmy poza słowo".
    R[0] = 0;
    int i = 1;
    int t = 0; // Zbieżność nazw zmiennych t z tego kodu i kodu KMP jest nieprzypadkowa.
    while (i <= n)
    {
       // Niezmiennik: t ≤ R[i], czyli innymi słowy: musimy jeszcze spróbować poszerzyć
       // palindrom o środku w i, który już mamy.
       // No to poszerzamy:
       while (s[i - t] == s[i + t + 1]) t++;
       R[i] = t;
    
       // Stosujemy obserwację pod daszkiem, dopóki możemy.
       int k = 1;
       while (k <= t && R[i - k] != R[i] - k)
       {
          R[i + k] = min(R[i - k], R[i] - k));
          k++;
       }
       // Skoro wyszliśmy z pętli, to nierówność R[i-k] ≠ R[i]-k z obserwacji nie jest
       // spełniona (albo k > t, ale to jest dużo łatwiejszy przypadek). To oznacza, że
       // daszek nad pozycją i+k jest co najmniej równy R[i]-k (=R[i-k]), ale potencjalnie może
       // być większy. Kwestię ewentualnego powiększenia rozwiąże kolejny przebieg zewnętrznej
       // pętli while, który zacznie od pozycji i+k i będzie próbował powiększać t - czyli zrobi
       // dokładnie to, co trzeba.
       t -= k; t = max(0, t);
       i += k;
    }

    Poprawność algorytmu wynika z arcymagicznej obserwacji i z komentarzy w kodzie. A jaka jest złożoność? Aby odpowiedzieć na to pytanie, można znowu bawić się w zliczanie inkrementacji/dekrementacji zmiennych i oraz t (stąd zbieżność nazw nieprzypadkowa z KMP) -- pozostawiam to Czytelnikowi jako (łatwe) ćwiczenie. Można także zastosować równoważną obserwację: w każdym kroku pierwszej wewnętrznej pętli while przesuwa się prawy koniec aktualnie rozważanego (najbardziej prawego) daszka, a w każdym kroku drugiej wewnętrznej pętli while -- środek tegoż daszka. No a żadne z tych (środek, prawy koniec) nie może wyskoczyć poza słowo. No to już.
    Mniej;-) o algorytmie Manachera można poczytać w książce Banachowski, Diks, Rytter "Algorytmy i struktury danych". Jako świetne ćwiczenie na zrozumienie tego algorytmu polecam Czytelnikowi zapisanie wersji dla palindromów nieparzystych. Jak się kto podda, to może zerknąć na stronę przedmiotu "Złożoność algorytmów na tekstach" -- tam można znaleźć implementacje obu wersji (istnieje też możliwość zintegrowania obu wersji w jedną funkcyjkę z dodatkowym parametrem).

  5. Funkcja PREF. Znowu liczymy fakąś funkcję dla słowa s[1..n]; tym razem nazywa się ona PREF, żeby się łatwiej pomyliło z prefiksową z KMP;-). PREF[i] (dla i ∈ {2,...,n}) definiujemy jako długość najdłuższego wspólnego prefiksu słów s oraz s[i..n]. Algorytm obliczania tej funkcji jest łudząco podobny do algorytmu Manachera, tylko korzystamy w nim z trochę mniej magicznej obserwacji.
    Trochę mniej magiczna obserwacja: Jeżeli 1 ≤ k < PREF[i] oraz PREF[1+k] ≠ PREF[i]-k, to PREF[i+k] = min(PREF[1+k], PREF[i]-k). Uzasadnienie obserwacji opiera się znowu na czymś podobnym do spaceru pod daszkiem, tym razem uformowanym przez PREF[i]. Skoro pierwsze PREF[i] liter słowa s[i..n] zgadza się dokładnie z tyloma pierwszymi literami wyjściowego słowa, to wartość PREF[i+k] (o ile wciąż jest pod daszkiem) można próbować wywnioskować na podstawie PREF[1+k], bowiem pozycja i+k ma się tak do pozycji i, jak pozycja 1+k do pozycji 1. No i znowu jeśli wyrażenia PREF[1+k] i PREF[i]-k są różne, to można dokładnie wyznaczyć wartość PREF[i+k] jako minimum z tych dwóch. Faktycznie, jeżeli PREF[1+k] jest mniejszym z tych wyrażeń, to wiemy, że dokładnie tyle samo liter prefiksowych pasuje od pozycji i+k i ani jedna więcej (bo inaczej PREF[1+k] musiałoby być większe). Jeżeli zaś mniejsze jest PREF[i]-k, to to oznacza, że budując wspólny prefiks, możemy dojść od pozycji i+k aż do końca daszka wyznaczonego przez PREF[i]. Nie możemy iść dalej, bo s[1+PREF[i]] ≠ s[i+PREF[i]] (z definicji PREF[i]), a to właśnie literka s[1+PREF[i]] byłaby potrzebna do przedłużenia wartości PREF[i+k] (bo ta właśnie literka pozwoliła na przedłużenie odpowiadającej jej wartości PREF[1+k]). Podane uzadanienie jest na tyle podobne do tego z algorytmu Manachera, że nie będziemy się tutaj więcej rozpisywać.
    Wyposażeni w obserwację możemy już całkiem łatwo wyznaczyć funkcję PREF, ponownie stosując metodę: wylicz PREF[i], idź ile się da, wykorzystując obserwację i jeszcze raz od początku. Kod tego algorytmu jest łudząco podobny do kodu algorytmu Manachera, więc zachęcam Czytelnika do samodzielnego jego stworzenia. No dobra, jeżeli Czytelnik jest bardzo leniwy, to rozwiązanie jest tu.
    Pozostaje jedno drobne pytanie: po co w ogóle komu ta funkcja PREF? Ja znam tylko jedno "zastosowanie" takie, w którym funkcja prefiksowa nie działa równie dobrze, a mianowicie w rozwiązaniu zadania Prawie równoważne słowa z Potyczek Algorytmicznych 2007 (od tego momentu tekstu zakładamy znajomość treści tego zadania przez Czytelnika). Sprawdzenie, czy dwa słowa u i v są równoważne cyklicznie, można łatwo wykonać za pomocą KMP: wyszukujemy słowo u w słowie vv, czyli liczymy funkcję prefiksową dla słowa u#vv. Aby rozwiązać problem prawie cyklicznej równoważności, spróbujmy się posłużyć takim samym słowem, czyli u#vv. Otóż dla każdej pary pozycji (i,i+n-1), z której obie mieszczą się wewnątrz vv (dla i ∈ {1,...,n}) chcemy się dowiedzieć, czy długość pi najdłuższego prefiksu słowa u, rozpoczynającego się od pozycji i w słowie vv oraz długość si+n-1 najdłuższego sufiksu słowa u, który się kończy na pozycji i+n-1 w vv, sumują się do n-1, co oznacza zgodność odpowiedniej rotacji cyklicznej v z u poza dokładnie jedną literką, czyli to, o co nam chodzi. Wreszcie pi to dokładnie PREF[i+n+1] dla słowa u#vv, zaś si+n-1 można wyznaczyć, licząc funkcję PREF dla słowa uR#vRvR (gdzie uR to po prostu odwrócone słowo u).
    Widzimy więc, że posiadanie w arsenale funkcji PREF znakomicie upraszcza rozwiązanie zadania Prawie równoważne słowa. A zatem zachęta dla Czytelników, żeby zaimplementowali tę funkcję i, aby ją dobrze przetestować, rozwiązali wspomniane zadanie.
  6. Na wykładzie miałem jeszcze zamiar wspomnieć o związkach algorytmów tekstowych i problemów geometrycznych, lecz ze względów czasowych mi się nie udało. Tutaj opiszę to w skrócie. Sprawdzenie, czy dany zbiór punktów można przekształcić dokładnie na drugi za pomocą izometrii i jednokładności możemy wykonać tak, że każdy z tych zbiorów zaczepiamy w jego środku ciężkości, przeskalowujemy odległości punktów od środka tak, żeby największe z nich sobie odpowiadały, a następnie badamy równoważność cykliczną napisów postaci (długość odcinka, rozmiar kąta, odcinek, kąt, ...), gdzie odcinki łączą kolejne punkty ze zbioru ze środkiem ciężkości, a kąty są zawarte pomiędzy kolejnymi takimi odcinkami. Czyli rozwiązanie wykorzystuje algorytm KMP.
    Z kolei wyznaczenie osi symetrii wielokąta wykonujemy, sklejając kolejne współliniowe odcinki na obwodzie, wstawiając bonusowe wierzchołki wielokąta w środki wszystkich boków, a następnie poszukując długich palindromów w słowie: (kąt, bok, kąt, bok, ...) -- każdy taki palindrom o odpowiedniej długości odpowiada przekrojeniu wielokąta osią symetrii. No to co? No to pomaga nam algorytm Manachera!
    To był opis w telegraficznym skrócie; dokładniejsze opisy (wraz z dowodami) można znaleźć w opracowaniu zadania Punkty z I etapu XII Olimpiady Informatycznej w Niebieskiej książeczce XII OI oraz w opracowaniu zadania Osie symetrii z I etapu XIV Olimpiady Informatycznej w Niebieskiej książeczce XIV OI.

Wszelkie uwagi odnośnie tego wykładu, w tym niniejszego jego opisu, w tym wszelkie poprawki błędów, jakich niewątpliwie jest w nim mnóstwo, prosimy kierować do Jakuba Radoszewskiego.