Zaawansowane algorytmy i struktury danych/Wykład 2

Zaawansowane algorytmy tekstowe II

W module tym zajmiemy się kodowaniem Huffmana. Zwiazane sa z nimi różne ciekawe problemy tekstowe.

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$.