Kompresja Huffmana

Wprowadzenie

Kodowanie Huffmana (ang. Huffman Coding) to algorytm kompresji danych opracowany przez Davida Huffmana w 1952 roku. Jest to optymalne kodowanie prefiksowe - żaden inny algorytm kodowania prefiksowego nie może osiągnąć lepszej kompresji.

Idea: Przydziel krótsze kody znakom występującym częściej, a dłuższe znakom rzadszym.

Kluczowa własność: Kodowanie prefiksowe - żaden kod nie jest prefiksem innego kodu.

Kodowanie Huffmana jest wykorzystywane w:

Kompresji plików (ZIP, GZIP, DEFLATE)
Formatach graficznych (JPEG, PNG)
Kompresji wideo (MPEG)
Protokołach sieciowych (HTTP/2, HPACK)
Kompresji tekstu (archiwa, ebook'i)
Przesyłaniu danych (modemy, satelity)

Problem kodowania

Kodowanie o stałej długości vs zmiennej długości

Wyjście:

=== Kodowanie o stałej vs zmiennej długości ===

Tekst: 'ABRACADABRA'
Długość: 11 znaków

Częstości znaków:
  'A': 5 (45.5%)
  'B': 2 (18.2%)
  'C': 1 (9.1%)
  'D': 1 (9.1%)
  'R': 2 (18.2%)

============================================================
KODOWANIE O STAŁEJ DŁUGOŚCI:
============================================================

Liczba unikalnych znaków: 5
Bitów na znak: 3

Kody:
  'A': 000
  'B': 001
  'C': 010
  'D': 011
  'R': 100

Zakodowany tekst:
  000001100000010000011000001100000
  Długość: 33 bitów

============================================================
KODOWANIE O ZMIENNEJ DŁUGOŚCI (przykład):
============================================================

Kody (krótsze dla częstszych):
  'A': 0      (częstość: 5)
  'B': 110    (częstość: 2)
  'C': 1110   (częstość: 1)
  'D': 1111   (częstość: 1)
  'R': 10     (częstość: 2)

Zakodowany tekst:
  0110100111001111011100
  Długość: 22 bitów

============================================================
PORÓWNANIE:
============================================================

Stała długość:  33 bitów
Zmienna długość: 22 bitów
Oszczędność:    11 bitów (33.3%)

Kodowanie prefiksowe

Właściwość prefiksu

Definicja: Kodowanie jest prefiksowe jeśli żaden kod nie jest prefiksem innego kodu.

Wyjście:

=== Kodowanie prefiksowe ===

Test 1: Kodowanie prefiksowe (dobre)
Kody: {'A': '0', 'B': '110', 'C': '1110', 'D': '1111', 'R': '10'}
Jest prefiksowe? ✓ TAK

Test 2: Kodowanie NIE-prefiksowe (złe)
Kody: {'A': '0', 'B': '01', 'C': '011', 'D': '1'}
Jest prefiksowe? ✗ NIE
Konflikty:
  '0' (A) jest prefiksem '01' (B)
  '0' (A) jest prefiksem '011' (C)
  '01' (B) jest prefiksem '011' (C)

============================================================
PROBLEM Z DEKODOWANIEM (nie-prefiksowe):
============================================================

Zakodowany ciąg: '011'

Możliwe dekodowania:
  1. '0' + '11' → A + ??  (brak '11' w kodach)
  2. '01' + '1' → B + D
  3. '011' → C

✗ Niejednoznaczne! Nie można poprawnie zdekodować!

Drzewo Huffmana

Reprezentacja kodowania prefiksowego

Kluczowa idea: Każde kodowanie prefiksowe można reprezentować jako drzewo binarne.

Liście = symbole do zakodowania
Ścieżka od korzenia do liścia = kod symbolu
Lewo = '0', Prawo = '1'

Struktura węzła

Algorytm Huffmana

Budowa drzewa (zachłanna)

Algorytm:

1. Stwórz liść dla każdego symbolu z jego częstością
2. Umieść wszystkie liście w kolejce priorytetowej (min-heap)
3. Dopóki w kolejce jest więcej niż 1 węzeł:
   a) Wyciągnij dwa węzły o najmniejszych częstościach
   b) Stwórz nowy węzeł z nimi jako dziećmi
   c) Częstość nowego węzła = suma częstości dzieci
   d) Wstaw nowy węzeł do kolejki
4. Pozostały węzeł to korzeń drzewa Huffmana

Implementacja

Wyjście:

=== Budowanie drzewa Huffmana ===

Budowanie drzewa Huffmana dla 5 unikalnych znaków

Początkowe węzły (liście):
  'C': częstość = 1
  'D': częstość = 1
  'B': częstość = 2
  'R': częstość = 2
  'A': częstość = 5

Krok 1:
  Połącz: Leaf('C', freq=1) + Leaf('D', freq=1)
  Nowy węzeł: freq = 2

Krok 2:
  Połącz: Node(freq=2) + Leaf('B', freq=2)
  Nowy węzeł: freq = 4

Krok 3:
  Połącz: Leaf('R', freq=2) + Node(freq=4)
  Nowy węzeł: freq = 6

Krok 4:
  Połącz: Leaf('A', freq=5) + Node(freq=6)
  Nowy węzeł: freq = 11

============================================================
WYGENEROWANE KODY HUFFMANA:
============================================================

Znak     Kod          Długość    Częstość
---------------------------------------------
'A'      0            1          5
'R'      10           2          2
'B'      110          3          2
'C'      1110         4          1
'D'      1111         4          1

Kodowanie i dekodowanie

Kodowanie tekstu

Wyjście:

=== Kodowanie tekstu ===

Tekst oryginalny: 'ABRACADABRA'
Długość: 11 znaków

Zakodowany (bity): 0110100111001111011100
Długość: 22 bitów

Porównanie:
  Kodowanie Huffmana: 22 bitów
  Kodowanie stałe:    33 bitów
  Oszczędność:        11 bitów (33.3%)

Dekodowanie tekstu

Wyjście:

=== Dekodowanie ===

Zakodowane bity: 0110100111001111011100
Długość: 22 bitów

Zdekodowany tekst: 'ABRACADABRA'
Długość: 11 znaków

Oryginalny tekst:  'ABRACADABRA'
Zdekodowany tekst: 'ABRACADABRA'
Poprawne? ✓ TAK

Wizualizacja drzewa Huffmana

Wyjście:

=== Wizualizacja drzewa Huffmana ===

Drzewo:
[11]
├── 0: 'A' (freq=5)
└── 1: [6]
    ├── 0: 'R' (freq=2)
    └── 1: [4]
        ├── 0: 'B' (freq=2)
        └── 1: [2]
            ├── 0: 'C' (freq=1)
            └── 1: 'D' (freq=1)

============================================================
Interpretacja:
============================================================

Ścieżki od korzenia do liści to kody:
  'A': 0
  'R': 10
  'B': 110
  'C': 1110
  'D': 1111

Optymalnść algorytmu Huffmana

Dowód optymalności

Obliczanie średniej długości kodu

Wyjście:

=== Średnia długość kodu ===

Tekst: 'ABRACADABRA'
Liczba znaków: 11

Analiza kodów:
Znak     Częstość     P(char)      Kod      L(code)    P × L
----------------------------------------------------------------------
'A'      5            0.455        0        1          0.455
'B'      2            0.182        110      3          0.545
'C'      1            0.091        1110     4          0.364
'D'      1            0.091        1111     4          0.364
'R'      2            0.182        10       2          0.364

Średnia długość kodu: 2.091 bitów/znak
Kodowanie stałe:      3 bitów/znak
Oszczędność:          0.909 bitów/znak (30.3%)

Praktyczne zastosowania

1. Kompresja pliku tekstowego

Wyjście (fragment):

=== Kompresja pliku tekstowego ===

Oryginalny tekst:
  "TO BE OR NOT TO BE THAT IS THE QUESTION"

[... budowanie drzewa ...]

======================================================================
WYNIKI KOMPRESJI:
======================================================================

Rozmiar oryginalny:    312 bitów (39 bajtów)
Rozmiar skompresowany: 127 bitów
Narzut drzewa:         160 bitów
Całkowity rozmiar:     287 bitów (35.9 bajtów)

Współczynnik kompresji: 8.0%

2. Kompresja vs częstości znaków

Wyjście:

=== Wpływ rozkładu częstości na kompresję ===

Typ rozkładu                   Oryg (b)     Komp (b)     Kompresja %
======================================================================
Równomierny (1 znak)           80           26            67.5%
Równomierny (4 znaki)          80           84            -5.0%
Nierównomierny (A dominuje)    80           51            36.2%
Bardzo nierównomierny          80           43            46.2%
Całkowicie różnorodny          80          106           -32.5%

Wnioski: - Kompresja najlepsza dla nierównomiernych rozkładów - Dla równomiernych rozkładów może być ujemna (plik większy!)

Warianty algorytmu Huffmana

Adaptive Huffman Coding

Złożoność obliczeniowa

Analiza algorytmu

Operacja	Złożoność	Opis
Liczenie częstości	O(n)	Jeden przebieg przez tekst
Budowa drzewa	O(k log k)	k = liczba unikalnych znaków, operacje na kopcu
Generowanie kodów	O(k)	Przejście po drzewie
Kodowanie	O(n)	Jeden przebieg przez tekst
Dekodowanie	O(n × L)	L = max długość kodu
Całkowita	O(n + k log k)	Zazwyczaj k << n

gdzie: - n = długość tekstu - k = liczba unikalnych znaków

Podsumowanie

Kluczowe koncepcje

Pojęcie	Definicja
Kodowanie prefiksowe	Żaden kod nie jest prefiksem innego
Drzewo Huffmana	Reprezentacja kodowania jako drzewa binarnego
Strategia zachłanna	Łącz dwa najmniej częste symbole
Optymalnść	Minimalna średnia długość kodu

Właściwości algorytmu Huffmana

✅ Zalety: - Optymalne kodowanie prefiksowe - Prosty algorytm zachłanny - Wydajny (O(n + k log k)) - Dekodowanie jednoznaczne

✅ Kompresja najlepsza gdy: - Rozkład częstości nierównomierny - Niektóre symbole bardzo częste - Długie teksty

❌ Ograniczenia: - Wymaga przesłania drzewa - Słaba kompresja dla równomiernych rozkładów - Dla małych plików narzut drzewa może być duży

Zastosowania w praktyce

✅ Formaty kompresji: - DEFLATE (ZIP, GZIP) - JPEG (kodowanie AC/DC) - MP3 (kodowanie danych)

✅ Protokoły sieciowe: - HTTP/2 (HPACK - kompresja nagłówków) - WebSockets (kompresja wiadomości)

✅ Algorytmy pokrewne: - Arithmetic coding (lepsza kompresja) - LZW (Lempel-Ziv-Welch) - Run-Length Encoding

Co dalej?

Po opanowaniu kodowania Huffmana, następne tematy to:

Zaawansowane algorytmy kompresji:
LZ77, LZ78, LZW
Arithmetic Coding
Burrows-Wheeler Transform
Algorytmy grafowe zachłanne:
Dijkstra (najkrótsza ścieżka)
Prim i Kruskal (minimalne drzewo rozpinające)
Kolorowanie grafów
Teoria informacji:
Entropia Shannona
Granice kompresji
Kodowanie kanałów

Zadania praktyczne

Zadanie 1: Kompresja pliku

Zaimplementuj pełny kompresor i dekompresor plików używający kodowania Huffmana. Zapisz zakodowane dane i drzewo do pliku.

Zadanie 2: Porównanie z RLE

Porównaj kompresję Huffmana z Run-Length Encoding dla różnych typów danych (tekst, obrazy binarne).

Zadanie 3: Adaptive Huffman

Zaimplementuj adaptacyjną wersję algorytmu Huffmana, która aktualizuje drzewo podczas kodowania.

Zadanie 4: Canonical Huffman

Zaimplementuj Canonical Huffman Coding - wariant który wymaga przesłania tylko długości kodów, nie całego drzewa.

Zadanie 5: Analiza entropii

Oblicz entropię Shannona dla tekstu i porównaj ze średnią długością kodu Huffmana. Czy są blisko siebie?

Następna lekcja: Gratuluję ukończenia sekcji o algorytmach zachłannych!