Кодова дерево (дерево кодування Хаффмана, Н-дерево) - це бінарне дерево. у якого:
- листя позначені символами, для яких розробляється кодування;
- вузли (в тому числі корінь) позначені сумою ймовірностей появи всіх символів, відповідних листів поддерева. коренем якого є відповідний вузол.
Метод Хаффмана на вході отримує таблицю частот зустрічальності символів в початковому тексті. Далі на підставі цієї таблиці будується дерево кодування Хаффмана.
Алгоритм побудови дерева Хаффмана.
Крок 1. Символи вхідного алфавіту утворюють список вільних вузлів. Кожен лист має вагу. який може дорівнювати або ймовірності, або кількістю входжень символу в стискається текст.
Крок 2. Вибираються два вільних вузла дерева з найменшими вагами.
Крок 3. Створюється їх батько з вагою, рівним їх сумарному вазі.
Крок 4. Батько додається в список вільних вузлів, а двоє його дітей видаляються з цього списку.
Крок 5. Однією дузі. виходить з батьків, ставиться у відповідність біт 1, інший - біт 0.
Крок 6. Повторюємо кроки, починаючи з другого, до тих пір, поки в списку вільних вузлів не залишиться тільки один вільний вузол. Він і буде вважатися коренем дерева.
Існує два підходи до побудови кодового дерева: від кореня до листя і від листя до кореня.
Приклад побудови кодового дерева. Нехай задана вихідна послідовність символів:
Її вихідний обсяг дорівнює 20 байт (160 біт). Згідно з наведеними на рис. 41.1 даними (таблиця ймовірності появи символів, кодове дерево і таблиця оптимальних префіксних кодів) закодована вихідна послідовність символів буде виглядати наступним чином:
Отже, її обсяг буде дорівнює 42 біта. Коефіцієнт стиснення приблизно дорівнює 3,8.
Мал. 41.1. Створення оптимальних префіксних кодів
Класичний алгоритм Хаффмана має один істотний недолік. Для відновлення вмісту стиснутого тексту при декодуванні необхідно знати таблицю частот, яку використовували при кодуванні. Отже, довжина стиснутого тексту збільшується на довжину таблиці частот, яка повинна надсилатися попереду даних, що може звести нанівець всі зусилля зі стиснення даних. Крім того, необхідність наявності повної частотної статистики перед початком власне кодування вимагає двох проходів по тексту: одного для побудови моделі тексту (таблиці частот і дерева Хаффмана), іншого для власне кодування.
Приклад 2. Програмна реалізація алгоритму Хаффмана за допомогою кодового дерева.
Для здійснення декодування необхідно мати кодове дерево. яке доводиться зберігати разом із стисненими даними. Це призводить до деякого незначного збільшення обсягу стислих даних. Використовуються найрізноманітніші формати, в яких зберігають це дерево. Звернемо увагу на те, що вузли кодового дерева є порожніми. Іноді зберігають не саме дерево. а вихідні дані для його формування, тобто відомості про можливості появи символів або їх кількостях. При цьому процес декодування передує побудовою нового кодового дерева, яке буде таким же, як і при кодуванні.
Ключові терміни
Стиснення даних - це процес, що забезпечує зменшення обсягу даних шляхом скорочення їх надмірності.
Стиснення без втрат (повністю оборотне) - це метод стиснення даних, при якому раніше закодована порція даних відновлюється після їх розпакування повністю без внесення змін.
Стиснення з втратами - це метод стиснення даних, при якому для забезпечення максимального ступеня стиснення вихідного масиву даних частина його даних відкидається.
Алгоритм стиснення даних (алгоритм архівації) - це алгоритм. який усуває надмірність записи даних.
Алфавіт коду - це безліч всіх символів вхідного потоку.
Кодовий символ - це найменша одиниця даних, що підлягає стисненню.
Кодове слово - це послідовність кодових символів з алфавіту коду.
Токен - це одиниця даних, що записується в стислий потік деяким алгоритмом стиснення.
Фраза - це фрагмент даних, що поміщається в словник для подальшого використання в стисненні.
Кодування - це процес стиснення даних.
Декодування - це зворотний кодування процес, при якому здійснюється відновлення даних.
Ставлення стиснення - це величина для позначення ефективності методу стиснення, що дорівнює відношенню розміру вихідного потоку до розміру вхідного потоку.
Коефіцієнт стиснення - це величина, зворотна відношенню стиснення.
Середня довжина кодового слова - це величина, яка обчислюється як зважена можливостями сума довжин всіх кодових слів.
Статистичні методи - це методи стиснення, які присвоюють коди змінної довжини символам вхідного потоку, причому більш короткі коди присвоюються символам або групам символів, які мають велику ймовірність появи у вхідному потоці.
Словникове стиснення - це методи стиснення, що зберігають фрагменти даних в деякій структурі даних, званої словником.
Хаффмановское кодування (стиснення) - це метод стиснення, привласнює символам алфавіту коди змінної довжини грунтуючись на можливостях появи цих символів.
Префіксний код - це код, в якому ніяке кодове слово не є префіксом будь-якого іншого кодового слова.
Оптимальний префіксний код - це префіксний код. має мінімальну середню довжину.
Кодова дерево (дерево кодування Хаффмана, Н-дерево) - це бінарне дерево. у якого: листя позначені символами, для яких розробляється кодування; вузли (в тому числі корінь) позначені сумою ймовірностей появи всіх символів, відповідних листів поддерева. коренем якого є відповідний вузол.
короткі підсумки
- Стиснення даних є процесом, що забезпечує зменшення обсягу даних шляхом скорочення їх надмірності.
- Стиснення даних може відбуватися з втратами і без втрат.
- Ставлення стиснення характеризує ступінь стиснення даних.
- Існують два основних способи проведення стиснення: статистичні методи і словникове стиснення.
- Алгоритм Хаффмана відноситься до статистичних методів стиснення даних.
- Ідея алгоритму Хаффмана полягає в наступному: знаючи ймовірності входження символів у вихідний текст, можна описати процедуру побудови кодів змінної довжини, що складаються з цілого кількості бітів.
- Коди Хаффмана мають унікальний префікс, що і дозволяє однозначно їх декодувати, незважаючи на їх зміну довжину.
- Алгоритм Хаффмана універсальний, його можна застосовувати для стиснення даних будь-яких типів, але він малоефективний для файлів малих розмірів.
- Класичний алгоритм Хаффмана на основі кодового дерева вимагає зберігання кодового дерева, що збільшує його трудомісткість.