и кодування. Метод Хаффмана є прикладом побудови кодів змінної довжини, що мають мінімальну середню довжину. Цей метод виробляє ідеальне стиснення, тобто стискає дані до їх ентропії, якщо ймовірності символів точно рівні негативним ступенями числа 2. p align="justify"> Цей метод кодування складається з двох основних етапів:
. Побудова оптимального кодового дерева. p align="justify">. Побудова відображення код-символ на основі побудованого дерева. p align="justify"> Алгоритм заснований на тому, що деякі символи зі стандартного 256-символьного набору в довільному тексті можуть зустрічатися частіше середнього періоду повтору, а інші - рідше. Отже, якщо для запису поширених символів використовувати короткі послідовності біт, довжиною менше 8, а для запису рідкісних символів - довгі, то сумарний обсяг файлу зменшиться. У результаті виходить систематизація даних у вигляді дерева (В«двійкове деревоВ»). p align="justify"> Нехай A = {a1, a2, ..., an} - алфавіт з n різних символів, W = {w1, w2, ..., wn} - відповідний йому набір позитивних цілих ваг. Тоді набір бінарних кодів C = {c1, c2, ..., cn}, такий що:
- ci не є префіксом для cj, при i! = j;
мінімальна (| ci | довжина коду ci)
називається мінімально-надлишковим префіксним кодом чи інакше кодом Хаффмана.
Бінарним деревом називається орієнтоване дерево, полустепені результату будь-якої з вершин якого не перевищує двох.
Вершина бінарного дерева, полустепені заходу якої дорівнює нулю, називається коренем. Для решти вершин дерева полустепені заходу дорівнює одиниці. p align="justify"> Нехай Т-бінарне дерево, А = (0,1) - двійковий алфавіт і кожному ребру Т-дерева приписана одна з букв алфавіту таким чином, що всі ребра, що виходять з однієї вершини, позначені різними літерами . Тоді будь-якому листу Т-дерева можна приписати унікальне кодове слово, утворене з букв, якими позначені ребра, що зустрічаються при русі від кореня до відповідного листу. Особливість описаного способу кодування в тому, що отримані коди є префіксними. p> Очевидно, що вартість зберігання інформації, закодованої за допомогою Т-дерева, дорівнює сумі довжин шляхів з кореня до кожного листу дерева, зважених частотою відповідного кодового слова або довжиною зважених шляхів:, де - частота кодового слова довжини у вхідному потоці. Розглянемо як приклад кодування символів в стандарті ASCII. Тут кожен символ являє собою кодове слово фіксованій (8 біт) довжини, тому вартість зберігання визначиться виразом, де W-кількість кодових слів у вхідному потоці. p> Тому вартість зберігання 39 кодових слів в кодуванні ASCII дорівнює 312, незалежно від відносної частоти окремих символів в цьому потоці. Алгоритм Хаффмана дозволяє зменшити вартість зберігання потоку кодових слів шляхом такого підбору довжин кодових слів, який мінімізує довжину зважених шляхів. Будемо ...
