Код Хаффмена

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

Алгоритм Хаффмена вимагає читати вхідний файл двічі, один раз, вважаючи частоти входження символів, а другий раз, виконуючи безпосереднє кодування.

Отже, в основі алгоритму кодування Хаффмена лежить простий принцип: символи заміняються кодовими послідовностями різної довжини. Чим частіше використовується символ, тим коротше відповідна послідовність. Наприклад, для англійського тексту символам e, t, a можна поставити відповідні 3-бітові послідовності, а j, z, q — 8-бітові. В одних варіантах алгоритму Хаффмена використовуються готові кодові таблиці, в інших — кодова таблиця будується на основі статистичного аналізу умісту файла. Застосування коду Хаффмена гарантує можливість декодування. Це важливо, тому що "упаковані" кодові послідовності мають різну довжину, на відміну від звичайних, довжина яких постійна і дорівнює 8 біт на символ.

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

Процес повторюється і продовжується до тих пір, поки залишиться одна літера з імовірністю, рівною 1. Кодові комбінації можна легко отримати, побудувавши кодове дерево. Вершиною дерева є остання літера, процес розгалуження проводиться з урахуванням отриманої таблиці, рухаючись у зворотному напрямку. Кожному з двох ребер, що беруть участь в об'єднанні, приписується кодовий символ: ребру з більшою ймовірністю - «1», з меншою - «0». Рухаючись від вершини дерева до однієї з літер алфавіту по відповідним ребрах, отримуємо її кодову комбінацію.

Приклад 4.1. Проведемо кодування за методом Хаффмена. Вихідний алфавіт складається з шести літер із заданими ймовірностями. Складемо таблицю.

A_ip(A_i) Допоміжні стовпці

A₁	0.4	0.4	0.4	0.4	0.4	1.0
A₂	0.25	0.25	0.25	0.25	0.6
A₃	0.15	0.15	0.15	0.35
A₄	0.10	0.10	0.20
A₅	0.06	0.10
A₆	0.04

Складемо таблицю кодування.

A_i p(A_i) Допоміжні стовпці

A₁	0.4 0	0.4 0	0.4 0	0.4 0	0.4 0	1.0
A₂	0.25 10	0.25 10	0.25 10	0.25 10	0.6 1
A₃	0.15 110	0.15 110	0.15 110	0.35 11
A₄	0.10 1110	0.10 1110	0.20 111
A₅	0.06 11110	0.10 1111
A₆	0.04 11111

Отриманий код:

A₁	A₂	A₃	A₄	A₅	A₆

Читайте також:

Кодування та стиснення інформації методом хаффмена та Шенона-Фано

<== попередня сторінка	\|	наступна сторінка ==>
Кодування та стиснення інформації методом хаффмена та Шенона-Фано	\|	Код Шеннона-Фано

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.001 сек.