Коди Хаффмана: приклади, застосування

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

Історія алгоритму

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

Принцип ефективного кодування

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

Код Хаффмана, приклад

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

у кожен вузол може входити не більше однієї з дуг;

один з вузлів повинен бути коренем дерева, тобто в нього не повинні входити дуги взагалі;

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

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

Алгоритм побудови дерева за Хаффманом

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

Підвищення ефективності стиснення

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

Прискорення процесу стиснення

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

Висновок

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