Zaawansowane algorytmy i struktury danych/Wykład 2

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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ę , która każdemu symbolowi przyporządkowuje niepusty ciąg binarny . Całe słowo zostanie zakodowane na słowo (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 znaleźć binarne kodowanie prefiksowe takie, że ma minimalną długość.


Przykład

Niech . Liczby wystąpień symboli w słowie są:


Optymalnym kodowaniem jest zostaje zakodowane na , ciąg binarny długości . Optymalne drzewo binarne odpowiadające optymalnemu kodowi prefiksowemu jest pokazane na rysunku.

Huffnal.jpg

Rysunek 2:Drzewo Huffmana kodujące optymalnie symbole z wagami odpowiednio . 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:

Długość tekstu 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: .

Niech będzie liczbą różnych symboli w , będzie liczbą wystąpień -tego symbolu. Problem możemy rozwiązać, stosując algorytm dla problemu Optymalne Sklejanie Par dla ciągu . 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 , w element tworzy również dowiązania, staje się lewym synem , natomiast staje się prawym synem.

Algorytm Huffmana (nieformalny opis)


Konfiguracje pośrednie algorytmu to zbiory drzew,

początkowo każdy pojedyńczy element z wagą 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 , a jeśli wagi są posortowane, to w czasie liniowym.

Kodowanie Huffmana słowami -arnymi.

Pozostawiamy jako ćwiczenie podobny problem, ale gdy kodujemy w alfabecie -arnym, mamy teraz symbole . 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 , gdzie 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 . Pozostawiamy jako ćwiczenie znalezienie efektywnego algorytmu dla małych ( lub ). Dla dowolnego (będącego częścią wejścia) i dowolnych wag jest to zbyt trudne, nie znamy algorytmu wielomianowego. Dla ustalonego istnieje algorytm wielomianowy, którego stopień zależy od .

Natomiast pozostawiamy jako ćwiczenie przypadek, gdy jest dowolne, a wszystkie wagi 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ę . 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 .