Zaawansowane algorytmy i struktury danych/Wykład 2

From Studia Informatyczne

Zaawansowane algorytmy tekstowe II

Spis treści


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.

Grafika:Huffnal.jpg

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],\ldots 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,\ldots, 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.