Kodowanie Huffmana – omówienie i implementacje

W informatyce każdą informację możemy przedstawić na wiele sposobów. Przykładem może być prosta konwersja z typu całkowitego int na typ tekstowy string. Zabieg taki jest czasem wymagany, aby mieć łatwiejszą kontrolę nad programem lub, po prostu, aby wyświetlić użytkownikowi dane w odpowiedniej formie. Zamiana sposobu zapisu informacji jest również powszechnie wykorzystywana w procesie kompresji danych. Dzisiaj omówimy więc wspólnie jeden z ważniejszych algorytmów kompresji bezstratnej, jakim jest kodowanie Hoffmana.

Czym jest kompresja danych?

Krótko mówiąc kompresja danych ma na celu zminimalizowanie redundancji i tym samym zmniejszenie rozmiaru pliku.

kodowanie Huffmana - zbiór przed kompresją

Za przykład weźmy 12-elementowy zbiór. Łatwo zauważyć, że składa się on z 3 rodzajów figur geometrycznych. Z pozoru może wydawać się mało rozbudowany, jednak gdyby go powtórzyć 1000-krotnie mielibyśmy już 12000 elementów. Taką ilość elementów ciężej już sobie wyobrazić. Co można zrobić, by uprościć przedstawienie zbioru? Zamiast wypisywać tą samą figurę wielokrotnie pod rząd, wystarczy zapisać ją raz i dopisać ilość jej wystąpień. Powyższy zbiór możemy więc uprościć do:

kodowanie Huffmana - zbiór po kompresji

W ten sposób zredukowaliśmy ilość elementów do sześciu i mimo, że nadal trudno by było sobie wyobrazić sześciotysięczny ciąg elementów, to jednak byłoby ich dwukrotnie mniej, niż przed „kompresją”. Podsumowując kompresją możemy nazwać proces, którego celem jest zredukowanie wielkości zbioru danych, poprzez zastępowanie powtarzających się ciągów prostszymi symbolami.

Algorytmy kompresji danych możemy podzielić na stratne i bezstratne. Kompresja bezstratna oznacza, że po dekompresji (procesie odwrotnym do kompresji) stan pliku będzie identyczny, jak przed kompresją. Stosowana jest np. w formatach GIF, PNG, czy wszędzie tam, gdzie ważne jest, aby każdy szczegół pliku był zachowany. Kodowanie Hoffmana, o którym będziemy dzisiaj mówić, jest przykładem kompresji bezstratnej.

Kompresja stratna oznacza, że po kompresji pewne szczegóły pliku są nieodwracalnie tracone i po dekompresji zostaną one pominięte. Kompresję stratną spotyka się np. w plikach JPEG, MP3, czy MPEG.

Kodowanie Huffmana – zasada działania

Kodowanie Huffmana polega na zastępowaniu złożonych partii danych pojedynczymi, prostymi kodami (ciągami bitów). W efekcie dane wyjściowe są znacznie krótsze od wejściowych.

By zrozumieć istotę kodowania Huffmana, przejdźmy do przykładu. Weźmy ciąg znaków „programowanie”. Jak pewnie dobrze wiecie, w klasycznym kodowaniu ASCII każdy znak reprezentowany jest przez jeden bajt danych, czyli 8 bitów. Za pomocą ośmiu bitów można zapisać 256 znaków. W powyższym słowie zapisanym w formacie ASCII nie wykorzystaliśmy jednak ich wszystkich, a mimo to zajęliśmy łącznie 13 bajtów. Nie potrzebujemy więc aż 256 znaków. Nasz ciąg składa się z liter z podanego zbioru : {p, r, o, g, a, m, w, n, i, e}. Wykorzystujemy więc jedynie 10 znaków z 256. Oznacza to, że na pojedynczy znak wystarczą nam 4 bity (24 = 16 > 10), zamiast ośmiu. Zauważ jednak, że im więcej liter wykorzystamy w tekście, tym mniej efektywny będzie ten algorytm. Gdyby wykorzystać w pliku wszystkie 256 znaków, to jego działanie nie miałoby żadnego efektu.

Kodowanie Huffmana – algorytm

Jak działa kodowanie Huffmana? W przypadku zbiorów znaków w pierwszej kolejności sprawdzana jest ilość wystąpień każdej litery ze zbioru, a następnie przypisywane jest im odpowiednia wartość. Znaki występujące najczęściej dostają najkrótsze kody, zaś te występujące rzadziej – dłuższe. W tym celu wykorzystuje się drzewo binarne, w które wpisywane są znaki i ich częstotliwości wystąpień. Jeżeli nie wiesz czym jest drzewo binarne, to odsyłam Cię do tego wpisu.

Działanie algorytmu możemy rozpisać następująco:

  1. Pobierz tekst od użytkownika;
  2. Zlicz ilość wystąpień dla każdego znaku;
  3. Dla każdego znaku utwórz liście drzewa binarnego; wartością liścia jest ilość wystąpień dla danego znaku
  4. Wybierz dwa liście o najmniejszych wartościach
  5. Utwórz nowy liść, który będzie kontenerem dla wybranych liści; jego wartość jest sumą ich wartości; mniejszy element będzie dzieckiem po lewo, większy dzieckiem po prawo
  6. Powtarzaj kroki 4-5, aż nie pozostanie jeden element – korzeń drzewa.

Na poniższej animacji prześledzisz działanie kodowania Huffmana, dla słowa „banany”:

Kodowanie Huffmana – implementacja C++ Java Python

Mając schemat działania pozostało nam już tylko wcielić go w życie 🙂 Zanim przejdziemy do faktycznego kodowania, musimy najpierw przygotować sobie odpowiednie obiekty i funkcje.

Na początek utwórzmy obiekt liścia – będzie on budulcem naszego drzewa. Musimy w nim zawrzeć jego wartość, wskaźniki na potomne liście oraz znak jaki reprezentuje. Dobrze jest również stworzyć przyjmujący wszystkie te wartości jako argumenty. Dzięki temu zaoszczędzimy sobie nieco wysiłku. Proponuję również dodać metodę typu logicznego, która zwróci, czy dany liść nie jest kontenerem dla innych liści.

C++

Java

Python

Gdy mamy już obiekt-liść,  to musimy stworzyć kolejny obiekt, który będzie efektywnie te liście porównywać. Obiekt ten będzie miał znaczący wpływ na strukturę drzewa:

C++

Java

Python

W Pythonie poniższą funkcję należy dodać do ciała klasy Node:

Mając już potrzebne obiekty możemy przystąpić do tworzenia drzewa. Stworzymy więc funkcję o argumencie tekstowym, która zwróci obiekt Node będący korzeniem drzewa.  Zanim jednak w ogóle zaczniemy je budować, musimy najpierw zliczyć znaki i stworzyć na ich podstawie liście drzewa. Utworzone liście dodamy do obiektu typu Priority Queue, który będzie porównywać je przy pomocy przygotowanej wyżej funkcji. Priority Queue jest obiektem o podobnej zasadzie działania, co stos, z tą róznicą, że dane nie zawsze są wrzucane na „wierzch”. Zamiast tego przy dodawaniu dokonuje się porównania i na podstawie jego wyniku element jest umieszczany na odpowiedniej pozycji.

C++

Java

Python

Następnie łączymy dwa liście o najmniejszej wartości, tworząc tym samym liść-kontener, którego wartością będzie suma wartości tych dwóch liści. Następnie dodajemy go do listy pozostałych liści. Kroki te powtarzamy, aż na liście nie zostanie jeden element – korzeń naszego drzewa. Wtedy to możemy zwrócić go jako wynik naszej funkcji – drzewo jest już wtedy zbudowane.

C++

Java

Python

Mamy już utworzone nasze drzewo. Możemy teraz zakodować jego wartości i stworzyć tablicę kodowania. W tym celu stworzymy funkcję rekurencyjną, która wykona się dla wszystkich elementów po lewo i po prawo dla każdego elementu. Jeżeli natrafimy na koniec drzewa, przerywamy rekurencję. Jeżeli temat rekurencji nie jest Ci do końca znany, rzuć okiem na wpis, w którym go wytłumaczyliśmy.  

C++

Java

Python

Na sam koniec pozostało nam już tylko zakodowanie tekstu, przy użyciu utworzonej tablicy kodowania:

C++

 Java

Python

Kodowanie Huffmana – odkodowanie

Powyższa procedura kodowania jest całkowicie odwracalna, o ile nadal mamy dostęp do drzewa lub tablicy kodowania. W pierwszym przypadku procedura jest prosta. Iterujemy poprzez każdy bit w kodzie. Jeżeli natrafimy na zero, idziemy w lewą stronę drzewa, jeżeli natomiast trafimy na jeden – wybieramy prawy liść. Gdy posiada on swój znak, to wstawiamy go w zmienną pomocniczą i wracamy na początek drzewa. Jeżeli jednak jest to kontener, to idziemy dalej, dopóki nie trafimy na liść zawierający znak. Czynności te powtarzamy do samego końca zakodowanego tekstu. W ich wyniku w zmiennej pomocniczej będzie znajdować się odkodowany tekst.

C++

Java

Python

grupa wsparcia matura z informatyki

Podsumowanie

W ten oto sposób udało nam się wspólnie zaimplementować kodowanie Huffmana. Z racji na swoją niską wydajność, praktycznie wcale nie korzysta się z niego samodzielnie. Wykorzystywany jest on jednak jako ostatni etap kompresji, najczęściej w połączeniu z kilkoma innymi metodami. Niemniej jednak jest to algorytm warty poznania i zrozumienia. Kto wie, może spotkacie się z nim na maturze? Poniżej znajdziecie pełną implementację kodowania Huffmana:

C++

Java

Python

You Might Also Like
1 Comment
Dodaj komentarz