WOJSKOWA AKADEMIA TECHNICZNA

LABORATORIUM

TEORIA INFORMACJI I KODOWANIA

SPRAWOZDANIE

Z

PRACY LABORATORYJNEJ

Temat:	Program realizujący kompresję oraz dekompresję pliku metodą Huffmana

1. Treść zadnia

Napisać program kompresujący oraz dekompresujący plik metodą Huffmana.

2. Tabela wybranych częstości występowania znaków*

Symbol	Częstość	Binarnie
[spacja]	0.239220
e	0.086938
B	0.000614
^	0.000005

* Tabela ukazuje wybrane częstości występowania znaków w pliku „rfc.txt”.

3. Wyznaczanie średniej długości kodu

Teoretyczną średnią długość kodu jesteśmy w stanie wyznaczyć korzystając z ogólnie znanego wzoru:

gdzie:

H(S) - średnia długość kodu

p_i - prawdopodobieństwo wystąpienia danego znaku

Natomiast wartość rzeczywistą możemy uzyskać znając rozmiar danego pliku nieskompresowanego jak i skompresowanego. Dzielimy wtedy liczbę bitów pliku skompresowanego przez liczbę bajtów (w tym wypadku znaków) plik nieskompresowanego. Dokładny rozmiar obu plików możemy poznać poprzez np. program Total Commander.

Stan pliku	Bajtów	Bitów
skompresowany	374 112	2992896
nieskompresowany	649 767	5198136

Teoretyczna średnia długość kodu wynosi: 4,45

Rzeczywista średnia długość kodu wynosi: 4,61

4.1 Metoda kompresji

Na początku zakładamy, że będziemy pobierać znaki z pliku, aż nie napotkamy końca pliku przeznaczonego do kompresji:

while (!feof(odczytywany_plik)){

Następnie potrzebujemy dodatkowej zmiennej, która to będzie naszym licznikiem, który pomoże znaleźć odpowiedni znak w tablicy kodowej

licznik=0;

Teraz czas na pobranie znaku. Znaki pobieramy pojedynczo

fread(&litera,sizeof(unsigned char),1,odczytywany_plik);

Poprzez następną funkcje while wyszukujemy w tablicy kodowej znak odpowiadający dopiero co wczytanej przez nas litery

while (litera!=tablicakodowa[licznik].znak)

licznik++;

Teraz program musi sprawdzić warunek czy w paczce pozostała odpowiednia ilość miejsca na przyjęcie nowego znaku. Na początku omówimy przypadek bezproblemowy, w którym jest wystarczająca ilość miejsca na zapisanie w niej następnego znaku

if (pozostalo>=tablicakodowa[licznik].dlugosckodu){

Zmiennej bufor przypisujemy kod tablicy kodowej pobranego znaku, a następnie przesuwamy pozostałe wolne miejsca w buforze w lewo, o ilość jaka pozostała wolna w buforze pomniejszona o długość kodu znaku, który przed chwilą dodaliśmy. Teraz pozostaje nam tylko wpisać zawartość bufora do paczki oraz zmodyfikować zmienną odpowiadającą ilości bitów jaką można jeszcze dodać do niej.

bufor=tablicakodowa[licznik].kod;

bufor<<=pozostalo-tablicakodowa[licznik].dlugosckodu;

paczka|=bufor;

pozostalo-=tablicakodowa[licznik].dlugosckodu;

Sprawa kompresji trochę się komplikuje w przypadku, w którym długość kodu reprezentującego pobrany znak przekracza ilości wolnego miejsca w paczce.

}else{

Na początku tak samo jak w mniej problemowym przypadku zmiennej bufor przypisujemy kod tablicy kodowej pobranego znaku, ale tą zmienną przesuwamy w prawo o długość kodu pomniejszoną o pozostałe miejsca w paczce. W ten oto sposób możemy wpisać zawartość bufora do paczki, a następnie wysłać ją już do pliku wyjściowego programu. Następnie oczywiście musimy wyczyścić paczkę, a bufor przesunąć tym razem w lewo o 32 miejsca pamiętając, że zostały jakieś zera i jedynki (przecież nie wszystko zostało wysłane w poprzedniej paczce). Następnie ponownie wpisujemy nową zawartość bufora do wyczyszczonej wcześniej przez nas paczki oraz modyfikujemy zmienną odpowiadającą ilości bitów jaką można jeszcze dodać do nowopowstałej paczki.

bufor=tablicakodowa[licznik].kod;

bufor>>=tablicakodowa[licznik].dlugosckodu-pozostalo;

paczka|=bufor;

fwrite(&paczka,sizeof(unsigned int),1,zapisywany_plik);

paczka=0;

bufor=tablicakodowa[licznik].kod;

bufor<<=32-(tablicakodowa[licznik].dlugosckodu-pozostalo);

paczka|=bufor;

pozostalo=32-(tablicakodowa[licznik].dlugosckodu-pozostalo);

}

Na koniec wypadałoby sprawdzić czy paczka nie jest po obu operacjach zapełniona. Jeżeli jest to przesyłamy ja do pliku wyjściowego, zerujemy paczkę za pomocą różnicy bitowej, oraz pokazujemy ze bufor jest pusty nadając zmiennej pozostalo maksymalną wartość wynosząca 32.

if (pozostalo==0){

fwrite(&paczka,sizeof(unsigned int),1,zapisywany_plik);

paczka^=paczka;

pozostalo=32;

}

}

4.2 Metoda dekompresji

Cała funkcja dekompresji polega na umiejętnym posługiwaniem się buforami na które jesteśmy tutaj skazani ze względu na to, że nie jesteśmy w stanie pobierać dowolnej długości ciągu z naszego pliku. Drugi bufor służy nam w takim razie do buforowania tego pierwszego.

Na początku przypisujemy obu buforom początek pliku, a następnie ustalamy, że funkcja trwa do momentu kiedy pierwszy bufor nie będzie zawierał już ciągu z pliku

fread(&bufor,sizeof(unsigned int),1,odczytywany_plik);

fread(&bufor_bufora,sizeof(unsigned int),1,odczytywany_plik);

while(bufor){

Także tutaj potrzebujemy licznika, który to znowu pomoże nam posługiwać się strukturą jaką jest tablica kodowa.

licznik=0;

Paczce przypisujemy zawartość bufora, a następnie przesuwamy ją w prawo o maksymalną długość pomniejszoną o długość kodu pierwszego znaku z tablicy

paczka=bufor;

paczka>>=32-tablicakodowa[licznik].dlugosckodu;

Ta pętla while próbuje rozpoznać pierwsze znaki ciągu. Jeżeli pierwszy znak w tablicy znaków nie pasuje to sprawdza następny, przy okazji poprzez przesuwanie pamiętając o dopasowaniu długości kodu (kod może składać się z 2 znaków jak np. spacja albo z wielu jak jest to rzadziej spotykana zakodowana litera)

while (paczka!=tablicakodowa[licznik].kod){

licznik++;

paczka=bufor;

paczka>>=32-tablicakodowa[licznik].dlugosckodu;

}

Następnie kiedy mamy już pewność, że znaleźliśmy ciąg odpowiadający konkretnemu znakowi to zapisujemy daną literkę w pliku wyjściowym, a bufor przesuwamy tak aby zlikwidować część ciągu, która przed chwilą została zamienioną w znak.

fwrite(&tablicakodowa[licznik].znak,sizeof(unsigned char),1,zapisywany_plik);

bufor<<=tablicakodowa[licznik].dlugosckodu;

Teraz wypada sprawdzić czy została odpowiednia ilość miejsca do dalszego rozpoznawania znaków. Jeżeli taki warunek nie zostaje spełniony korzystamy z pomocy ostatniego bufora. jego zawartość staje się na chwilę zawartością paczki, ale ze względu na to aby nie stracić żadnego zera bądź jedynki ciągu przesuwamy zawartość paczki.

if (pozostalo<tablicakodowa[licznik].dlugosckodu){

paczka=bufor_bufora;

paczka>>=32-pozostalo;

paczka<<=tablicakodowa[licznik].dlugosckodu-pozostalo;

Po tej operacji wpisujemy poprzez operacje na bitach zawartość paczki do bufora, a następnie sprawdzamy czy przypadkiem odczytywany plik się nie skończył. Jeżeli się nie skończył to wczytujemy do drugiego bufora następne 32 bity.

bufor|=paczka;

if(!feof(odczytywany_plik)){

fread(&bufor_bufora,sizeof(unsigned int),1,odczytywany_plik);

}

Teraz kiedy bufor nr 2 posiada nowy ciąg przesyłamy go ponownie do paczki, ponownie manipulując nią tak, aby nie stracić ani jednego bitu w międzyczasie przesyłając paczkę do bufora,

paczka=bufor_bufora;

paczka>>=32-(tablicakodowa[licznik].dlugosckodu-pozostalo);

bufor|=paczka;

Pozostaje nam teraz zmodyfikować bufor 2 i odpowiednio ustanowić liczbę „pozostalo”

bufor_bufora<<=tablicakodowa[licznik].dlugosckodu-pozostalo;

pozostalo-=tablicakodowa[licznik].dlugosckodu;

pozostalo+=32;

Teraz rozpatrzmy przypadek jeżeli została odpowiednia ilość miejsca do dalszego rozpoznawania znaków. Przypisujemy paczce zawartość bufora numer 2, a następnie ponownie jak to miało miejsce wyżej odpowiednio go przesuwamy, także w międzyczasie modyfikując zawartość pierwszego bufora. Pod koniec modyfikujemy jeszcze raz zmienną „pozostalo”.

}else{

paczka=bufor_bufora;

paczka>>=32-(tablicakodowa[licznik].dlugosckodu);

bufor|=paczka;

bufor_bufora<<=tablicakodowa[licznik].dlugosckodu;

pozostalo-=tablicakodowa[licznik].dlugosckodu;

}

}

5. Efektywność na wybranych przykładach

Nazwa pliku	Skompresowany	Nieskompresowany	Kompresja
tekst1.txt	4 476	6 553	32%
tekst2.txt	76 784	98 304	22%
rfc.txt	374 112	649 767	44%

6. Wnioski

Wykonana praca laboratoryjna potwierdza, że kodowanie Huffmana jest efektywny, kiedy to występuje duża różnica w ilości wystąpień poszczególnych znaków. Dowodem tego jest niska kompresja pliku tekst2.txt

Cel ćwiczenia jakim było napisanie programu kompresującego uważam za osiągniety.

Grupa szkoleniowa

I7Y2S1

Stopień, imię i nazwisko prowadzącego

mgr inż. Marcin Pajewski

Stopień, imię i nazwisko słuchacza

Grzegorz Pol

---