Алгоритм Хаффмана

Алгоритм Хаффмана - адаптивний жадібний алгоритм оптимального префіксного кодування алфавіту з мінімальною надмірністю. Був розроблений в 1952 році аспірантом Массачусетського технологічного інституту Девідом Хаффманом при написанні ним курсової роботи. В даний час використовується в багатьох програмах стиснення даних. На відміну від алгоритму Шеннона - Фано, алгоритм Хаффмана залишається завжди оптимальним і для вторинних алфавітів з більш ніж двома символами. Цей метод кодування складається з двох основних етапів:

• Побудова оптимального кодового дерева.
• Побудова відображення код-символ на основі побудованого дерева.

Кодування Хаффмана

Один з перших алгоритмів ефективного кодування інформації був запропонований Д. А. Хаффманом в 1952 році. Ідея алгоритму полягає в наступному: знаючи ймовірності входження символів в повідомленні, можна описати процедуру побудови кодів змінної довжини, що складаються з цілого кількості бітів. Символам з більшою ймовірністю присвоюються більш короткі коди. Коди Хаффмана володіють властивістю префіксності, що дозволяє однозначно їх декодувати. Класичний алгоритм Хаффмана на вході отримує таблицю частот входженн символів у повідомленні. Далі на підставі цієї таблиці будується дерево кодування Хаффмана (Н-дерево).

• Символи вхідного алфавіту утворюють список вільних вузлів. Кожен лист має вагу, який може дорівнювати або ймовірності, або кількості входжень символу в стиснутому повідомленні.
• Вибираються два вільних вузла дерева з найменшими вагами.
• Створюється їх батько з вагою, рівною їх сумарній вазі.
• Батько додається в список вільних вузлів, а двоє його дітей (нащадків) видаляються з цього списку.
• Одній дузі, котра виходить з батька, ставиться у відповідність біт 1, іншій - біт 0.
• Кроки, починаючи з другого, повторюються до тих пір, поки в списку вільних вузлів не залишиться тільки один вільний вузол. Він і буде вважатися коренем дерева.

Припустимо, у нас є наступна таблиця частот:

15	7	6	6	5
А	Б	В	Г	Д

Цей процес можна представити як побудова дерева, коріння якого - символ з сумою ймовірностей об'єднаних символів, що вийшов при об'єднанні символів з останнього кроку, його n0 нащадків - символи з попереднього кроку і т. д. Щоб визначити код для кожного із символів, що входять до повідомлення, ми повинні пройти шлях від листа дерева, відповідного цьому символу, до кореня дерева, накопичуючи біти при переміщенні по гілках дерева. Отримана таким чином послідовність бітів є кодом даного символу, записаним у зворотному порядку. Для даної таблиці символів коди Хаффмана будуть виглядати наступним чином.

А	Б	В	Г	Д
0	100	101	110	111

Оскільки жоден з отриманих кодів не є префіксом іншого, вони можуть бути однозначно декодовані при читанні їх з потоку. Крім того, найбільш частий символ повідомлення А закодований найменшою кількістю біт, а найбільш рідкісний символ Д - найбільшим. При цьому загальна довжина повідомлення, що складається з наведених у таблиці символів, складе 87 біт (у середньому 2,2308 біта на символ). При використанні рівномірного кодування загальна довжина повідомлення склала б 117 біт (рівно 3 біта на символ). Зауважимо, що ентропія джерела, незалежним чином породжує символи з зазначеними частотами складає ~ 2,1858 біта на символ, тобто надмірність побудованого для такого джерела коду Хаффмана, що розуміється, як різниця середнього числа біт на символ від ентропії, становить менше 0,05 біт на символ. Класичний алгоритм Хаффмана має ряд істотних недоліків. По-перше, для відновлення вмісту стиснутого повідомлення декодер повинен знати таблицю частот, якою користувався кодер. Отже, довжина стиснутого повідомлення збільшується на довжину таблиці частот, яка повинна надсилатися попереду даних, що може звести нанівець всі зусилля зі стиснення повідомлення. Крім того, необхідність наявності повної частотної статистики перед початком власне кодування вимагає двох проходів за повідомленням: одного для побудови моделі повідомлення (таблиці частот і Н-дерева), другий для себе власне кодування. По-друге, надмірність кодування звертається в нуль лише в тих випадках, коли ймовірності кодованих символів є зворотними ступенями числа 2. По-третє, для джерела з ентропією, що не перевищує 1 (наприклад, для двійкового джерела), безпосереднє застосування коду Хаффмана безглуздо.

Адаптивне стиснення

Адаптивне стиснення дозволяє не передавати модель повідомлення разом з ним самим і обмежитися одним проходом за повідомленням як при кодуванні, так і при декодуванні. У створенні алгоритму адаптивного кодування Хаффмана найбільші складнощі виникають при розробці процедури ОбновітьМодельСімволом (); можна було б просто вставити всередину цієї процедури повне побудова дерева кодування Хаффмана. У результаті ми отримали б самий повільний у світі алгоритм стиснення, тому що побудова Н-дерева - це занадто велика робота і проводити її при обробці кожного символу нерозумно. На щастя, існує спосіб модифікувати вже існуюче Н-дерево так, щоб відобразити обробку нового символу. Оновлення дерева при зчитуванні чергового символу повідомлення складається з двох операцій. Перша - збільшення ваги вузлів дерева. Спочатку збільшуємо вагу листа, відповідного вважалося символом, на одиницю. Потім збільшуємо вагу батька, щоб привести його у відповідність з новими значеннями ваги у дітей. Цей процес продовжується до тих пір, поки ми не доберемося до коріння дерева. Середнє число операцій збільшення ваги одно середній кількості бітів, необхідних для того, щоб закодувати символ. Друга операція - перестановка вузлів дерева - потрібно тоді, коли збільшення ваги вузла призводить до порушення властивості впорядкованості, тобто тоді, коли збільшена вага вузла став більше, ніж вага наступного по порядку вузла. Якщо і далі продовжувати обробляти збільшення ваги, рухаючись до кореня дерева, то наше дерево перестане бути деревом Хаффмана. Щоб зберегти впорядкованість дерева кодування, алгоритм працює наступним чином. Нехай новий збільшена вага вузла дорівнює W +1. Тоді починаємо рухатися за списком у бік збільшення ваги, поки не знайдемо останній вузол з вагою W. Переставимо поточний і знайдений вузли між собою в списку, відновлюючи таким чином порядок в дереві. (При цьому батьки кожного з вузлів теж зміняться.) На цьому операція перестановки закінчується. Після перестановки операція збільшення ваги вузлів продовжується далі. Наступний вузол, вага якого буде збільшений алгоритмом, - це новий батько вузла, збільшення ваги якого викликало перестановку.

Переповнення

У процесі роботи алгоритму стиснення вага вузлів у дереві кодування Хаффмана неухильно зростає. Перша проблема виникає тоді, коли вага кореня дерева починає перевершувати місткість осередку, в якому він зберігається. Як правило, це 16-бітове значення і, отже, не може бути більше, ніж 65535. Друга проблема, яка заслуговує ще більшої уваги, може виникнути значно раніше, коли розмір найдовшого коду Хаффмана перевершує місткість осередку, який використовується для того, щоб передати його у вихідний потік. Декодеру все одно, якої довжини код він декодує, оскільки він рухається зверху вниз по дереву кодування, вибираючи з вхідного потоку по одному біту. Кодер же повинен починати від аркуша дерева і рухатися вгору до кореня, збираючи біти, які потрібно передати. Зазвичай це відбувається зі змінною типу «ціле», і, коли довжина коду Хаффмана перевершує розмір типу «ціле» в бітах, настає переповнення. Можна довести, що максимальну довжину код Хаффмана для повідомлень з одним і тим же вхідним алфавітом буде мати, якщо частоти символів утворює послідовність Фібоначчі. Повідомлення з частотами символів, рівними числах Фібоначчі до Fib (18), - це відмінний спосіб протестувати роботу програми стиснення по Хаффману.

Масштабування ваг вузлів дерева Хаффмана

Беручи до уваги сказане вище, алгоритм оновлення дерева Хаффмана повинен бути змінений таким чином: при збільшенні ваги потрібно перевіряти його на досягнення допустимого максимуму. Якщо ми досягли максимуму, то необхідно «масштабувати» вагу, зазвичай розділивши вага листя на ціле число, наприклад, 2, а потім перерахувавши вага всіх інших вузлів. Однак при розподілі ваги навпіл виникає проблема, пов'язана з тим, що після виконання цієї операції дерево може змінити свою форму. Пояснюється це тим, що ми ділимо цілі числа і за розподілі відкидаємо дробову частину. Правильно організоване дерево Хаффмана після масштабування може мати форму, значно відрізняється від вихідної. Це відбувається тому, що масштабування призводить до втрати точності нашої статистики. Але зі збором нової статистики наслідки цих «помилок» практично сходять нанівець. Масштабування ваги - досить дорога операція, оскільки вона призводить до необхідності заново будувати все дерево кодування. Але, оскільки необхідність у ній виникає відносно рідко, то з цим можна змиритися. Виграш від масштабування Масштабування ваги вузлів дерева через певні інтервали дає несподіваний результат. Незважаючи на те, що при масштабуванні відбувається втрата точності статистики, тести показують, що воно призводить до кращих показників стиснення, ніж якщо б масштабування відкладалося. Це можна пояснити тим, що поточні символи стисливого потоку більше «схожі» на своїх близьких попередників, ніж на тих, які зустрічалися набагато раніше. Масштабування призводить до зменшення впливу «давніх» символів на статистику і до збільшення впливу на неї «недавніх» символів. Це дуже складно виміряти кількісно, але, в принципі, масштабування робить позитивний вплив на ступінь стиснення інформації. Експерименти з масштабуванням в різних точках процесу стиснення показують, що ступінь стиснення сильно залежить від моменту масштабування ваги, але не існує правила вибору оптимального моменту масштабування для програми, орієнтованої на стиск будь-яких типів інформації.

Застосування

Стиснення даних за Хаффману застосовується при стисканні фото-і відеозображень (JPEG, стандарти стиснення MPEG), в архіваторах (PKZIP, LZH та ін), в протоколах передачі даних MNP5 і MNP7.