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

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

Можна уявити, що всі файли - це тексти, написані на алфавіті, який складається з 256 літер (так воно власне і є). Розглянемо всю множину файлів, розмір не перевищує n байт (де n будь - яке число). І припустимо, що існує деякий алгоритм кодування, який любий файл стискує з "додатною" ефективністю. Тоді множина всіх їх архівів які входять в склад всіх файлів, розмір яких менше n байт. Згідно нашому припущенню існує відповідність між двома закінченими множинами, кількість елементів яких не співпадає. Звідси можливо зробити досить вагомі висновки: 1) не існує архіватора, який би однаково добре пакував будь-які файли, 2) для будь-якого архіватора знайдуться файли, в результаті стиснення яких будуть отримані архіви в кращому випадку не меншого розміру чим початкові файли.

Тепер почнемо описання алгоритму Хаффмана. Розглянемо його на прикладі наступного файлу:

cccacbcdaaabdcdcddcddccccccccccc {end of file}

Розпишемо частоти кожного з символів:

a - 4,

b - 2,

c - 19,

d - 7.

Весь файл займає 32 байта. Кожен з символів в початковому файлі кодується згідно таблиці ASCII вісьмома бітами:

a - 01100001,

b - 01100010,

c - 01100011,

d - 01100100,

Крок №1. Розмістимо ці чотири символи в порядку зменшення їх частот:

{(c,19),(d,7),(a,4),(b,2)}

Крок №2. На наступному рядку запишемо набір, отриманий з попереднього наступним чином:

замість двох останніх символів з їх частотами запишемо новий елемент, котрий замість назви символу буде мати запис "Вершина #n", а замість частоти - сума частот останніх двох елементів попереднього набору;

відсортуємо отриманий набір по спаданню.

{(c,19),(d,7),( "Вершина #1", 6)}

Крок №3. Переходимо на крок №2до тих пір, поки набір не буде складатися тільки з одного елемента: ("Вершина #last_number", summa_vseh_chastot):

{(c,19), ("Вершина #2", 13)}

{( "Вершина #3", 32)} (візуальна ілюстрація див. Малюнок №1)

Що ж отримали? Розгляньте малюнок. Ви бачите дерево, яке росте з листків! Якщо з'єднати лінією кожен з елементів "вершина #x" з тими елементами попередніх наборів, сума частот яких зберігається в другій частині елемента "вершина #x", то ми отримаємо так би мовити дерево(в програмуванні подібні структури називаються бінарними деревами).

Суть цієї деревовидної структури в тому, щоб кожному з символів спів ставити різне число біт в залежності від його частоти (як вже казалося, в нетиснутому файлі символи зберігаються в виді груп по вісім біт). Якщо уважно придивитись в цей малюнок, ви побачите, що кожна з гілок відмічена або нулем або одиницею. Таким чином, якщо уявно пройтись по дереву від кореня до якої-небудь вершини, маючої символ, то послідовність нулів та одиниць, які зустрічаються на вашому шляху, буде комбінацією біт для цього символу. Наприклад, символ "с" як найбільш часто зустрічаємий буде кодуватися одним бітом "0", символ "d" двома бітами "10" і т.д. (див. Малюнок №2)

Давайте розглянемо ще один приклад файлу, власне дерево якого має вигляд більш складний, ніж в попередньому випадку.

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

ddddddaaaaaabbbbbbccccdffffffffffdddd{37 byte, end of file}

В двійковому вигляді файл буде мати вигляд такий:

01100100 01100100 01100100 01100100 01100100 01100100 01100001 01100001 01100001 01100001 01100001 01100001 01100010 01100010 01100010 01100010 01100010 01100010 01100011 01100011 01100011 01100011 01100100 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100100 01100100 01100100 01100100{296 bit, end of file}

Розпишемо частоти кожного з символів:

a - 6

b - 6

c - 4

d - 11

f - 10

Весь файл займає 37 байт. Кожен з символів в початковому файлі кодується згідно таблиці ASCII вісьмома бітами. Поглянемо, як будуть кодуватись ці символи в стиснутому файлі. Для цього побудуємо відповідне дерево (не забуваємо сортувати отриманий набір):

1. {(d,11), (f,10), (a,6), (b,6), (c,4)};

2. {(d,11), (f,10), (вершина #1, 10), (a,6)} (зауважте, що сортування по спаданню частот є обов'язковим!);

3. {(вершина #2, 16), (d,11), (f,10)};

4. {(вершина #3, 21), (вершина #2, 16)};

5. {(вершина #4, 37)}

Аналізуючи отримане дерево, розпишемо, як буде кодуватися кожен з символів після стиснення:

a - "11"

b - "100"

c - "101"

d - "00"

f - "01".

В двійковому вигляді файл буде мати такий вигляд:

00000000 00001111 11111111 10010010 01001001 00101101 10110100 01010101 01010101 01010000 0000хххх{88 bit, end of file}

Стиснутий файл зайняв 11 байт (останні чотири біта хххх записуються будь-які, тому що весь файл насправді вміщується в 84 біта, що не кратно восьми). Коефіцієнт стиснення при такому кодуванні дорівнює 3,5.

Список використаних джерел