Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Код Хаффмана



План:


Введення

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

На відміну від алгоритму Шеннона - Фано, алгоритм Хаффмана залишається завжди оптимальним і для вторинних алфавітів m 2 із більш ніж двома символами.

Цей метод кодування складається з двох основних етапів:

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

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

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

Класичний алгоритм Хаффмана на вході отримує таблицю частот зустрічальності символів у повідомленні. Далі на підставі цієї таблиці будується дерево кодування Хаффмана (Н-дерево). [1]

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

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

15 7 6 6 5
А Б В Г Д

Цей процес можна представити як побудова дерева, коріння якого - символ з сумою ймовірностей об'єднаних символів, що вийшов при об'єднанні символів з ​​останнього кроку, його n 0 нащадків - символи з попереднього кроку і т. д.

Щоб визначити код для кожного із символів, що входять в повідомлення, ми повинні пройти шлях від листа дерева, відповідає поточному символу, до його кореня, накопичуючи біти при переміщенні по гілках дерева (перша гілка в дорозі відповідає молодшому біту). Отримана таким чином послідовність бітів є кодом даного символу, записаним у зворотному порядку.

Для даної таблиці символів коди Хаффмана будуть виглядати наступним чином.

А Б В Г Д
0 100 101 110 111

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

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

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


2. Адаптивне стиск

Адаптивне стиск дозволяє не передавати модель повідомлення разом з ним самим і обмежитися одним проходом за повідомленням як при кодуванні, так і при декодуванні.

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

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

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

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

Щоб зберегти упорядкованість дерева кодування, алгоритм працює в такий спосіб. Нехай новий збільшена вага вузла дорівнює W +1. Тоді починаємо рухатися по списку у бік збільшення ваги, поки не знайдемо останній вузол з вагою W. Переставимо поточний і знайдений вузли між собою в списку, відновлюючи таким чином порядок в дереві (при цьому батьки кожного з вузлів теж зміняться). На цьому операція перестановки закінчується.

Після перестановки операція збільшення ваги вузлів продовжується далі. Наступний вузол, вага якого буде збільшений алгоритмом, - це новий батько вузла, збільшення ваги якого викликало перестановку.


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

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

Можна довести, що максимальну довжину код Хаффмана для повідомлень з одним і тим же вхідним алфавітом матиме, якщо частоти символів утворює послідовність Фібоначчі. Повідомлення з частотами символів, рівними числам Фібоначчі до Fib (18), - це відмінний спосіб протестувати роботу програми стиснення по Хаффману.


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

Беручи до уваги сказане вище, алгоритм поновлення дерева Хаффмана повинен бути змінений таким чином: при збільшенні ваги потрібно перевіряти його на досягнення допустимого максимуму. Якщо ми досягли максимуму, то необхідно "масштабувати" вагу, зазвичай розділивши вагу листя на ціле число, наприклад, 2, а потім перерахувавши вага всіх інших вузлів.

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

Правильно організоване дерево Хаффмана після масштабування може мати форму, значно відрізняється від вихідної. Це відбувається тому, що масштабування призводить до втрати точності нашої статистики. Але зі збором нової статистики наслідки цих "помилок" практично сходять нанівець. Масштабування ваги - досить дорога операція, оскільки вона призводить до необхідності заново будувати все дерево кодування. Але, так як необхідність в ній виникає відносно рідко, то з цим можна змиритися.

Виграш від масштабування

Масштабування ваги вузлів дерева через певні інтервали дає несподіваний результат. Незважаючи на те, що при масштабуванні відбувається втрата точності статистики, тести показують, що воно призводить до кращих показників стиснення, ніж якщо б масштабування відкладалося. Це можна пояснити тим, що поточні символи стисливого потоку більше "схожі" на своїх близьких попередників, ніж на тих, які зустрічалися набагато раніше. Масштабування призводить до зменшення впливу "давніх" символів на статистику і до збільшення впливу на неї "недавніх" символів. Це дуже складно виміряти кількісно, ​​але, в принципі, масштабування робить позитивний вплив на ступінь стиснення інформації. Експерименти з масштабуванням в різних точках процесу стиснення показують, що ступінь стиснення сильно залежить від моменту масштабування ваги, але не існує правила вибору оптимального моменту масштабування для програми, орієнтованої на стиск будь-яких типів інформації.


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

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

Примітки

  1. Д. Мастрюков. Монитор 7-8.93 - masters.donntu.edu.ua/2005/fvti/kozlenko/library/mastrukov_1993_huffman.pdf

Література

  • Томас Х. Кормен, Чарльз І. Лейзерсон, Рональд Л. Рівестом, Кліффорд Штайн. Алгоритми: побудова й аналіз = Introduction to Algorithms. - 2-ге вид. - М .: Вільямс, 2006. - 1296 с. - ISBN 0-07-013151-1
  • Д. Селомон. Стиснення даних, зображення і звуку. - М .: Техносфера, 2004. - 368 с. - 3000 екз. - ISBN 5-94836-027-X
  • Ананій В. Левітін. Глава 9. Жадібні методи: Алгоритм Хаффмана / / Алгоритми: введення в розробку й аналіз = Introduction to The Design and Analysis of Aigorithms. - М .: Вільямс, 2006. - С. 392-398. - ISBN 0-201-74395-7

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Код
Код
QR-код
Код (значення)
ZIP-код
Штриховий код
Код ІАТА
Код Грея
Код INSEE
© Усі права захищені
написати до нас