Проблема стиснення інформації

Для того, щоб зберігати й передавати дані, часто корисно (а іноді навіть необхідно) зменшити розмір цих даних. Метод, що використовується для цього, називається стисненням даних (data compression). Одним із загальних методів стиснення даних є частотно-залежне кодування (frequency-dependent encoding), у якому довжина коду елемента інформації обернено пропорційна частоті використання цього елемента. Ці коди є прикладами кодів змінної (нерівномірної) довжини (variable-length codes), що означає представлення елементів інформації послідовностями різної довжини, на відміну від таких кодів, як Unicode, у якому всі символи представлені 16-бітовими послідовностями. Майже всі частотно-частотно-залежні коди, що використовуються сьогодні - це коди Хафмана (Huffman codes).

Завдання оптимізації кодування можна сформулювати наступним чином: побудувати таку схему кодування, в якій сумарна довжина кодів при передачі (або сумарне число кодів при зберіганні) даного повідомлення була б найменшою.

3.2 Рівномірне кодування

Рівномірні коди мають однакову довжину для всіх символів початкового алфавіту. Розглянемо цей вид кодування на наступному прикладі: нехай є початковий алфавіт А, що складається з N = 6 знаків а₁...а₆ з ймовірностями їх появи в кодованому повідомленні 0,3; 0,2; 0,2; 0,15; 0,1; 0,05. Мінімальне значення середньої довжини рівномірного двійкового коду можна визначити за формулою:

K^рівн.к. (A, 2) ³ log₂ N,

де N - число знаків початкового алфавіту.

 

У нашому прикладі K (A, 2)^рівн.к._min ³ log₂6 ≈ 2,58 Þ K^. (A, 2)^рівн.к. = 3. Один з можливих варіантів кодування записаний в таблиці 3.1.

Визначимо відносну надлишковість отриманого рівномірного двійкового коду Q(A,2):

Q(A,2) = (K (A, 2) × I(B)) / I(A) – 1, де

(3.1)

 

I^(A) – середня кількість інформації на знак початкового алфавіту A:

 

I^(A) = - å p_i log₂ p_i, біт,

де p_i = n_i / n – ймовірність появи i -го символу початкового алфавіту, n_i – кількість повторень i-го символу в кодованому повідомленні, n – довжина кодованого повідомлення.

Для заданого алфавіту А одержимо:

I^(A) = - (0,3 × log₂0,3 + 0,2 × log₂0,2 + 0,2 × log₂0,2 +0,15 × log₂0,15 + 0,1 ´ log₂0,1+ 0,05 × log₂0,05) ≈ 2,409 біт.

Нехай I^(B) - середня кількість інформації на знак вторинного алфавіту B. З урахуванням того, що для кодування використано двійковий алфавіт:

 

I(2) = - å pi log2 pi = - (p 0log2 p 0 + p 1log2 p 1), біт,

(3.2)

де p ₀ – імовірність появи 0 у коді, p ₀ = m ₀/ m,

p ₁ – імовірність появи 1 у коді, p ₁ = 1 - p ₀,

m ₀ – кількість появи 0 у закодованому повідомленні,

m – загальна кількість символів у закодованому повідомленні.

Якщо m ₀ і m не відомі, тоді p ₀ можна визначити за формулою:

 

p 0 = å (pi × p (i)0) = å (pi × (k (i)0 / k (i))),

(3.3)

де i = 1..N,

p_i – імовірність появи i -го символу початкового алфавіту,

p ⁽ⁱ⁾₀ – імовірність появи 0 у коді i -го символу початкового алфавіту,

k ⁽ⁱ⁾ – довжина коду i -го символу початкового алфавіту,

k ⁽ⁱ⁾₀ – кількість цифр 0 у коді i -го символу початкового алфавіту.

Для складеного в таблиці 3.1 рівномірного двійкового коду, маємо:

p ₀ ^рівн.к. = 0,3 × 3/3 + 0,2 × 2/3 + 0,2 × 2/3 + 0,15 × 1/3 + 0,1 × 2/3 + 0,05 × 1/3 = 0,7.

Тоді, згідно (3.2), I^{(2) рівн.к.} = - (p ₀ ^рівн.к. × log₂ p ₀ ^рівн.к. + (1 - p ₀ ^рівн.к.) × log₂ (1 - p ₀ ^рівн.к.)) = = - (0,7 × log₂0,7 + 0,3 × log₂0,3) ≈ 0,881 біт.

За формулою (3.1) маємо: Q(A,2) ^рівн.к. = (K (A, 2) ^рівн.к. × I^{(2) рівн.к.} ) / I^(A) – 1 =
= 3 × 0,881 / 2,409 – 1 ≈ 0,101.

 

3.3 Алфавітне кодування в префіксний код Хафмана.

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

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

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

Побудову кодів Хафмана розглянемо на тому ж прикладі 3.1. Розташуємо знаки початкового алфавіту в таблиці в порядку зменшення ймовірностей. Створимо новий допоміжний алфавіт А₁, об'єднавши два знаки з найменшими ймовірностями (а ₅ й а ₆) і замінивши їх одним знаком (наприклад, а ⁽¹⁾); ймовірність нового знаку буде дорівнювати сумі ймовірностей тих знаків попереднього проміжного алфавіту, що в нього увійшли, тобто 0,15. Інші знаки вихідного алфавіту включимо в новий без змін. Загальне число знаків у новому алфавіті, зрозуміло, буде на 1 менше, ніж у вихідному. Аналогічним чином продовжимо створювати нові алфавіти, поки в останньому не залишиться два знаки; очевидно, що кількість таких кроків буде дорівнювати N - 2, де N - число знаків початкового алфавіту (у нашому випадку N = 6, отже, необхідно побудувати 4 допоміжних алфавіти). У проміжних алфавітах щораз будемо перевпорядковувати знаки по зменшенню ймовірностей.

Далі у зворотному напрямку потрібно виконати процедуру кодування. Двом знакам останнього алфавіту присвоїмо коди 0 і 1 (порядок присвоєння не має значення; домовимось, що верхній знак буде мати код 0, а нижній - 1). У нашому прикладі знак a ₁⁽⁴⁾ алфавіту А ⁽⁴⁾, щомає імовірність 0,6, отримає код 0, a a ₂⁽⁴⁾ з імовірністю 0,4 - код 1. В алфавіті А ⁽³⁾ знак a ₁⁽³⁾отримає від a ₂⁽⁴⁾ його імовірність 0,4 і код (1); коди знаків a ₂⁽³⁾і a ₃⁽³⁾, що виникли від знаку a ₁⁽⁴⁾ з імовірністю 0,6, будуть вже двозначним: їх першою цифрою стане код їх попередника (тобто 0), а друга цифра - як домовлено раніше - у верхнього 0, у нижнього – 1. Таким чином, a ₂⁽³⁾ буде мати код 00, а a ₃⁽³⁾ - код 01. Повністю процедура кодування представлена на рисунках 3.1, 3.2:

 

Рисунок 3.1 – Схема побудови проміжних алфавітів префіксного коду Хафмана

 

Рисунок 3.2 – Схема побудови кодування в префіксний код Хафмана

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

Середня довжина отриманого префіксного коду:

 

K (А,2)= å (p_i × k ⁽ⁱ⁾),

де i = 1..N,

p_i – імовірність появи i-го символу початкового алфавіту,

k ⁽ⁱ⁾ – довжина коду i-го символу початкового алфавіту.

 

В нашому випадку:

K (А,2)^преф.к. = 0,3 × 2 + 0,2 × 2 + 0,2 × 2 +0,15 × 3 + 0,1 × 4 + 0,05 × 4 = 2,45.

 

Згідно (3.3) p ₀ ^преф.к. = å (p_i × (k ⁽ⁱ⁾_0/ k ⁽ⁱ⁾)) = 0,3 × 2/2 + 0,2 × 1/2 + 0,2 × 0/2 + 0,15 × × 2/3 + 0,1 × 2/4 + 0,05 × 1/4 = 0,563.

p ₁ = 1 - p ₀ = 1 - 0,563 = 0,437.

Визначимо середню кількість інформації на знак вторинного алфавіту отриманого префіксного коду. За формулою (3.2) маємо:

 

I^{(2) преф.к..} = - (p ₀ ^преф.к. log₂ p ₀ ^преф.к. + (1 - p ₀ ^преф.к log₂ (1 - p ₀ ^преф.к.) = - (0,563 ×
× log₂0,563 + 0,437 × log₂0,437) ≈ 0,988 біт.

 

Відносні надмірність коду згідно (3.1) дорівнює:

Q(A,2) ^преф.к. = (K (A, 2)^преф.к. × I^{(2) преф.к.} ) / I^(A) – 1 = 2,45 × 0,988 / 2,409 – 1 ≈ 0,005.

Результати обчислень рівномірного двійкового коду й префіксного коду Хафмана відображені в таблиці 3.2. Звідси можна зробити висновок, що префіксний код Хафмана є значно оптимальнішим, ніж мінімальний за довжиною рівномірний двійковий код, тому що 1) містить на 12% більше інформації I⁽²⁾ завдяки меньшій різниці значення p ₀ й p ₁, 2) має на 22% меншу середню довжину коду на один символ початкового алфавіту, а також 3) є в 20 разів менш надлишковим.

 

Таблиця 3.1 – Результати алфавітного кодування символів із прикладу 3.1 в рівномірний двійковий код і нерівномірний префіксний код Хафмана

 

Символ початкового алфавіту A	Вірогідність появи аi у вхідному повідомленні	Рівномірний двійковий код	Префіксний код Хафмана
а1	0,3
а2	0,2
а3	0,2
а4	0,15
а5	0,1
а6	0,05

 

 

Таблиця 3.2 – Порівняльні результати кодування тексту

 

Вид кодування	I(A)	p 0	p 1	I(2)	K(A,2)	Q(A,2)
Рівномірний двійковий код	2,409	0,7	0,3	0,881		0,101
Префіксний код Хафмана	2,409	0,563	0,437	0,988	2,45	0,005