Теоретична частина
алгоритм Хаффмена
Один з перших алгоритмів ефективного кодування інформації був запропонований Хаффменом в 1952 році. Цей алгоритм став базою для великої кількості програм стиснення інформації. Наприклад, кодування по Хаффмену використовується в програмах стиснення ARJ. ZIP. RAR. в алгоритмі стиснення графічних зображень з втратами JPEG. а також вбудовано в сучасні факс-апарати.
Ефективне кодування по Хаффмену полягає в поданні найбільш ймовірних (часто зустрічаються) букв двійковими кодами найменшої довжини, а менш ймовірних - кодами більшої довжини (якщо все кодові слова меншої довжини вже вичерпані). Це робиться таким чином, щоб середня довжина коду на букву вихідного повідомлення була мінімальною.
До початку кодування повинні бути відомі ймовірності появи кожної літери, з яких буде складатися повідомлення. На підставі цієї таблиці ймовірностей будується кодове дерево Хаффмена, за допомогою якого проводиться кодування букв.
Побудова кодового дерева Хаффмена
Для ілюстрації алгоритму Хаффмена розглянемо графічний спосіб побудови дерева кодування. Перед цим введемо деякі визначення, прийняті для опису алгоритму Хаффмена з використанням цього способу.
Граф - сукупність безлічі вузлів і безлічі дуг, спрямованих від одного вузла до іншого.
Дерево - граф, що володіє наступними властивостями:- ні в один з вузлів не входить більше однієї дуги;
- тільки в один вузол не входить жодної дуги (цей вузол називається коренем дерева);
- переміщаючись по дугам від кореня, можна потрапити в будь-який вузол.
Лист дерева - вузол, з якого не виходить жодної дуги. У парі вузлів дерева, з'єднаних між собою дугою, той, з якого вона виходить, називається батьком. інший же - дитиною.
Два вузла називаються братами. якщо мають одного і того ж батька.
Двійкове дерево - дерево, у якого з усіх вузлів, крім листя, виходить рівно по дві дуги.
Дерево кодування Хаффмена - бінарне дерево, у якого кожен вузол має вагу. і при цьому вага батька дорівнює сумарному вазі його дітей.
Алгоритм побудови дерева кодування Хаффмена такий:- Букви вхідного алфавіту утворюють список вільних вузлів майбутнього дерева кодування. Кожен вузол в цьому списку має вагу, рівний ймовірності появи відповідної букви в повідомленні.
- Вибираються два вільних вузла дерева з найменшими вагами. Якщо є більше двох вільних вузлів з найменшими вагами, то можна брати будь-яку пару.
- Створюється їх батько з вагою, рівним їх сумарному вазі.
- Батько додається в список вільних вузлів, а двоє його дітей видаляються з цього списку.
- Однією дузі, що виходить з вузла-батька, ставиться у відповідність біт 1, інший - 0.
- Пункти 2, 3, 4, 5 повторюються до тих пір, поки в списку вільних вузлів не залишиться тільки один вузол. Цей вузол буде коренем дерева. Його вага виходить рівним одиниці - сумарною ймовірності всіх букв повідомлення.
Тепер, рухаючись по кодовому дереву зверху вниз і послідовно виписуючи виконавчі цифри, відповідні дуг, можна отримати коди букв вхідного алфавіту.
Для прикладу розглянемо побудову дерева кодування Хаффмена для наведеного в таблиці 1 алфавіту з восьми букв.
Побудова дерева починаємо зі списку листя (див. Рис. 1) і виконуємо по кроках.
Мал. 1. Список вільних вузлів-листя.
На першому кроці з листя дерева вибираються два з найменшими вагами z7 і z8. Вони приєднуються до вузла-батькові, вага якого встановлюється в 0.04 +0.02 = 0.06. Потім вузли z7 і z8 видаляються зі списку вільних. Вузол z7 відповідає гілки 0 батька, вузол z8 - гілки 1. Дерево кодування після першого кроку наведено на рис. 2.
Мал. 2. Дерево кодування Хаффмена після першого кроку.
На другому кроці "найлегшій" парою виявляється лист z6 і вільний вузол (z7 + z8). Для них створюється батько з вагою 0.16. Вузол z6 відповідає гілки 0 батька, вузол (z7 + z8) - гілки 1. На даному етапі дерево кодування виглядає наступним чином (див. Рис. 3).
Мал. 3. Дерево кодування Хаффмена після другого кроку.
На третьому кроці найменші ймовірності мають z5. z4. z3 і вільний вузол (z6 + z7 + z8). Таким чином, на даному етапі можна створити батька для z5 і (z6 + z7 + z8) з вагою 0.26. отримавши при цьому дерево кодування, представлене на рис. 4. Зверніть увагу, що в даній ситуації можливі декілька варіантів з'єднання вузлів з найменшими вагами. При цьому всі такі варіанти будуть правильними, хоча і можуть привести до різних наборів кодів, які, втім, будуть володіти однаковою ефективністю для заданого розподілу ймовірностей.
Мал. 4. Дерево кодування Хаффмена після третього кроку.
На четвертому кроці "найлегшій" парою виявляються листя z3 і z4. Дерево кодування Хаффмена наведено на рис. 5.
Мал. 5. Дерево кодування Хаффмена після четвертого кроку.
На п'ятому кроці вибираємо вузли з найменшими вагами 0.22 і 0.20. Дерево кодування Хаффмена після п'ятого кроку наведено на рис. 6.
Мал. 6. Дерево кодування Хаффмена після п'ятого кроку.
На шостому етапі залишається три вільних вузла з вагами 0.42. 0.32 і 0.26. Вибираємо найменші ваги 0.32 і 0.26. Дерево кодування Хаффмена після шостого кроку наведено на рис. 7.
Мал. 7. Дерево кодування Хаффмена після шостого кроку.
На сьомому етапі залишається об'єднати дві що залишилися вільні вершини, після чого отримуємо остаточне дерево кодування Хаффмена, наведене на рис. 8.
Мал. 8. Остаточне дерево кодування Хаффмена.
На підставі побудованого дерева літери передаються кодами, що відображають шлях від кореневого вузла до листа, відповідного потрібній літері. У розглянутому прикладі букви вхідного алфавіту кодуються так, як показано в таблиці 2.
З таблиці 3 видно, що коди також вийшли префіксними, і найбільш імовірним буквах відповідають найбільш короткі коди.
Питання практичної реалізації алгоритму
Для підвищення ефективності стиснення необхідно, щоб при побудові кодового дерева використовувалися дані по можливостям появи букв саме в цьому файлі, а не усереднені по великій кількості текстів. Виходячи з цього, необхідна статистика зустрічальності букв стискається файлу, яка може бути отримана попередніми проходом по файлу.
Для прискорення роботи прийнято визначати не вірогідність появи букв pi. а частоту народження (кількість появ) букви в файлі ni. Це дозволяє істотно спростити і прискорити алгоритм (не потрібно повільних операцій з плаваючою комою і операцій ділення). При такому підході алгоритм роботи не змінюється, так як частоти прямо пропорційні можливостям. Варто зауважити, що вага кореневого вузла дерева кодування в такому випадку буде дорівнює загальній кількості букв в оброблюваному файлі.
Інтерактивне навчання
Після того, як ви ознайомилися з теоретичною частиною роботи, пропонуємо вам попрактикуватися в побудові кодових дерев Хаффмена за допомогою інтерактивної навчальної системи. Для цього достатньо перейти за цим посиланням.