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
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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

kompresja bezstratna
kompresja bezstratna

metoda kompresji, w przypadku której – po zdekompresowaniu danych – otrzymujemy informację niezmienioną, taką samą jak początkowa (przed skompresowaniem)

drzewo binarne
drzewo binarne

drzewo, w którym każdy węzeł ma nie więcej niż dwóch synów

kod prefiksowy
kod prefiksowy

kod, w którym żadne ze słów kodowych nie jest początkiem innego słowa