UK 
EnglishТипова
Polski🌳 Кодування Гаффмана
Побудуйте оптимальний префіксний код, послідовно зливаючи два найрідші символи. Дивіться, як росте дерево, зчитуйте коди 0/1 та порівнюйте біти Гаффмана з фіксованою довжиною й межею ентропії.
Про кодування Гаффмана
Кодування Гаффмана — це алгоритм стиснення даних без втрат, винайдений Девідом А. Гаффманом 1952 року, який призначає коротші двійкові коди частішим символам і довші коди рідкісним, утворюючи оптимальний префіксний код. Він будує двійкове дерево знизу вгору: послідовно зливає два вузли з найменшими частотами з мінімальної пріоритетної черги, доки не залишиться єдиний корінь, а потім зчитує мітки шляху 0/1, щоб отримати код кожного символу. Алгоритм доведено оптимальний серед посимвольних кодів і лежить в основі таких форматів, як DEFLATE (застосовується в ZIP і PNG), етапу ентропійного кодування JPEG та MP3.
У цій симуляції можна ввести будь-який текст, спостерігати за заповненням таблиці частот і покроково проходити кожну операцію злиття під час росту дерева. Панель праворуч показує призначений код кожного символу, загальну довжину бітів Гаффмана та порівнює її з фіксованим 8-бітним ASCII-кодуванням і нижньою межею ентропії Шеннона.
Поширені запитання
Як кодування Гаффмана гарантує оптимальний префіксний код?
Жадібний алгоритм Гаффмана на кожному кроці зливає два вузли з найменшою частотою; це відповідає принципу, що символи, які трапляються найчастіше, повинні мати найкоротші шляхи від кореня до листка. Формальний аргумент обміну доводить, що жодне інше призначення довжин кодів цьому розподілу частот не може досягти коротшої очікуваної довжини коду, тож ця схема є оптимальною серед усіх однозначно декодовних символьних кодів.
Яка середня довжина коду, що виробляє кодування Гаффмана?
Очікувана довжина коду L задовольняє H(X) ≤ L < H(X) + 1, де H(X) = −∑ pi log2 pi — ентропія Шеннона джерела. У найгіршому випадку (усі символи рівноймовірні) Гаффман перевищує ентропію лише на один біт на символ. Для джерел із сильно нерівномірними частотами середня довжина коду може бути дуже близькою до ентропії.
Чому коди Гаффмана мають бути префіксними?
Префіксний код гарантує, що жодне кодове слово не є префіксом іншого, тож декодер може однозначно зчитувати біти з потоку без роздільників. Оскільки Гаффман призначає коди за шляхами від листка до кореня в двійковому дереві, листки ніколи не є предками одне одного, що автоматично гарантує префіксну властивість.
Які структури даних потрібні для ефективної побудови дерева Гаффмана?
Стандартна реалізація використовує мінімальну купу (пріоритетну чергу), впорядковану за частотою вузла. Кожна з n операцій злиття коштує O(log n) для вставки й вилучення з купи, що дає загальний час побудови O(n log n). Для алфавіту з 256 символів це практично миттєво.
Чим кодування Гаффмана відрізняється від арифметичного кодування?
Гаффман призначає ціле число бітів на символ, тож не може подолати межу в один біт на символ для дуже ймовірних символів. Арифметичне кодування кодує все повідомлення як єдиний дріб, досягаючи очікуваних довжин, як завгодно близьких до ентропії, навіть коли ймовірність окремого символу перевищує 0,5. Однак арифметичне кодування обчислювально складніше і історично підпадало під патентні обмеження.
Чи використовується кодування Гаффмана в сучасних форматах файлів?
Так. DEFLATE — ядро стиснення в ZIP, gzip і PNG — поєднує пошук збігів LZ77 із кодуванням Гаффмана. JPEG використовує кодування Гаффмана (або опційно арифметичне) після етапу квантування DCT. Старіший формат PKZIP і веб-алгоритм стиснення Brotli також побудовані на схемах родини Гаффмана.
Що відбувається, коли два вузли мають однакову частоту під час побудови дерева?
Нічия розв'язується довільно; різні стратегії розв'язання нічиї дають різні форми дерева, але завжди досягають однакової оптимальної очікуваної довжини коду. На практиці стабільні або канонічні реалізації Гаффмана задають детерміновне правило розв'язання нічиї, щоб кодувальник і декодувальник могли відтворити те саме дерево з компактного заголовка.
Що таке канонічний код Гаффмана?
Канонічний код перепризначає кодові слова так, щоб коди однакової довжини йшли послідовними цілими числами, дозволяючи декодеру зберігати лише довжини кодів, а не все дерево. Це суттєво зменшує накладні витрати заголовка: замість серіалізації дерева кодувальник передає лише довжини символів, заощаджуючи кілобайти в таких форматах, як шар zlib у PNG.
Чи може кодування Гаффмана досягти коефіцієнта стиснення понад 8× порівняно з ASCII?
Лише якщо джерело має дуже низьку ентропію — наприклад, двійковий файл, що складається майже виключно з одного значення байта. У цьому крайньому випадку код Гаффмана для цього символу може становити 1 біт, даючи до 8-кратного зменшення порівняно з 8-бітним ASCII. Для природного англійського тексту коефіцієнти стиснення зазвичай становлять 1,5–2,5× лише за допомогою Гаффмана.
Що таке адаптивне (динамічне) кодування Гаффмана?
Адаптивне кодування Гаффмана оновлює таблицю частот і перебудовує (або поступово коригує) дерево під час обробки кожного символу, усуваючи потребу в двопрохідному алгоритмі чи збереженому заголовку. Алгоритми FGK і Віттера підтримують властивість братів і сестер (sibling property), що дозволяє інкрементальні оновлення за O(log n), уможливлюючи однопрохідне потокове стиснення.