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

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

Відео: Код Хаффмана

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

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

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

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

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

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

Відео: Алгоритм Хаффмана C ++

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

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

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

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

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

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

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

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

Відео: Лекція 218. Код Хеммінга

висновок

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