Kodowanie Huffmana PDF

Preview

Summary

Kodowanie Huffmana...

Description

POLITECHNIKA KRAKOWSKA im. T.Kościuszki Wydział Inżynierii Elektrycznej i Komputerowej

STUDIA STACJONARNE

SPRAWOZDANIE METODY PROGRAMOWANIA

Krzysztof Czyrkiewicz Kodowanie Huffmana Prowadzący laboratoria dr hab. inż. Zbigniew Kokosiński

Kraków, rok akad. 2018/2019 Dnia 10.05.2019, godz. 11:00 – 12:30

2

1. Temat Kodowanie Huffmana.

2. Analiza 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ć:

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:

3

Krok 1.

Krok 2.

Krok 3.

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 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ć:

4

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:

3. Projektowanie Dzięki analizie tematu można stworzyć algorytm realizujący powyższe założenia. Algorytm powinien działać w następujący sposób: 1. Określ prawdopodobieństwo (lub częstość występowania) dla każdego symbolu . 2. Utwórz listę drzew binarnych, które w węzłach przechowują pary: symbol, prawdopodobieństwo. Na początku drzewa składają się wyłącznie z korzenia. 3. Dopóki na liście jest więcej niż jedno drzewo, powtarzaj: 1. Usuń z listy dwa drzewa o najmniejszym prawdopodobieństwie zapisanym w korzeniu. 2. Wstaw nowe drzewo, w którego korzeniu jest suma prawdopodobieństw usuniętych drzew, natomiast one same stają się jego lewym i prawym poddrzewem. Korzeń drzewa nie przechowuje symbolu. Drzewo, które pozostanie na liście, jest nazywane drzewem Huffmana.

5

Na podstawie drzewa Huffmana tworzone są słowa kodowe; algorytm jest następujący: 1. Każdej lewej krawędzi drzewa przypisz 0, prawej 1 (można oczywiście odwrotnie). 2. Przechodź w głąb drzewa od korzenia do każdego liścia (symbolu): 1. Jeśli skręcasz w prawo, dopisz do kodu bit o wartości 1. 2. Jeśli skręcasz w lewo, dopisz do kodu bit o wartości 0. Długość słowa kodowego jest równa głębokości symbolu w drzewie, wartość binarna zależy od jego położenia w drzewie.

4. Specyfikacja zewnętrzna Po uruchomieniu, program informuje o jego przeznaczeniu oraz prosi użytkownika o wybranie opcji poboru danych. Należy wprowadzić jeden z dwóch numerów odpowiedzi [1 (wprowadzanie ręczne) lub 2 (z pliku Huffman_data.txt)] oraz zatwierdzić wprowadzony numer przyciskiem Enter. 

Przy wyborze pierwszej opcji użytkownik zostanie poproszony o wpisanie tekstu, który ma zostać zakodowany metodą Huffmana.

Po wykonaniu powyższych czynności użytkownikowi ukaże się zakodowany tekst oraz słowa kodowe każdego znaku. Na koniec użytkownik zostanie zapytany czy chce wprowadzić inne dane lub czy chce wyjść z programu. Należy wprowadzić jeden z dwóch numerów odpowiedzi [1 (wprowadzenie danych) lub 2 (wyjście z programu)] oraz zatwierdzić wprowadzony numer przyciskiem Enter.

5. Specyfikacja wewnętrzna Program składa się z dwóch struktur i czterech funkcji, których działanie zostało opisane poniżej: - Node Struktura węzła drzewa. Zawiera znak, jego częstotliwość występowania oraz informacje czy jest węzłem prawym czy lewym. - comp Struktura sortująca węzły od najmniejszej częstotliwości występowania do największej oraz przypisująca priorytet. Największy priorytet ma węzeł z najmniejszą częstotliwością występowania.

6

- getNode Funkcja tworząca nowe węzły drzewa. - encode Funkcja zapisująca słowa kodowe każdego znaku dzięki przeszukiwaniu drzewa Huffmana. - buildHuffmanTree Funkcja tworząca drzewo Huffmana. Stwórz węzły drzewa dla każdego znaku i dodaj je do kolejki pierwszeństwa (funkcja comp) Wykonuj poniższe polecenia dopóki w kolejce jest więcej niż 1 węzeł: Usuń z kolejki dwa węzły o największym priorytecie (najniższej częstotliwości). Stwórz nowy węzeł z dwóch poprzednio usuniętych węzłów (dzieci) oraz sumy ich częstotliwości (rodzic). Dodaj nowo powstały węzeł do kolejki.

- main Funkcja odpowiadająca za tekstową reprezentację menu programu oraz odczyt z pliku Huffman_data.txt.

7

6. Testowanie Poniżej znajdują się wyniki testów programu: - Test 1: Huffman coding. [1] Enter data by hand. [2] Take data from Huffman_data.txt. Chosen answer number = 2

Text from Huffman_data.txt: In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression.

Characters in Huffman code :

Encoded text :

Encoded text was save in a Huffman_result.txt file.

8

- Test 2: Huffman coding. [1] Enter data by hand. [2] Take data from Huffman_data.txt. Chosen answer number = 1

Enter text to encrypt: Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.

Characters in Huffman code :

Encoded text :

Encoded text was save in a Huffman_result.txt file.

9

- Test 3: Huffman coding. [1] Enter data by hand. [2] Take data from Huffman_data.txt. Chosen answer number = 1

Enter text to encrypt: Politechnika Krakowska

Characters in Huffman code :

Encoded text :

Encoded text was save in a Huffman_result.txt file.

Program testowany był na komputerze ASUS F555LN-XO214H z systemem operacyjnym Windows 10 w środowisku Visual Studio 2019.

7. Wnioski Na podstawie analizy wyników zwracanych przez program można stwierdzić, iż program koduje podany przez użytkownika tekst zgodnie z metodą kodowania Huffmana.

10

8. Literatura 1. W. Lipski, Kombinatoryka dla programistów, Warszawa, Wydawnictwo NaukowoTechniczne, 1989, ISBN 83-204-1023-1 (http://students.mimuw.edu.pl/~mp347204/inf/1_rok/II_sem/MD/Lipski%20Witold%20%20Kombinatoryka%20dla%20programist%C3%B3w.pdf) 2. W. Muła, Statyczne kodowanie Huffmana (http://0x80.pl/articles/huffman.html) 3. Kodownie Huffmana, Wikipedia.pl (https://pl.wikipedia.org/wiki/Kodowanie_Huffmana) 4. 5. Projekt 2. Kodowanie Huffmana, Ics.p.lodz.pl (http://ics.p.lodz.pl/~dpuchala/PodstInfII/projektII_opis.pdf)

11...