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

Для того, щоб зберігати й передавати дані, часто корисно (а іноді навіть необхідно) зменшити розмір цих даних. Метод, що використовується для цього, називається стисненням даних (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⁽²⁾ = - å p_i log₂p_i = - (p₀log₂p₀ + p₁log₂p₁), біт, (3.2)

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

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

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

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

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

p₀= å (p_i × p⁽ⁱ⁾₀) = å (p_i × (k⁽ⁱ⁾₀ / k⁽ⁱ⁾)), (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 у вхідному повідомленні	Рівномірний двійковий код	Префіксний код Хафмана
а₁	0,3
а₂	0,2
а₃	0,2
а₄	0,15
а₅	0,1
а₆	0,05

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

Вид кодування	I^(A)	p₀	p₁	I⁽²⁾	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