projektII_opis.pdf

Projekt 2. Kodowanie Huffmana

I. Opis problemu*

Kodowanie Huffmana polega na zast ħ powaniu symboli wyst ħ puj Ģ cych w strumieniu wej Ļ ciowym

specjalnymi sekwencjami bitów stanowi Ģ cych tzw. słowa kodowe. Słowa kodowe dobiera si ħ w taki

sposób, by najkrótsze z nich przyporz Ģ dkowa ę symbolom najcz ħĻ ciej wyst ħ puj Ģ cym w strumieniu

wej Ļ ciowym, a najdłu Ň sze symbolom o najni Ň szych cz ħ stotliwo Ļ ciach wyst Ģ pie ı . Ponadto Ň adna

sekwencja bitów nie mo Ň e by ę przedłu Ň eniem innej, co zapewnia jednoznaczno Ļę pomi ħ dzy

reprezentacj Ģ naturaln Ģ a zbiorem danych przedstawionym w postaci zakodowanej. Dzi ħ ki swej

konstrukcji kody Huffmana znajduj Ģ szerokie zastosowanie w bezstratnej kompresji danych, w

szczególno Ļ ci tam, gdzie wyst ħ puj Ģ znaczne ró Ň nice pomi ħ dzy cz ħ stotliwo Ļ ciami wyst Ģ pie ı

symboli, a słaba korelacja pomi ħ dzy s Ģ siednimi elementami wyklucza u Ň ycie metod słownikowych.

St Ģ d kody Huffmana stosuje si ħ powszechnie w formatach kompresji obrazu i d Ņ wi ħ ku, np. JPEG,

MPEG oraz MP3.

Klasyczny algorytm wyznaczania słów kodowych bazuje na drzewie binarnym. Załó Ň my, Ň e w

strumieniu wej Ļ ciowym wyst ħ puj Ģ 8-bitowe liczby całkowite, tzn. dane typu „ unsigned char” .

Niech przykładowy ci Ģ g symboli do zakodowania przyjmie nast ħ puj Ģ c Ģ posta ę :

aaaabbccaaaaccbbaddaaaaaaabbbbcccaaaaaabbbb

Wówczas:

1. Zliczamy cz ħ stotliwo Ļ ci wyst Ģ pie ı poszczególnych symboli tworz Ģ c tzw. las, w którym

ka Ň de drzewo (tutaj posiadaj Ģ ce tylko jeden w ħ zeł) zawiera jeden symbol oraz wag ħ b ħ d Ģ c Ģ

liczb Ģ wyst Ģ pie ı danego symbolu. Poniewa Ň w naszym przykładzie litera a wyst Ģ piła 22

razy, b 12 razy, c 7 razy oraz d 2 razy, to wspomniany las przyjmie posta ę :

a , 22

b , 12

c ,7

d , 2

2. Nast ħ pnie z lasu utworzonego w punkcie 1 wybieramy dwa drzewa o najni Ň szych wagach i

ł Ģ czymy je, tworz Ģ c nowe drzewo o wadze b ħ d Ģ cej sum Ģ wag drzew składowych. Operacj ħ

t ħ powtarzamy a Ň do uzyskania jednego drzewa. Dla naszego przykładu mamy:

Krok 1.

a , 22

b , 12

c ,7

d , 2

Krok 2.

a , 22

b , 12

c ,7

d , 2

Krok 3.

a , 22

b , 12

c ,7

d , 2

W rezultacie otrzymujemy jedno drzewo, którego li Ļ cie zawieraj Ģ kodowane symbole, tutaj

liczby typu „ unsigned char ”.

3. Nast ħ pnie dla ka Ň dego symbolu wyznaczamy słowo kodowe, b ħ d Ģ ce Ļ cie Ň k Ģ od korzenia do

li Ļ cia zawieraj Ģ cego dany symbol, przy czym przej Ļ ciu w lewo przyporz Ģ dkowujemy bit '0'

a przej Ļ ciu w prawo bit '1'. W naszym przykładzie po przyj ħ ciu tej zasady drzewo kodów

Huffmana przyjmie posta ę :

a , 22

b , 12

c ,7

d , 2

Przechodz Ģ c drzewo od korzenia do ka Ň dego li Ļ cia otrzymamy tablic ħ kodów Huffmana dla

poszczególnych symboli wyst ħ puj Ģ cych w przykładowym ci Ģ gu danych:

Symbol

Kod

110

111

* Opracowano na podstawie [1].

II. Specyfikacja zadania

Pa ı stwa zadanie sprowadza si ħ do wyznaczenia słów kodowych wg. powy Ň szego algorytmu dla

symboli wyst ħ puj Ģ cych w pliku, którego nazw ħ wprowadza u Ň ytkownik programu. Słowa kodowe

nale Ň y zapisa ę do drugiego pliku (tzw. pliku słownika) wskazanego przez u Ň ytkownika, zgodnie z

nast ħ puj Ģ c Ģ zasad Ģ :

1. Najpierw zapisujemy symbol jako liczb ħ typu „ unsigned char ”, tzn. jako liczb ħ całkowit Ģ z

przedziału od 0 do 255 w postaci kodów ASCII poszczególnych cyfr.

2. Nast ħ pnie wstawiamy znak ':'.

3. Dalej podajemy kod Huffmana dla danego symbolu w postaci ci Ģ gu zer i jedynek

zapisanych równie Ň za pomoc Ģ kodów ASCII.

4. Na ko ı cu takiego wpisu wstawiamy znak nowej linii, tzn. liczby 13 i 10.

W naszym przykładzie plik wynikowy z kodami Huffmana wygl Ģ dałby w sposób

nast ħ puj Ģ cy:

97:0

98:10

99:110

100:111

oraz jako liczby szesnastkowe (tak nie trzeba zapisywa ę ):

39 37 3A 30 0D 0A

39 38 3A 31 30 0D 0A

39 39 3A 31 31 30 0D 0A

31 30 30 3A 31 31 31 0D 0A

Oczywi Ļ cie kolejno Ļę wpisów w pliku nie ma znaczenia. Zał Ģ czony program

demonstracyjny „ gen.exe ” słu Ň y do generowania oraz zapisu słów kodowych Huffmana wg.

powy Ň szych ustale ı .

Tutaj ko ı czy si ħ obowi Ģ zkowy dla Pa ı stwa zakres działa ı .

Nast ħ pnie nale Ň ałoby zakodowa ę wej Ļ ciowy plik (plik_we) przy u Ň yciu wcze Ļ niej wyznaczonych

kodów (zamieszczonych w pliku słownika plik_slownika) zapisuj Ģ c do pliku wynikowego

(plik_wy) zamiast symboli wej Ļ ciowych, odpowiadaj Ģ ce im ci Ģ gi bitów, oczywi Ļ cie ju Ň nie jako

kody ASCII. Operacj ħ t ħ wykonuje zał Ģ czony program demonstracyjny „kom.exe”.

Dekodowanie pliku umo Ň liwia program „dek.exe”. Operacj ħ t ħ realizuje si ħ równie Ň w oparciu o

drzewo kodów Huffmana przechodz Ģ c drzewo od korzenia do li Ļ ci wg. Ļ cie Ň ek zapisanych w

zakodowanym pliku. Dzi ħ ki jednoznaczno Ļ ci kodów odtworzenie zbioru danych wej Ļ ciowych jest

mo Ň liwe.

W praktyce nale Ň ałoby oczywi Ļ cie zapami ħ tywa ę słownik w sposób bardziej optymalny ni Ň w

postaci kodów ASCII oraz zamie Ļ ci ę nagłówek w zakodowanym pliku zawieraj Ģ cy długo Ļę

oryginalnego zbioru danych, co uniemo Ň liwi doklejanie dodatkowych znaków na ko ı cu pliku

podczas dekompresji.

Pomimo długiego opisu projekt drugi nie jest projektem bardzo czasochłonnym. Zakłada znajomo Ļę

podstawowych poj ħę zwi Ģ zanych z budow Ģ drzew binarnych, w tym przechodzenia wg. kolejno Ļ ci

preorder, inorder oraz postorder, a tak Ň e umiej ħ tno Ļ ci dynamicznego tworzenia danych. Ze wzgl ħ du

na spó Ņ nione zamieszczenie specyfikacji projektu termin zaliczenia zostanie przesuni ħ ty.

III. Zał Ģ czone programy

Generator kodów Huffmana - gen.exe

Program kompresuj Ģ cy dane - kom.exe

Program dekompresuj Ģ cy - dek.exe

Literatura:

[1] pod redakcj Ģ W. Skarbka, „MULTIMEDIA. Algorytmy i standardy kompresji”, Akademicka

Oficyna Wydawnicza PLJ, Warszawa 1998.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: