> huffman | optymalne | kody <
// Kodowanie Huffmana – optymalny algorytm bezprefiksowej kompresji
>> funkcje
Optymalne kody
Generuje możliwie najkrótszą średnią długość kodu dla zadanych częstotliwości.
Bez prefiksów
Żaden kod nie jest prefiksem innego, co pozwala na jednoznaczne dekodowanie.
Oparte na częstotliwości
Znaki częściej występujące otrzymują automatycznie krótsze kody.
>> informacje techniczne
Jak działa kodowanie Huffmana
Kodowanie Huffmana buduje od dołu do góry drzewo binarne. Zaczynamy od częstotliwości znaków, a następnie wielokrotnie łączymy dwa węzły o najmniejszej częstotliwości w węzeł nadrzędny, aż pozostanie tylko korzeń. Lewa gałąź odpowiada '0', prawa '1'. Znaki o wyższej częstotliwości dostają krótsze kody, co zapewnia optymalną kompresję dla danego rozkładu częstotliwości.
Przykład kodowania Huffmana
Text: "AABBBCCCC"
Frequencies:
A: 2
B: 3
C: 4
Tree Building:
1. Combine A(2) + B(3) = AB(5)
2. Combine C(4) + AB(5) = Root(9)
Tree:
Root(9)
/ \
C(4) AB(5)
/ \
A(2) B(3)
Codes:
C: 0
A: 10
B: 11
Encoded: 10 10 11 11 11 0 0 0 0
= 1010111111 0000
Dlaczego warto używać kodowania Huffmana?
- Prawie optymalny współczynnik kompresji
- Prosta implementacja
- Podstawa kompresji ZIP/JPEG
- Brak utraty danych
- Sprawdzona wydajność w praktyce
>> najczęściej zadawane pytania
Czym jest kodowanie Huffmana?
Kodowanie Huffmana to optymalny, bezprefiksowy algorytm kompresji zaproponowany przez Davida A. Huffmana w 1952 roku. Przypisuje znakom kody o zmiennej długości na podstawie ich częstotliwości; częstsze znaki otrzymują krótsze kody, dzięki czemu średnia długość kodu jest minimalna.
Dlaczego kod jest bezprefiksowy?
Kod jest bezprefiksowy, gdy żadne słowo kodowe nie jest prefiksem innego. Na przykład jeśli „A” ma kod „01”, to żaden inny znak nie może mieć kodu zaczynającego się od „01”. Dzięki temu strumień bitów można dekodować jednoznacznie, bez dodatkowych znaków rozdzielających.
Jak wydajne jest kodowanie Huffmana?
Kodowanie Huffmana osiąga optymalną kompresję dla danego rozkładu częstotliwości i zazwyczaj mieści się w 1 bicie od teoretycznej granicy entropii. Dla tekstu angielskiego kompresja często wynosi 60–70%, a im większe różnice w częstotliwości znaków, tym lepsze efekty.
Gdzie stosuje się kodowanie Huffmana?
Kodowanie Huffmana jest używane w kompresji obrazów JPEG, w archiwach ZIP (razem z LZ77 w DEFLATE), w audio MP3 i wielu innych formatach. Często występuje w połączeniu z innymi algorytmami – na przykład JPEG używa Huffmana po DCT i kwantyzacji, a ZIP po LZ77.