Кодування Хаффмана: Будівництво оптимального префіксно-вільного коду

Визначте загальні символи короткими кодами

Основна ідея кодування Хаффмана, опублікована Давидом Хаффманом у 1952 році як курсова робота, не нова — модуль Морзе вже надає літеру 'E' один штрибок, оскільки це найпоширеніша англійська літера. Внесок Хаффмана полягав у розробці алгоритму, який знаходить доказово оптимальне призначення змінних за довжиною бінарного коду для фіксованого алфавіту, враховуючи частоту кожного символу, з урахуванням обмеження, що коди використовують ціле число біт.

Побудова дерева знизу вгору

Кожен символ починається як окреме маленьке дерево, мінливий вузол з вагомю відповідно до частоти, яке знаходиться у черзі пріоритетів, за ключем від ваги. Алгоритм потім повторює один простий крок, поки не залишиться лише одне дерево:

while more than one tree remains in the queue: a = pop the tree with the SMALLEST weight b = pop the tree with the next SMALLEST weight merge a and b under a new internal node new node's weight = weight(a) + weight(b) push the merged node back into the queue the last remaining tree is the Huffman tree

Після побудови дерева код для кожного символу просто є шляхом від кореня до його листка, читаючи 0 для «йти ліворуч» і 1 для «йти праворуч» на кожному кроці. Символи, які були об'єднані рано — найрідші з них — опиняються глибоко в дереві з довгими кодами; символи, які вижили багато раундів без об’єднання, знаходяться біля кореня з короткими кодами.

while more than one tree remains in the queue:
  a = pop the tree with the SMALLEST weight
  b = pop the tree with the next SMALLEST weight
  merge a and b under a new internal node
  new node's weight = weight(a) + weight(b)
  push the merged node back into the queue

the last remaining tree is the Huffman tree

Чому коди ніколи не стикаються: префіксно-вільні

Оскільки кожен символ живе на листі дерева, і жоден лист не є предком іншого листа, код жодного символу ніколи не може бути префіксом коду іншого символу. Ця властивість – префіксно-вільна (або, оманливо, «код з префіксами») – дозволяє декодеру читати бітопотік без роздільників між кодовими словами: він спускається від кореня по одному біту за раз, і в момент, коли він приземляється на лист, цей символ однозначний, без необхідності перегляду.

Почніть знову з кореня та повторіть для наступного символу.

Як близько до оптимального, насправді?

Теорема Шеннона про кодування джерела встановлює жорсткий нижній поріг середнього числа біт на символ, необхідного для кодування джерела: це ентропія, H = -Σ p_i·log₂(p_i), сумувана по ймовірності кожного символу p_i.

Хуффманівське кодування доведено як оптимальне серед кодів, які використовують ціле число біт на символ, і завжди потрапляє в межах одного біта від ентропії на символ — часто саме тоді, коли ймовірності випадково є степенями половини. Його одна структурна слабкість полягає у цьому ж обмеженні «цілого числа бітів»: символ із ймовірністю 0,99 ідеально повинен коштувати лише приблизно 0,0145 біта, але Хуффман ніколи не може дати його менше ніж 1 біт.

Для дуже спотворених розподілів ця різниця реальна, і арифметичне кодування та кодування діапазонів закривають її шляхом кодування всього послідовності символів у один спільний потоку дробів бітів замість одного коду слова на символ.

Де куди це застосовується

Кодування Хаффмана, або близький варіант, є етапентропійного кодування всередині DEFLATE (використовується в ZIP, gzip та PNG), JPEG та класичного MP3 формату — у всіх випадках раніше етап трубки виконує фактичне пошук шаблонів (LZ77 відповідність, DCT квантування) і передає результати, тепер сильно схилені до певних значень, на етап Хаффмана, який вичавлює залишок статистичної надмірності. Сучасні формати, як Brotli, Zstandard та новіші варіанти JPEG, переважно перейшли до кодування діапазонами або асиметричною числовою системою для цього остаточного етапу, щоб закрити проміжок у один біт, який не може забезпечити Хаффман.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Huffman Coding і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.