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

 

 

Статистичне кодування Хаффмана співставляє вхідним символам, представленим ланцюжками бітів однакової довжини (наприклад, восьмибітовими байтами), ланцюжки бітів змінної довжини. Довжина коду для символу пропорційна двійковому логарифму його частоти, взятому із протилежним знаком. Це кодування є префіксним, що дозволяє легко його декодувати однопрохідним алгоритмом. Префіксний код зручно відображати у вигляді двійкового дерева, в якого символи знаходяться в листях, а дуги відмічені 0 або 1. Тоді код символу можна задавати як шлях від кореня дерева до листка, який містить цей символ.

При використанні адаптивного кодування Хаффмана необхідне постійне коректування дерева у відповідності зі зміною статистики вхідного потоку. При реалізації це звичайно потребує значних витрат на перебалансування кодового дерева у відповідності з новими частотами символів на кожному кроці. Стиснення інформації виконується за два проходи:

Під час першого проходу оцінюються частоти появи символів в початковому файлі.

Під час другого проходу виконується представлення цих символів префіксними кодами змінної довжини.

Як це реалізується на практиці розглянемо на прикладі деякого файлу. Після першого етапу отримана така інформація про частоти появи символів в файлі:

Об'єм файла 180 байт (1440 біт). Він складається з шести різних символів, які зустрічаються в файлі від 7 до 61 раза.

На наступному етапі необхідно закодувати символи у відповідності з частотою їх повторення. Цей процес пояснює рис. 2. 1. Виберемо із таблиці два символи з найменшою частотою появи у вхідному файлі і утворимо з них вузол. Вміст вузла – це сума обох частот символів (19+7=26). Далі знову знаходимо два символи з найменшою частотою. При цьому частоти 19 і 7 вже не враховуються, але в пошуку символів з найменшими частотами бере участь утворений вузол. Разом з символом «H» перший вузол створює наступний вузол (26+23=49).

Якщо проводити вибір символів за даною схемою, то колись структура повинна закінчитись. Для останнього вузла сума вже не записується, оскільки порівняння закінчилось. Цей останній вузол називається коренем, через який можливий вхід в дерево кодування.

 

 

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

Символи, які найбільш часто зустрічаються («U» і «F») отримали короткі 2-бітові кодові комбінації, а ті, що найрідше («M») – 4-бітові кодові комбінації. Ступінь стискання показаний в табл. 2. 1: початкові 1440 біт файлу стиснулись до 435 біт, що відповідає ступеню стискання 31%.

 

 

На останньому етапі програма оброблює файл і замінює кожний символ на його код. Також вона записує кодове дерево у файл, оскільки тільки за допомогою цього дерева можна знову декодувати файл. Ступінь стискання погіршується через те, що і кодове дерево потребує додаткової пам'яті.

Таким чином, алгоритм статистичного кодування способом Хаффмана буде складатись з таких етапів:

1. Визначення кількості повторювання кожного символу.

2. Побудова двійкового дерева.

3. Побудова кодової послідовності для кожного символу.

4. Заміна символів заданого файлу відповідними кодовими послідовностями і запис результату.

Недоліком кодування Хаффмана є залежність ступеня стискання від близькості ймовірностей символів до від'ємних степенів двійки, а також складна апаратурна реалізація, яка пов’язана з необхідністю запам’ятовування кадру зображення, тобто кодування виконується за два проходи.

 

 

1. Створити таблицю частот зустрічає мості різних 20 символів, перша частина з яких літери з прізвища студента.

2. Побудувати двійкове дерево

3. Визначити коди переходів по дереву

4. Оцінити ступінь стиснення даних

5. Сформувати звіт