Algorytm kodowania Huffmana to kolejna metoda, którą stosuję w
nGENE Tech do kompresji plików zasobów (podobno w kodowaniu arytmetycznym, które daje lepsze wyniki łatwo nadziać się na jakiś patent). Wykorzystuję ją jako ostatni krok kompresji, zaraz po wykonaniu na danych wejściowych opisywanego ostatnio
Run-Length Encoding.
Algorytm tu opisywany opiera się na częstotliwości występowania poszczególnych znaków w bloku danych.
Powiedzmy, że mamy jakiś ciąg znaków, w którym częstotliwości poszczególnych znaków przedstawiają się jak poniżej (dokładna postać ciągu jest nieistotna gdyż algorytm nie uwzględnia ich kolejności):
a: 10b: 2c: 21d: 44e: 78f: 1Jednocześnie nie występuje jakikolwiek inny znak.
Normalnie każdy z tych znaków byłby reprezentowany przy pomocy 1 bajtu (8 bitów). Ale łatwo zauważyć, że można by je reprezentować za pomocą binarnych kodów o różnej długości (>= 1 bit). Im częściej występuje dany znak, tym jego kod powinien być krótszy dzięki czemu wszystkie jego wystąpienia zajmą dużo mniej miejsca, co jest równoważne wyższemu stopniowi kompresji, np. znak 'e' (najczęściej występujący w przykładzie powyżej) mógłby być reprezentowany przez '1' tj. pojedynczy bit. Oznacza to, że wszystkie jego wystąpienia zajęłyby 78 bitów ~ 10 bajtów zamiast standardowych 78 bajtów!
Jak znaleźć kody dla znakówAle jak znaleźć kody dla każdego znaku (najlepiej, optymalne)? Tutaj do gry wchodzi algorytm Huffmana. Jeśli znamy już częstotliwości wszystkich znaków musimy zbudować specjalne drzewo binarne, które w prosty sposób pozwoli nam na ich znalezienie. Zanim przejdę do jego omawiania o to jak będzie ono wyglądało dla danych z wcześniejszego przykładu:
Mając drzewo w takiej postaci znalezienie kodów jest trywialne. Zwróćmy uwagę, że w liściach znajdują się poszczególne znaki z naszego alfabetu (są tam też podane ich częstotliwości). Jeśli chcemy znaleźć kod dla danego znaku, dla którego znamy już częstotliwość występowania, zaczynając w korzeniu z kodem "" idziemy w dół dodając do kodu '0' jeśli obieramy lewą krawędź i '1' jeśli prawą aż dotrzemy do docelowego znaku.
Dla przykładu dla znaku 'f' kod jest następujący: '00000' (uwaga! to nie jest 0!!!) ponieważ 5 razy obieramy lewą krawędź, dla 'c' - '001', dla 'd' - '01', a dla znaku 'e' - '1'. Jak widać im częściej dany znak występuje, tym krótszy ma kod (co chcieliśmy osiągnąć).
Budowanie drzewa kodów HuffmanaBudowanie drzewa kodów jest dosyć prostą sprawą. Mając listę elementów ('lista' jest tu użyta raczej w dowolny sposób. Zwykle wykorzystywaną strukturą jest bowiem kopiec), wybieramy w każdej iteracji algorytmu dwa o najmniejszych częstotliwościach występowania po czym łączymy je w drzewo w taki sposób, że stają się one liśćmi, a ich rodzic-korzeń ma częstotliwość będącą sumą ich częstotliwości występowania. W pierwszej iteracji łączymy w ten sposób znaki 'f' oraz 'b' (o częstotliwościach odpowiednio 1 i 2) i wpisujemy 3 jako częstotliwość ich rodzica.
To drzewo z powrotem wstawiamy na kopiec, przywracamy jego właściwości i wybieramy kolejne dwa elementy. Tym razem będzie to właśnie '3' i '10' (co odpowiada znakowi 'a'). Postępujemy tak dotąd aż liczba elementów kopca nie wyniesie 1. Gdy tak się stanie - znaleźliśmy drzewo kodów.
Mając to drzewo, kompresja (kodowanie) jest bardzo proste. Przechodząc przez kolejne znaki ciągu wejściowego musimy po prostu wyszukać odpowiadający im kod, i wypisać go na wyjście. Oczywiście należy pamiętać, żeby wypisywać bity, a nie całe bajty, co można zrobić np. tak jak pokazano w poniższym pseudokodzie:
unsigned char curr = 0;
usigned int currByte = 0;
usingned int bits = 0;
while(!data.eof())
{
// First get next character from the input
curr = data.getNextCharacter();
// Look up its code in the table
const char* code = huffmanCodes[curr];
usingned char c = 0;
while(code++)
{
c = code[i];
currByte <<= 1;
// Write one in the least significant bit
if(c == '1')
currByte |= 1;
++bits;
// When whole byte has been filled write it to the output
if(bits == 8)
{
result.write((char*)&currByte, 1);
bits = 0;
currByte = 0;
}
}
}
Oczywiście należy też zadbać o ewentualne wolne bity pod koniec, ale to już pomijam.
Dekompresja danychJak zdekodować dane skompresowane za pomocą tego algorytmu? Aby było to możliwe musimy na wyjście zapisać dodatkowe dane, które pozwolą nam na rekonstrukcję drzewa (nie jest możliwe znalezienie częstotliwości w oparciu o skompresowane dane :) ). Mianowicie musimy zapisać drzewo kodów. Dla każdego węzła rozpoczynając od korzenia zapisujemy takie dane:
- 0 - jeśli jest to wewnętrzny węzeł (1 bit),
- 1 + znak - jeśli jest to liść drzewa (9 bits). Znak to oczywiście znak, z którym dany kod jest powiązany, np. dla kodu '1' w naszym przypadku będzie to 'e'.
Oczywiście oznacza to pewne dodatkowe dane, ale w większości przypadków jest to niemal pomijalne. Za to dzięki temu rekonstrukcja drzewa jest trywialna, a tym samym dekodowanie znaków również. Wczytujemy dane bit po bicie i rozpoczynając w korzeniu idziemy w lewo jeśli wartość bitu wynosi 0 i w prawo jeśli 1, aż nie znajdziemy się w liściu, co oznacza, że powinniśmy wypisać znak w nim się znajdujący i znów zacząć od korzenia, bo kolejny bit należy już do innego znaku. Oczywiście kody są jednoznaczne, np. dla naszego przykładu kod:
111001101zostanie odkodowany jako:
eeeced
Z innych rzeczy, zarejestrowałem się na
Twitterze na fali jego popularności i dodałem odpowiedni widget do tej strony.
Posty
