Math
Код Гаффмана
Черга частот перетворюється на дерево префіксного коду. Виберіть літеру, щоб побачити її біти; проходьте злиття покроково.
Що відбувається
Кожен крок об’єднує дві найменші ваги. Позначки 0 та 1 задають код на шляху від кореня до символу. Вибір літери виділяє весь цей шлях. L — середня довжина коду, H — ентропія. Хаффман мінімізує L серед двійкових префіксних кодів окремих символів і за L > H. Рівність досягається для ймовірностей 2^(-k). Обсяг у бітах не враховує таблицю кодів і заголовки файла.
Рівняння модуля
Рівняння побудова: зливаємо два найлегші вузли, n−1 разів; код символу є його шляхом від кореня: ліворуч 0, праворуч 1 L = Σ p(i)·l(i) (бітів на символ); H = −Σ p(i)·log₂ p(i); довжина коду l(i) є глибиною листка Крафт: кожен префіксний код має Σ 2^(−l(i)) ≤ 1, і кожен такий вектор є деревом; дерево Гаффмана повне, тому сума дорівнює рівно 1 H ≤ L < H + 1 завжди; L = H рівно тоді, коли кожне p(i) є степенем двійки оптимальність перевіряється порівнянням з перебором УСІХ допустимих за Крафтом векторів довжин - перебір нічого не знає про алгоритм однакові частоти: 2(n − 2^k) символів отримують довгий код, де 2^k є найбільшим степенем двійки, меншим за n частоти Фібоначчі 1, 1, 2, 3, 5, … дають найбільш перекошене дерево: довжини n−1, n−1, n−2, …, 1
