Math
Kod Huffmana
Uporządkowana kolejka częstości tworzy drzewo kodu prefiksowego. Wybierz symbol, aby prześledzić jego bity i kolejne połączenia.
Co się dzieje
Każdy krok łączy dwie najmniejsze wagi. Gałęzie 0 i 1 wyznaczają kod od korzenia do symbolu. Wybranie litery wyróżnia całą ścieżkę. L to średnia długość kodu, a H to entropia. Huffman minimalizuje L wśród binarnych kodów prefiksowych pojedynczych symboli, również gdy L > H. Równość zachodzi dla prawdopodobieństw 2^(-k). Liczba bitów nie uwzględnia tablicy kodów ani nagłówków.
Równania modułu
Równania budowa: łączymy dwa najlżejsze węzły, n−1 razy; kod symbolu to jego ścieżka od korzenia, w lewo 0, w prawo 1 L = Σ p(i)·l(i) (bitów na symbol); H = −Σ p(i)·log₂ p(i); długość kodu l(i) jest głębokością liścia Kraft: każdy kod prefiksowy spełnia Σ 2^(−l(i)) ≤ 1, a każdy taki wektor odpowiada drzewu; drzewo Huffmana jest pełne, więc suma wynosi dokładnie 1 H ≤ L < H + 1 zawsze; L = H dokładnie wtedy, gdy każde p(i) jest potęgą dwójki optymalność jest sprawdzana względem przeszukania WSZYSTKICH wektorów długości dopuszczalnych według Krafta - przeszukanie nic nie wie o algorytmie równe częstości: 2(n − 2^k) symboli dostaje długi kod, gdzie 2^k jest największą potęgą dwójki mniejszą od n częstości Fibonacciego 1, 1, 2, 3, 5, … dają najbardziej nierówne drzewo: długości n−1, n−1, n−2, …, 1
