Zaawansowane algorytmy i struktury danych/Wykład 2

Zaawansowane algorytmy tekstowe II

Poprzednie algorytmy dokonywały na tekstach wejściowych jedynie operacji sprawdzania symboli na równość. Załóżmy teraz, że alfabet jest liniowo uporządkowany. Pokażemy, że porównywanie symboli w sensie porządku liniowego można istotnie wykorzystać w algorytmach tekstowych. Porządek liniowy na symbolach implikuje {\em porządek leksykograficzny} na słowach, na przykład:

$ab<ababab<abb<abbaa<abbaaaaaaaaaaa<abbaaaaaab$

String-matching w pamięci stałej dla specjalnych wzorów

Oznaczmy przez $MaxSuf(w)$ maksymalny leksykograficznie sufiks słowa $w$. Słowo $x$ nazwiemy specjalnym, gdy $MaxSuf(x)=x$.

Przykład

'bajtocja' nie jest słowem specjalnym, ale rotacja tego słowa 'tocjabaj' jest.

Dlaczego słowa o tej własności są interesujące? Większość szybkich algorytmów szukania podsłów korzysta z okresów $p$ prefiksów słowa. Liczenie tych okresów w ogólnym przypadku jest wąskim gardłem w projekcie algorytmu. Natomiast dla słow specjalnych liczenie okresów jest trywialne.

Jeśli $x$ jest specjalny, to okres każdego prefiksu słowa $x$ można policzyć następującym naiwnym algorytmem:

Algorytm Funkcja Naiwne-Liczenie-Okresu (j)

---

$period:=1$;
for $i:=2$ to $j$ do
   if $x[i]\ne x[i-period]$ then $period:=i$;
return $period$;

Przykład

Funkcja Naiwne-Liczenie-Okresu daje zły wynik dla tekstów które nie są specjalne, na przykład załóżmy że $x=(aba{)}^{6}a=abaabaabaabaabaabaa$.} Wtedy kolejne wartości okresów dla pozycji $j=1,2,..$

są:

a	b	a	a	b	a	a	b	a	a	b	a	a	b	a	a	b	a	a
1	2	2	4	5	5	7	8	8	10	11	11	13	14	14	16	17	17	19

Zatem Naiwne-Liczenie-Okresu$(19)=19$, dla $x=(aba{)}^{6}a$, wynik całkowicie niepoprawny. Poprawność algorytmu jest wyjaśniona na rysunku. Korzystamy z prostej własności, że prefiks specjalnego słowa jest też specjalny.

Rysunek 1: Załóżmy, że w algorytmie Naiwne-Liczenie-Okresu $x[i-period(i-1)]\ne x[i]$. Niech $a=x[i]$, $b=x[i-period]$. Ponieważ $uz$ jest prefiksem słowa specjalnego $x$, zatem $a<b$. Gdyby $period(i)<i$ to wtedy, ze względu na dwie okresowości, $zb$ jest właściwym podsłowem słowa $x[1..i-1]$ oraz $zb>x$. Zaprzecza to założeniu, że $x$ jest specjalne. Zatem $period(i)=i$.

Opiszemy teraz program szukania wzorca $x$ w slowie $y$i, zakładając że $x$ jest specjalne. Program wczytuje dwa teksty, pierwszy z nich jest specjalny: $x$ pamiętamy w tablicy $x[0..m-1]$, $y$ w tablicy $y[0..n-1]$. Program wypisuje wszystkie wystapienia $x$ w $y$, tzn. wszystkie takie pozycje $i$, że $y[i\dots i+m-1]=x$. Zapisujemy program w języku C++.

Algorytm Specjalny-String-Matching

---

 #include <iostream.h>
 #include string.h
 int $i=0$, $j=0$, $p=1$;
 void przesun();
 main() {
 char[] x,y; cin>>x>>y; m$=$strlen(x); n$=$strlen(y);
 while (i $<=$ n-m-1)
    { if (j$==$m) {cout<<i<<endl; przesun();};
     else if (x[j]$==$y[i+j]) {j$=$j+1; if (j$==$1) $||$ (x[j-1]$!=$x[j-1-p]) p$=$j;};
     else przesun(); } }

void przesun()
   { if (j-1<2p) {i$=$i+p; j$=$0;} else {j$=$j-p; i$=$i+p;} }

Program jest wstępem do programu szukającego dowolne podsłowo, niekoniecznie o własności bycia specjalnym. Podstawowym niezmiennikiem w programie przed każdym wykonaniem i po każdym zakończeniu pętli while jest: (A)\ $x[0\dots j-1]=y[i\dots i+j-1]$, (B)\ Program wypisał wszystkie wcześniejsze wystąpienia $i^{\prime }<i$, (C)\ $p$ jest okresem slowa $x[0\dots j-1]$

Algorytm działa w czasie liniowym. Można to udowodnić obserwując zmiany wartości $2i+j$. Zauważmy, że wartość ta nie zmniejsza się, a w wypadku pozytywnego testu $x[j)==y[i+j]$ zwiększa się co najmniej o 1. Jednocześnie $2i+j\le 3n$.

String-matching w pamięci stałej dla dowolnych wzorców

Algorytym Specjalny-String-Matching można łatwo zmodyfikować tak, aby znajdował on wystąpienia dowolnego słowa (niekoniecznie specjalnego) w czasie liniowym i stałej pamięci. Niech $x=uv$, gdzie $v$ jest leksykograficzne maksymalnym sufiksem $x$. Oznaczmy $r=|u|$. Technicznie informacja o rozkładzie $uv$ sprowadza się do pamiętania $r$.

Własność rozkładu. Niech $x=uv$ będzie rozkładem jak wyżej opisany. Wtedy słowo $v$ występuje tylko raz w słowie $uv$. Jeśli $i^{\prime }<i$ są początkami wystąpień $v$ oraz $i-i^{\prime }<r$, to na pozycji $i-1$ nie kończy się wystąpienie $u$.

Z powyższego faktu wynika stosunkowo prosty algorytm szukania $x$ w czasie liniowym i pamięci stałej. Algorytm ten jest modyfikacją algorytmu Specjalny-String-Matching, w którym rolę $x$ pełni $v$.

Algorytm String-matching w pamięci stałej

---

Niech $v$ będzie leksykograficznie maksymalnym sufiksem $x$;

Liczymy algorytmem Specjalny-String-Matching kolejne wystąpienia $v$ w $y$;

Dla każdego wystąpienia $i$ niech $i^{\prime }$ będzie wystąpieniem poprzednim;

jeśli $i-i^{\prime }\ge |v|$, sprawdź czy $u$ występuje na lewo od pozycji $i$;

(sprawdzanie to wykonujemy w sposób naiwny)

jeśli występuje, wypisz kolejne wystąpienie całego wzorca $x$.

Pozostawiamy bardziej precyzyjny zapis algorytmu jako ćwiczenie.

W ten sposób pokazaliśmy, że problem szukania słowa $x$ w słowie $y$ można rozwiązać w czasie liniowym i pamięci (dodatkowej) stałej, jeśli znamy początkową pozycję $r$ leksykograficznie maksymalnego sufiksu $v$ słowa $x$.

Liczenie maksymalnego sufiksu w pamięci stałej

W algorytmie szukania wzorca w pamięci stałej potrzebna jest pozycja $r$, od której zaczyna się maksymalny sufiks. Pokażemy teraz, jak ją znajdować w czasie liniowym i w pamięci stałej. Kluczem do tego jest liczenie czegoś więcej: dla każdego prefiksu liczymy maksymalny sufiks, jak również dodatkowo jego okres. To właśnie liczenie okresu daje efektywność, chociaż na końcu ten okres nie jest nam potrzebny. Przekształcimy najpierw algorytm Naiwne-Liczenie-Okresu na algorytm liczący długość najdłuższego specjalnego prefiksu włącznie z jego okresem.

{algorytm| funkcja Najdłuższy-Specjalny-Prefiks(x)|fun_najdl_spec_pref| $period:=1$;
for $i:=2$ to $|x|$ do
   if $x[i]<x[i-period]$ \textbf{then} $period:=i$
   'else if $x[i]>x[i-period]$ then
      return $(i-1,period)$;
return $(|x|,period)$; }}

Skorzystamy z algorytmu Najdłuższy-Specjalny-Prefiks. Funkcja Maksymalny-Sufiks liczy początkową pozycję i okres maksymalnego sufiksu.

Algorytm funkcja Maksymalny-Sufiks(x)

---

$j:=1$;
repeat
   $(i,period):=$ Najdłuższy-Specjalny-Prefiks$(x[j..n])$;
   if $i=n$ then return $(j,period)$
   else $j:=j+i-(imodperiod)$;
forever

Możemy przepisać algorytm Maksymalny-Sufiks tak, aby nie wywoływał on funkcji Najdłuższy-Specjalny-Prefiks, wpisując tę funkcję do algorytmu. Arytmetyczna funkcja $mod$ może być usunięta i zastąpiona przez operacje dodawania i odejmowania bez zmiany asymptotycznej złożoności.

Algorytm Maksymalny-Sufiks wykonuje co najwyżej $2.|x|$ porównań symboli. Uzasadnienie pozostawiamy jako ćwiczenie.

Algorytm funkcja} Maksymalny-Sufiks(x)

---

$s:=1$; $i:=2$; $p:=1$;
while ($i\le n$) do
   $r:=(i-s)modp$;
   if ($x[i]=x[s+r])$ then $i:=i+1$
   else if ($x[i]<x[s+r])$ then begin       $i:=i+1$; $p:=i-s$;    else       $s:=i-r$; $i:=s+1$; $p:=1$;
return $s$;

Kodowanie prefiksowe: drzewa i kody Huffmana

Zbiór słów jest prefiksowy, gdy żadne słowo nie jest prefiksem drugiego. Taki zbiór słów odpowiada drzewu, którego ścieżki etykietowane są symbolami. W przypadku binarnym możemy przyjąć, że krawędź w lewo jest etykietowana zerem, a w prawo jedynką. Przez kodowanie rozumiemy funkcję $h$, która każdemu symbolowi $s$ przyporządkowuje niepusty ciąg binarny $h(s)$. Całe słowo $x$ zostanie zakodowane na słowo $h(x)$ (każda litera jest zakodowana niezależnie i kody są skonkatenowane). Kod jest prefiksowy gdy zbiór kodów symboli jest prefiksowy. Rozważamy następujący problem:

Optymalne kodowanie prefiksowe

Dla danego słowa $x$ znaleźć binarne kodowanie prefiksowe takie, że $h(x)$ ma minimalną długość.

Przykład

Niech $x=abracadabra$. Liczby wystąpień symboli w słowie $x$ są:

$w_a=5,w_b=2,w_c=1,w_d=1,w_r=2.$

Optymalnym kodowaniem jest $h(a)=0,h(b)=10,h(c)=1100,h(d)=1101,h(r)=111.$ $abracadabra$ zostaje zakodowane na $01011101100011010101110$, ciąg binarny długości $23$. Optymalne drzewo binarne odpowiadające optymalnemu kodowi prefiksowemu jest pokazane na rysunku.

Rysunek 2:Drzewo Huffmana kodujące optymalnie symbole $a,b,c,d,r$ z wagami odpowiednio $S=(5,2,1,1,2)$. Liczby w wewnętrznych węzłach są sumą wag w liściach odpowiadającego poddrzewa. Koszt całkowity kodowania jest ważoną sumą długości ścieżek do liści, jest również sumą wartości w węzłach wewnętrznych: $2+4+6+11=23.$

Długość tekstu $h(x)$ jest równa ważonej sumie długości ścieżek, ważonej w tym sensie, że długość ścieżki do danego liścia jest przemnożona przez wagę tego liścia. W przykładzie jest to suma: $5*1+2*2+1*4+1*4+2*3=23$.

Niech $n$ będzie liczbą różnych symboli w $x$, $w[i]$ będzie liczbą wystąpień $i$-tego symbolu. Problem możemy rozwiązać, stosując algorytm dla problemu Optymalne Sklejanie Par dla ciągu $w[1],w[2],\dots w[n])$. Musimy algorytm zmodyfikować tak, aby nie tylko sklejał pary, ale również tworzył lokalnie drzewo. Inaczej mówiąc, algorytm w momencie sklejania elementów $a$, $b$ w element $c$ tworzy również dowiązania, $a$ staje się lewym synem $c$, natomiast $b$ staje się prawym synem.

Algorytm Huffmana (nieformalny opis)

---

Konfiguracje pośrednie algorytmu to zbiory drzew,

początkowo każdy pojedyńczy element $i$ z wagą $w[i]$ jest pojedyńczym drzewem.

Korzeń każdego drzewa reprezentuje sklejenie jego wszystkich liści.

Za każdym razem sklejamy dwa korzenie drzew o minimalnej wadze.

Drzewo, które algorytm generuje, nazywamy drzewem Huffmana.

Pozostawiamy jako ćwiczenie przerobienie algorytmu Optymalne-Sklejanie-Par na algorytm liczenia kodów i drzew Huffmana.

Z analizy algorytmu Optymalne Sklejanie Par wynika, że problem optymalnych binarnych kodów prefiksowych można rozwiązać w czasie $O(n\log n)$, a jeśli wagi $w[i]$ są posortowane, to w czasie liniowym.

Kodowanie Huffmana słowami $k$-arnymi.

Pozostawiamy jako ćwiczenie podobny problem, ale gdy kodujemy w alfabecie $k$-arnym, mamy teraz symbole $0,1,\dots ,k-1$. W algorytmie jednorazowo możemy sklejać więcej niż dwa elementy.

Kodowanie prefiksowe z symbolami kodowymi nierównej długości

Problem robi się skomplikowany, gdy długość symbolu 0 jest 1, a długość symbolu 1 jest $c$, gdzie $c$ jest pewną stałą (jest to problem tzw. lopsided trees). Inaczej mówiąc, szukamy takiego optymalnego drzewa, w którym ważona suma ścieżek jest minimalna, ale długość krawędzi na lewo wynosi 1, a długość krawędzi na prawo wynosi $c$. Pozostawiamy jako ćwiczenie znalezienie efektywnego algorytmu dla małych $c$ ($c=2$ lub $c=3$). Dla dowolnego $c$ (będącego częścią wejścia) i dowolnych wag jest to zbyt trudne, nie znamy algorytmu wielomianowego. Dla ustalonego $c$ istnieje algorytm wielomianowy, którego stopień zależy od $c$. Natomiast pozostawiamy jako ćwiczenie przypadek, gdy $c$ jest dowolne, ale wszystkie wagi $w[i]$ są równe.

Kodowanie prefiksowe z kodami o ograniczonej długości

Innym ciekawym problemem jest też skonstruowanie optymalnego kodu prefiksowego, w którym wszystkie słowa kodowe są ograniczone przez pewną zadaną liczbę $L$. Inaczej mówiąc, ograniczamy z góry wysokość drzewa Huffmana. Istnieją wtedy algorytmy wielomianowe dla tego problemu, stopień wielomianu jest niezależny od $L$.