Jednym z algorytmów wykorzystywanych w kompresji bezstratnejkompresja bezstratnakompresji bezstratnej jest algorytm Huffmana. Jego nazwa pochodzi od nazwiska pomysłodawcy tej metody, informatyka Dawida Huffmana.

Huffman zwrócił uwagę na fakt, że różne znaki – na przykład litery – możemy zapisywać za pomocą ciągów bitów o długości zależnej od częstości ich występowania. Znaki. które występują najczęściej mają kody najkrótsze, dzięki czemu łączna liczba bitów jest mniejsza niż przy stosowaniu kodów o stałej długości. Pozwala to zmniejszyć zapotrzebowanie na miejsce niezbędne do przechowywania danych.

Algorytm Huffmana – lista kroków

Ideą algorytmu Huffmana jest sprawdzenie liczby wystąpień każdego elementu kompresowanego zbioru. Element pojawiający się najczęściej jest kodowany z użyciem najkrótszego ciągu bitów. Symbolowi występującemu najrzadziej należy przyporządkować najdłuższy ciąg bitów.

Oto lista czynności składających się na algorytm Huffmana:

1. Utwórz listę drzew binarnychdrzewo binarnedrzew binarnych, z których każde reprezentuje pojedynczy znak alfabetu (unikatowy element kompresowanego zbioru). Drzewo ma składać się z korzenia zawierającego nazwę znaku oraz liczbę jego wystąpień.

2. Znajdź dwa drzewa z najmniejszą liczbą wystąpień znaków i połącz je w jedno. W korzeniu tego drzewa zapisz sumę liczb z drzew składowych; one same mają być prawym i lewym poddrzewem nowego drzewa. Krawędzi łączącej korzeń z lewym poddrzewem przypisz wartość 0, natomiast krawędzi łączącej korzeń z prawym poddrzewem – wartość 1.

3. Jeżeli na liście jest więcej niż jedno drzewo, przejdź do kroku 2.

4. Utwórz kody poszczególnych znaków alfabetu, przechodząc od korzenia do znaku i łącząc przy tym wartości odpowiadające każdej krawędzi.

Algorytm Huffmana – przykład

Porównajmy kodowanie Huffmana z systemu zapisywania symboli zgodnie ze standardem ASCII, w przypadku którego każdemu znakowi odpowiada unikatowy ciąg złożony z siedmiu bitów. Pozwala to zapisać 2Indeks górny 7⁷ = 128 różnych symboli.

Zapiszmy słowo ANIA za pomocą kodów ASCII.  Musimy zakodować trzy różne litery:

A – dwukrotnie, za pomocą ciągu bitów 01000001

N –  za pomocą ciągu bitów 01001110

I – za pomocą ciągu bitów 01001001

Po zakodowaniu słowo ANIA ma postać:

01000001 01001110 01001001 01000001

Do zapisania czterech liter użyliśmy 28 bitów.

Algorytm Huffmana pozwala zmniejszyć liczbę bitów wykorzystywanych do zapisania informacji dzięki przyporządkowaniu odpowiednich kodów literom składającym się na słowo ANIA. Posługujemy się przy tym tzw. drzewem Huffmana:

R1GIosJnZdShh

Ilustracja przedstawia grafikę drzewa binarnego. Złożone jest z pięciu owalów, każdy zawiera napis w środku. Poziom pierwszy, owal z napisem 4, od niego odchodzą strzałki z napisami 0 i 1. Przy napisie 0 owal z napisem 2, przy napisie 1 owal z napisem A dwukropek 2. Od owalu z napisem 2 odchodzą kolejne strzałki 0 i 1. 0 wskazuje na owal z napisem N dwukropek 1, 1 wskazuje na owal z napisem I dwukropek 1.

Korzystając z drzewa odczytujemy kody poszczególnych znaków:

A – 1

N – 00

I – 01

Słowo Ania zakodowane z użyciem algorytmu Huffmana przybiera zatem postać:

100011

W tym przypadku do zapisania wyrazu użyliśmy tylko 6 bitów.

Przykład kodowania Huffmana

Przeanalizujmy teraz przykład kodowania zbioru symboli z wykorzystaniem algorytmu Huffmana. Zakodujmy słowo RABARBAROWA. Każdemu symbolowi przypiszmy liczbę jego wystąpień, a następnie utwórzmy listę drzew binarnych. Każde drzewo zawiera symbol litery i liczbę jej wystąpień.

R1IwHo1jrK6uf

Ilustracja przedstawia 5 okręgów, od lewej do prawej wpisane w nich są litery oddzielone liczbami, są to o 1, w 1, b 2, r 3 oraz a 4.

Dwa drzewa reprezentujące litery występujące najrzadziej – O oraz W – łączymy w jedno drzewo. W korzeniu umieszczamy sumę wystąpień tych symboli, czyli 2. Lewym poddrzewem będzie litera O. Prowadzącej do niego krawędzi przypisujemy wartość 0; prawym poddrzewem jest W, a prowadząca do niego krawędź ma wartość 1:

R1L2CdnzR6q49

Ilustracja przedstawia 6 owali z napisami wewnątrz nich. 3 owale połączono w początkowe drzewo binarne. Podstawą jest owal z napisem 2, od niego odchodzą 2 gałęzie, z oznaczeniem 0 i 1. Gałąź 0 wskazuje na owal z napisem O dwukropek 1. Gałąź 1 wskazuje na owal z napisem W dwukropek 1. Pozostałe owale ustawione są obok pierwszego w rzędzie, są to B dwukropek 2, R dwukropek 3 oraz A dwukropek 4.

Pozostały 4 listy. Ponownie łączymy drzewa z  zapisaną najmniejszą liczbą wystąpień. W korzeniu umieszczamy sumę wystąpień liter O, W oraz B. Przypisujemy odpowiednie wartości nowym krawędziom drzewa: lewej – 0, natomiast prawej – 1:

RoFBnumqVo2ow

Ilustracja przedstawia owale z napisami wewnątrz. 2 z nich ustawiono bez struktury gałęzi, natomiast resztę połączono w drzewo binarne. Owal z napisem 4, gałąź prawa z liczbą 1 do owalu B dwukropek 2, gałąź lewa z liczbą 0 do owalu z liczbą 2. Owal z liczbą 2, gałąź prawa z liczbą 1 do owalu W dwukropek 1, gałąź lewa z liczbą 0 do owalu z napisem O dwukropek 1. Wolne owale to R dwukropek 3 oraz A dwukropek 4.

Na liście nadal jest więcej niż jedno drzewo. Łączymy więc dwa drzewa z najmniejszą liczbą wystąpień – będzie to drzewo składające się z samego korzenia R oraz drzewo z symbolami O, W, B. Sumą wystąpień jest suma znajdująca się w korzeniach dwóch drzew. Pamiętamy o przypisaniu krawędziom wartości 0 lub 1.

RsBJCt6GY0IfC

Ilustracja przedstawia owale z napisami wewnątrz. 1 z nich ustawiono bez struktury gałęzi, natomiast resztę połączono w drzewo binarne. Owal z napisem 7, gałąź prawa z liczbą 1 do owalu R dwukropek 3, gałąź lewa z liczbą 0 do owalu 4. Owal z napisem 4, gałąź prawa z liczbą 1 do owalu B dwukropek 2, gałąź lewa z liczbą 0 do owalu z liczbą 2. Owal z liczbą 2, gałąź prawa z liczbą 1 do owalu W dwukropek 1, gałąź lewa z liczbą 0 do owalu z napisem O dwukropek 1. Wolny owal ma napis A dwukropek 4.

Teraz łączymy dwa pozostałe drzewa. W korzeniu umieszczamy sumę wystąpień liter zapisaną w korzeniach, czyli wartość 11. Jest to liczba wszystkich liter, z których składa się kodowane słowo.

Rf5raxoBhO21J

Ilustracja przedstawia owale z napisami wewnątrz, które połączono w drzewo binarne. Owal z napisem 11, gałąź prawa z liczbą 1 do owalu A dwukropek 4, gałąź lewa z liczbą 0 do owalu 7. Owal z napisem 7, gałąź prawa z liczbą 1 do owalu R dwukropek 3, gałąź lewa z liczbą 0 do owalu 4. Owal z napisem 4, gałąź prawa z liczbą 1 do owalu B dwukropek 2, gałąź lewa z liczbą 0 do owalu z liczbą 2. Owal z liczbą 2, gałąź prawa z liczbą 1 do owalu W dwukropek 1, gałąź lewa z liczbą 0 do owalu z napisem O dwukropek 1.

Na liście pozostało jedno drzewo. Przystępujemy zatem do odczytania kodów symboli. Przechodzimy w tym celu od korzenia do każdej litery.

Otrzymujemy następujące kody:

R – 01

A – 1

B – 001

O – 0000

W – 0001

Zapisujemy kody w kolejności odpowiadającej literom składającym się na słowo  RABARBAROWA. Oto rezultat:

011001101001101000000011

Do zapisania słowa złożonego z 11 liter użyliśmy zatem tylko 24 bitów (zamiast 77, których musielibyśmy użyć posługując się kodami ASCII).

Kod Huffmana jest kodem prefiksowymkod prefiksowykodem prefiksowym. Oznacza to, że ciąg bitów opisujący dowolny symbol nie jest początkiem kodu żadnego innego symbolu.

W zaprezentowanym przykładzie kodem litery A jest 1. Nietrudno zauważyć, że żaden inny kod nie zaczyna się od tej cyfry. To samo dotyczy kodu litery R: od ciągu 01 nie rozpoczyna się ani jedna spośród pozostałych sekwencji bitów.

Słownik