Algorytmy » Kompresja

Huffmana, kodowanie

  • 2007-03-27 00:27
  • 3 komentarze
  • 2781 odsłon
  • Oceń ten tekst jako pierwszy

Kodowanie Huffmana


Kodowanie Huffmana w przeciwieństwie do algorytmu Imploding jest algorytmem
  kompresji statycznej. Oznacza to, że program kompresujący musi przynajmniej
  raz przelecieć cały kompresowany plik w celu stworzenia histogramu.


Kodowanie Huffmana jest sposobem dopasowania zapisu znaków do rodzaju kompresowanych danych. Wykorzystywane jest m. in. w kompresji JPEG jako końcowy etap przetwarzania.


Teraz już o samym algorytmie:


Algorytm wykorzystuje drzewa binarne i kodowanie znaków zmienną długością kodu.

  1. Utwórz histogram (częstotliwość występowania znaków w pliku).

  2. Utwórz wierzchołki drzewa o odpowiednich wagach (waga wierzchołka jest równa
  liczbie znaków).

  3. Połącz dwa najlżejsze wierzchołki w jeden dodając do kodu pierwszego cyfrę
  0 a drugiemu 1.

  4. Powtarzać etap 3, aż osiągniemy koniec drzewa.

  Huffman.gif


Znak
Q
W
E
R
T
Y
Kod
011
010
001
000
10
11
Liczba znaków
2
3
3
4
5
4

5. W ten sposób otrzymujemy listę znaków i ich kodów najlepiej dopasowanych do naszych danych.

  Najczęściej występującym znakom przyporządkowywany jest najkrótszy kod.

  6. Następnie zapisujemy kody znaków do strumienia bitów.


Odczyt jest znacznie prostszy. Odczytujemy zapisaną tablicę z kodami znaków, a następnie odczytujemy bit po bicie, sprawdzając, czy kod jaki nam powstaje jest na liście i podstawiając odpowiedni znak.


Przykładowy kod źródłowy Huffman.zip

3 komentarze

Adam Boduch 2002-10-26 13:24

Moim zdaniem powinienes troche tutaj dac kodu z tego przykladu i go omowic... ale OK! :)

spin 2002-10-12 12:14

Bardzo fajne !!!