Kodowanie Huffmana

Wprowadzenie: problem kodów o stałej długości

Informacje cyfrowe, w tym tekst, są zapisywane jako sekwencje bitów. Prostym sposobem reprezentowania tekstu jest użycie kodu o stałej długości. Standard ASCII definiuje unikalne kody 7-bitowe dla znaków, cyfr i znaków interpunkcyjnych. W pamięci znak często zajmuje cały bajt, dlatego kod ASCII zapisuje się w polu 8-bitowym z wiodącym zerem. Litera 'A' to 65 (01000001), 'B' to 66 (01000010) i tak dalej.

Kod stałej długości jest prosty i przewidywalny, lecz przydziela tyle samo bitów znakom o różnej częstości. Litera 'a' może otrzymać tyle samo miejsca co rzadkie 'ź' lub symbol '{'. Prace Claude'a Shannona pokazały, że język ma nierówny rozkład częstości znaków. Powtarzalność tego rozkładu jest redundancją, którą można wykorzystać do wydajniejszego kodowania tekstu. Kodowanie Huffmana przypisuje krótsze kody częstym symbolom.

Podstawowa idea: kodowanie o zmiennej długości

David A. Huffman opisał tę metodę w 1952 roku jako student. Kodowanie Huffmana jest statystyczną metodą kompresji bezstratnej.

Główna zasada jest następująca:

W efekcie średnia liczba bitów na symbol w wiadomości może być niższa niż w kodzie o stałej długości. Implementacja wymaga metody generowania kodów oraz jednoznacznego dekodera.

Jednoznaczne dekodowanie i kody prefiksowe

Przy kodach o różnych długościach trzeba określić, gdzie kończy się jeden kod i zaczyna następny.

Na przykład, załóżmy, że mamy kody A=0, B=1, C=01. Jeśli dekompresor odczyta strumień bitów '01', czy to oznacza 'A', a następnie 'B', czy może oznacza 'C'? Ta niejednoznaczność czyni kod bezużytecznym.

Kodowanie Huffmana rozwiązuje ten problem przez utworzenie kod prefiksowy. W takim kodzie żadne słowo kodowe nie jest początkiem innego słowa. Jeśli 'A' ma kod '0', żaden inny kod nie może zaczynać się od '0'. Jeśli 'B' ma kod '10', żaden inny kod nie może zaczynać się od '10'. Ta własność usuwa niejednoznaczność. Po dopasowaniu poprawnego słowa kodowego dekoder rozpoznaje kompletny symbol bez odczytywania separatora ani dodatkowych bitów. Algorytm Huffmana generuje optymalny kod prefiksowy dla zadanego rozkładu częstości.

Algorytm Huffmana

Zbudujmy kod Huffmana na przykładzie ciągu JEST TO PROCES TWORZENIA DRZEWA. Proces obejmuje cztery etapy: analizę częstotliwości symboli, budowę drzewa binarnego, przypisanie kodów i zakodowanie wiadomości.

Krok 1: analiza częstości

Najpierw zliczamy każdy unikalny znak w ciągu źródłowym. Spacja również jest symbolem danych i musi znaleźć się w tabeli.

Krok 2: konstrukcja drzewa Huffmana

W tym etapie częstotliwości służą do budowy drzewa binarnego od dołu do góry. Algorytm zachłanny w każdym kroku wybiera dwa węzły o najmniejszej sumie częstości.

1. Zacznij od listy "wolnych" węzłów, gdzie każdy węzeł jest liściem reprezentującym znak i jego częstotliwość.
2. Wybierz dwa węzły o najniższych częstotliwościach z listy.
3. Utwórz nowy wewnętrzny węzeł, który będzie rodzicem tych dwóch wybranych węzłów.
4. Częstotliwość tego nowego węzła nadrzędnego jest sumą częstotliwości jego dwóch potomków.
5. Usuń dwa węzły potomne z listy wolnych węzłów i dodaj do niej nowy węzeł nadrzędny.
6. Powtarzaj kroki 2-5, aż na liście pozostanie pojedynczy węzeł. Ten ostatni węzeł jest korzeniem drzewa Huffmana.

Iteracyjne łączenie umieszcza symbole o małej częstości dalej od korzenia, przez co otrzymują dłuższe kody. Symbole częste pozostają bliżej korzenia i otrzymują krótsze kody.

Krok 3: przypisywanie kodów

Po zbudowaniu drzewa przechodzimy od korzenia do każdego liścia. Przyjmujemy oznaczenie lewej gałęzi jako '0' i prawej jako '1'. Sekwencja bitów na ścieżce od korzenia do liścia jest kodem Huffmana tego symbolu.

Jedna poprawna konstrukcja drzewa dla tego przykładu daje następującą tabelę kodów:

Najczęstsze znaki (E i spacja) mają kody o długości 3, a znaki występujące raz mają kody o długości 5. Taki rozkład zmniejsza średnią długość kodu.

Krok 4: kodowanie i pomiar wyników

W ostatnim kroku zastępujemy każdy znak w ciągu jego kodem Huffmana i łączymy kody w jeden strumień bitów.

Ciąg "JEST TO PROCES TWORZENIA DRZEWA" ma 31 znaków. Dla porównania przyjmijmy 8 bitów przechowywania na znak. Rozmiar wyjściowy wynosi wtedy:

Skompresowany rozmiar jest sumą długości kodów Huffmana dla wszystkich znaków:$(4 \times 3) + (4 \times 3) + (3 \times 4) + (3 \times 3) + (3 \times 3) + (2 \times 4) + (2 \times 4) + (2 \times 4) + (2 \times 4) + (1 \times 5) + (1 \times 5) + (1 \times 5) + (1 \times 5) + (1 \times 5) + (1 \times 5) = 116 \text{ bitów}$

Współczynnik kompresji wynosi:

W tym przykładzie strumień kodów ma mniej niż połowę długości reprezentacji 8-bitowej. Wynik zależy od częstości znaków oraz narzutu na zapis tabeli kodów.

Wartość 116 bitów dotyczy samego strumienia kodów. Plik musi dodatkowo zawierać opis tabeli lub drzewa, a ostatni bajt może wymagać dopełnienia. Przy równych częstościach można zbudować różne drzewa Huffmana. Jeśli zachowują te same długości kodów, suma bitów pozostaje taka sama.

Dekoder musi otrzymać identyczny model kodowania. Przy krótkich danych narzut metadanych może więc zmniejszyć albo odwrócić zysk ze skrócenia strumienia.

Kolejność bitów wynika z kolejności znaków w wiadomości, a tabela kodów pozwala odtworzyć granice symboli.

Mocne i słabe strony kodowania Huffmana

Kodowanie Huffmana ma określone zalety i ograniczenia. Jego właściwości zależą od rozkładu częstości oraz od formatu, w którym jest używane.

Mocne strony

• Optymalny kod prefiksowy: Dla ustalonego zbioru częstości algorytm Huffmana generuje kod prefiksowy o najmniejszej średniej długości wśród kodów binarnych tego typu.
• Prostota i szybkość: Algorytm ma prostą implementację, a kodowanie i dekodowanie można wykonać za pomocą drzewa lub tabeli kodów.
• Publiczny opis metody: Podstawową metodę opisano w publikacji z 1952 roku. Warunki licencyjne konkretnego formatu mogą być odrębne.

Słabe strony i ograniczenia

• Wymóg dwóch przebiegów: Wersja statyczna wymaga znajomości częstości przed kodowaniem. Zwykle oznacza to jeden odczyt pliku do zbudowania tabeli i drugi odczyt do kodowania. Istnieją adaptacyjne wersje Huffmana, które aktualizują tabelę podczas pracy.
• Narzut Związany z Przechowywaniem Drzewa: Aby zdekompresować dane, odbiornik musi mieć dokładnie to samo drzewo Huffmana (lub tabelę częstotliwości), które zostało użyte do kompresji. Ta informacja musi być wysłana wraz ze skompresowanymi danymi, co dodaje narzut, który może zmniejszyć zyski z kompresji, zwłaszcza w przypadku małych plików.
• Całkowita długość kodów: Entropia może być wartością ułamkową, lecz Huffman przypisuje każdemu symbolowi całkowitą liczbę bitów. Kod może więc pozostawać powyżej granicy entropii. Kodowanie arytmetyczne może przybliżyć tę granicę dokładniej.
• Brak modelu kontekstu: Podstawowy algorytm traktuje symbole niezależnie od ich sąsiedztwa. Nie wykorzystuje zależności wyższego rzędu, takiej jak częste występowanie 'u' po 'q' w języku angielskim.

Zastosowania

Kodowanie Huffmana może działać samodzielnie, lecz często jest etapem większego systemu kompresji. Jego zadaniem jest kodowanie strumienia symboli według ustalonego modelu częstości. Przykłady obejmują:

• W profilach JPEG używających kodowania Huffmana kompresowane są skwantyzowane współczynniki DCT.
• W algorytmie Deflate (używanym przez ZIP, gzip i PNG), kodowanie Huffmana jest używane do kompresji strumienia literałów i par długość/odległość produkowanych przez etap słownikowy LZ77.

W tych zastosowaniach kodowanie Huffmana pozostaje metodą kodowania entropijnego o prostej strukturze i określonej optymalności dla kodów prefiksowych.