Zaawansowane algorytmy i struktury danych/Wykład 2

Zaawansowane algorytmy tekstowe II

W module tym zajmiemy się przedw wszystkim dwoma niezależnymi problemami: ‘’string-matching’’ w czasie liniowym i pamięci stałej, oraz kodowaniem Huffmana. Zwiazane sa z nimi róne inne ciekawe problemy tekstowe.

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

Załóżmy, ż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$

Oznaczmy przez $MaxSuf(w)$ leksykograficznie maksymalny 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$ daje wynik całkowicie niepoprawny. Poprawność algorytmu jest wyjaśniona na rysunku. Korzystamy z następującej prostej własności:

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 specjalne. 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 jego 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])$. Algorytm ten był przedsatwiony na wykładach z ASD. 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, a wszystkie wagi $w[i]$ są równe. Istniej wtedy algorytm wielomianowy.

Kodowanie prefiksowe z kodami o ograniczonej długości

Innym ciekawym problemem jest 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. Zakładamy teraz, że wagi krawędzi są takie same. Istnieją algorytmy wielomianowe dla tego problemu, w których stopień wielomianu jest niezależny od $L$.