Z jej treści możemy dowiedzieć się więcej na takie tematy, jak: czym jest kodowanie Huffmana, gdzie jest wykorzystywany ten algorytm, najważniejsze cechy kodu, działanie kodu, drzewo Huffmana
Kodowanie Huffmana to jedna z najprostszych i łatwych w implementacji metod kompresji bezstratnej. Została opracowana w 1952 roku przez Amerykanina Davida Huffmana.
Algorytm Huffmana jest wykorzystywany w wielu profesjonalnych metodach kompresji tekstu, obrazów i dźwięków, również w połączeniu z innymi metodami. Redukcja wielkości danych przy stosowaniu tego algorytmu wynosi ok 50 % ( w przypadku obrazów i dźwięków kodowane są nie same znaki np. piksele, ale również między kolejnymi znakami). Najważniejsze cechy kodu Huffmana :
- jest zero - jedynkowy;
- jest kodem prefiksowym;
- jest tworzony tak, aby średnia długość kodu znaku była możliwie najkrótsza;
Prześledźmy teraz działanie algorytmu Huffmana na przykładzie sześciu wybranych liter
Algorytm Huffmana dla sześciu wybranych liter :
w kółkach mamy częstotliwość występowania w języku polskim napisanej niżej litery.
Aby stworzyć drzewo Huffmana ze zbioru usuwamy dwie najmniejsze częstotliwości czyli w naszym przypadku 1,29 i 3,10, a na ich miejsce wstawiamy ich sumę 1,29 + 3,10 = 4,39 i podczepiamy wierzchołki z usuniętymi częstotliwościami pod nowy wierzchołek. Otrzymujemy:
teraz dwie najmniejsze częstotliwości to 3,45 i 4,39, które również łączymy jak wcześniej.
Nastepnym krokiem jest dodanie do siebie 4,63 i 7,83 po czym otrzymujemy: Kolejne dwie najmniejsze częstotliwości to 7,90 i 8,71, po czym otrzymaliśmy 2 drzewa:
Na końcu dodajemy dwie ostatnie częstotliwości - 13,47 i 16,61. Ostatecznie otrzymujemy jedno drzewo.
Po otrzymaniu jednego drzewa należy każde rozgałęzienie odpowiednio oznaczyć 0 lub 1. Każdą lewą gałąź 0, a prawą 1 (lub odwrotnie). Posługując się powyższym drzewem odkodujmy słowa : 1) 10110110101100
2) 00101011001011001000010101100
Dzięki temu, że kod jest prefiksowy łatwo można podzielić ten ciąg 0 i 1 na odpowiednie kody liter :
... zobacz całą notatkę
Komentarze użytkowników (0)