Оптимальне кодування

Досі термін " код" використовувався в загальноприйнятому смис­лі (див. параграф 7.1). Однак, у теорії кодування, а ще раніше в техніці слово " код" трактується також і як множина елементарних кодів. Починаючи з цього місця, слово " код" будемо використову­вати в двох смислах. З контексту буде зрозуміло, який саме з них маємо на увазі.

Нехай заданий алфавіт A={a₁..., а_r} і розподіл ймовірностей Р=(р₁,..., р_r) появи букв у повідомленні. Тутр_i ймовірність появи букви а₁. Не зменшуючи загальності, можна вважати, що

тобто можна одразу виключити букви, які не можуть з'явитись в повідомленні, і впорядкувати букви за спаданням ймовірностей їхньої появи. Крім того, р ₁+ р ₂+...+ р_r =1.

Для кожної роздільної схеми алфавітного кодування σ матема­тичне сподівання коефіцієнта збільшення довжини повідомлення і разі кодування (позначають ^͞ l _σ ) визначають так:

і називають середньою довжиною кодування σ для розподілу ймо­вірностей Р.

Позначимо

^͞ .

Очевидно, що завжди існує роздільна схема σ така, що l (β _i)= для кожногоi=1, 2,..., r. Отже, 1≤ ^͞ l. (Р)≤ і достатньо враховувати лише такі схеми, для яких (і=1, 2,..., r), де - ціле та . Звідси випливає, що є лише скінченна кількість схем σ, для яких, . Отже, існує схема , на якій інфімум досяга­ється: .

Алфавітне кодування з роздільною схемою для якої називають кодуванням з мінімальною надлишковістю, або оптимальним кодуванням для розподілу ймовірностей Р.

За наслідком 2 з теорем 7.3 та 7.4 існує алфавітне кодування і префіксною схемою, яке дає оптимальні коди. У зв'язку із цим під час побудови оптимальних кодів можна обмежитись префіксними схемами.

Проста ідея побудови коду, близького до оптимального, нале­жить американському математику Фано(Fano). Сформулюємо алго­ритм кодування за методом Фано.

1. Упорядковуємо букви алфавіту А за спаданням імовірностейїхньої появи в повідомленні.

2. Розбиваємо множину букв, записаних у вказаному порядку, на дві послідовні частини так, щоб сумарні ймовірності кожної з них були якомога ближчі одна до одної. Кожній букві з першої частини приписуємо символ 0, другої - символ 1. Далі так само чинять із кожною частиною, якщо вона містить принаймні дві

букви. Процедуру продовжуємо доти, доки вся множина не буде розбита на окремі букви.

Приклад 7.3. Нехай заданий розподіл ймовірностей Р=(0.4, 0.15, 0.15, 0.15, 0.15). Побудуємо код за методом Фано. Розв'язок подано втабл. 7.1.

Середня довжина коду дорівнює

= 0.4× 2 + 0.15× 2 + 0.15× 2 + 0.15× 3 + 0.15× 3 = 2.3,

де індекс Fозначає, що код отриманий за методом Фано. ▲

Таблиця 7.1

Алгоритм Фано має просту інтерпретацію за допомогою бінар­ного дерева. Від кореня відходять два ребра, одне з яких позначене символом 0, друге - символом 1. Ці два ребра відповідають розбиттю множини всіх букв на дві майже рівноймовірні частини, одній з яких співставляють символ 0, а другій - символ 1. Ребра, що виходять із вершин наступного рівня, відповідають розбиттю отриманих частин знову на дві майже рівноймовірні послідовні частини. Цей процес продовжують до моменту, коли множина букв буде розбита на окремі букви. Кожний листок дерева відповідає деякому елементарному коду. Щоб записати цей код потрібно пройти простий шлях від кореня до відповідного листка.

Зазначимо, що незалежно від способу кодування кожному бінар­ному дереву відповідає набір двійкових елементарних кодів. У тако­му разі дерево називають кодовим. Якщо елементарні коди відпові­дають листкам кодового дерева, то відповідна схема алфавітного кодування є префіксною (отже, забезпечується однозначність декодування).

Приклад 7.4. На рис. 7.1 зображено кодове дерево, яке отримане за методом Фано для розподілу ймовірностей із прикладу 7.3. ▲

Що ймовірнішою є поява букви, то швидше вона утворить " самостійну" підмножину, і, от­же, ця буква закодується корот­шим елементарним кодом. Ця обставина й забезпечує високу економічність коду Фано. Але чи завжди метод Фано приво­дить до оптимального коду?

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

Лема 7.1. В оптимальному коді буква з меншою ймовірністю не може кодуватись коротшим словом. Іншими словами, якщо код

оптимальний, то з . випливає l_i ≥ l_j.

Доведення. Припустимо протилежне: нехай є дві букви а_i та а_j.

такі, що р_i< р_j таl_i< lj. Поміняємо місцями β _i та β _j у схемі кодування.

Тоді середня довжина елементарних кодів зміниться на

тобто зменшиться, що суперечить оптимальності коду. ▲

Лема 7.2. Якщо код оптимальний, то завжди можна так пере­нумерувати букви алфавіту А={а₁,..., а_r} і відповідні елементарні коди β ₁, β ₂, …, β _r, що р₁≥ р₂≥...≥ р_rі при цьому l₁ ≤ l ₂≤ …≤ l.

Доведення. Якщо р_i> р_i+1, то з леми 7.1 випливає, що l_i ≤ l _i+1. Якщо ж p _i =p _i+1, то переставимо нумерацію букв а_i, а_i+1 та відповідних елементарних кодів. Повторюючи цю процедуру потрібну кількість разів, одержимо бажану нумерацію. ▲

З нерівності l ₁≤ l ₂≤ …≤ l _r випливає, що буква α _r (найменш імовірна) кодується словом β _r найбільшої довжини.

Лема 7.3. В оптимальному коді завжди знайдеться два елемен­тарних коди найбільшої довжини l _r і таких, що вони відрізняються лише в останньому символі.

Доведення. Припустимо, що це не виконується. Тоді можна відкинути останній символ елементарного коду β _r, не порушуючи властивості префіксності. У такому разі, очевидно, зменшиться середня довжина елементарного коду. Це суперечить твердженню, що код оптимальний. ▲

Теорема 7.5. Завжди існує такий оптимальний код, у якому елементарні коди двох найменш імовірних букв та відрізня­ються лише в останньому символі.

Доведення. За лемою 7.3 знайдеться елементарний код який має ту саму довжину, що й і відрізняється від нього лише в останньому символі. З лем 7.1 та 7.2 випливає, що = l _t+1=...= l _r. Якщо t≠ r-1, то можна поміняти номери та , не порушуючи при цьому нерівність ≤, ≤...≤ ▲

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

Розглянемо нову множину букв А={ , , а} із розподілом імовірностей =(, … ), де Цю множину отримано з алфавіту об'єднанням двох найменш імовірних букв та а_r в одну букву а з імовірністюр= +р_r.Кажуть, що А₁тримано стисненням А.

Нехай для , побудовано схему , з елементарними кодами , …, Іншими словами, указане деяке кодове дерево з листками , ,..., , β. Схемі можна поставити у відповідність схему σ з елементарними кодами , ,..., , для заданого алфавіту А, якщо взяти β 0, =β 1 (тобто елементарні коди , та отримують з елементарного коду β приписуванням справа 0 та 1, відповідно).

Процедуру переходу від , до σ називають розчепленням.

Теорема 7.6. Якщо схема σ є оптимальною для алфавіту , то схема σ є оптимальною для алфавіту А.

Доведення. Легко переконатись, що середні довжини елементарних кодів у схемах σ та з язані співвідношенням .

Припустимо, що схема σ не оптимальна для алфавіту А, тобто існує схема ∑, для якої . Нехай їїелементарними кодами є , , Можна вважати, що листки кодового дерева схеми ∑ відповідають двом найменш імовірним буквам алфавіту А і відрізняються лише в останньому символі.

Розглянемо схему ∑ для алфавіту . Елементарними кодами схеми , , , β ˊ. Елементарний кодβ ˊ отримують відкиданням останнього символу від (або від результат буде тим самим). Середні довжини кодів зв'язані співвідношенням

Зі співвідношень , та випливає, що . Це суперечить оптимальності схеми для алфавіту ▲

З теореми 7.6 випливає такий метод побудови оптимальної схеми алфавітного кодування. Спочатку здійснюють послідовні стисненняалфавіту А до отриманняалфавітуіздвох букв, оптимальна схема кодування для якого очевидна: першу букву кодують символом 0, другу символом 1. Післяцьоговикористовуютьпослідовнірозчепленняотриманоїсхеми. очевидно, що отримана схема є префіксною.

Описаний метод кодування запропоновано 1952р. американським математиком Хаффманом (Huffman) і названий його ім’ям.

Приклад.7.5. Нехай заданий розділ ймовірностей Р =(0.4, 0.15, 0.15, 0.15, 0.15) як у прикладі 7.3. Побудуємо код за методом Хаффмана. Розвязок наведено в табл. 7.2.

Кожний з алфавітів отримують стисненням попереднього алфавіту. Алфавіт складається із двох букв, тому оптимальна схема міститьусього два елементарнихкоди - символи 0 та 1. Послідовнерозщепленнядаєоптимальну схему для початкового алфавіту A (у процесі розщеплення потрібно рухатись проти

стрілок ).

Таблиця 7.2

Букви алфавіту А	Ймовірності та позначення елементарних кодів
Початкрвийалфавіт А	Стиснуті алфавіти
	0.4 1 0.15 010 0.15 011 0.15 000 0.15 001	0.4 1 0.3 00 0.15 010 0.15 011	0.4 1 0.3 00 0.3 01	0.6 0 0.4 1

Середнядовжинапобудованого коду, яка дорівнює = 0.4 х 1 + 4 х 0.15 х 3 = 2.2, є, як це випливає з попереднього, мінімально можливою для заданого розподілу ймовірностей Р. Тут індекс Н означає, що код отриманий за методом Хаффмана. ▲

У прикладі 7.3 отримано код за методом Фано з середньою довжиною = 2.3. Отже, метод кодування Фано не завжди дає оптимальний код.

Ґрунтуючись на алгоритмі Хаффмана, можна безпосередньо побудувати кодове дерево оптимального коду. Це дерево називають деревом Хаффмана.

За алгоритмом Хаффмана бінарне дерево, яке відповідає оптимальному коду, будують знизу вверх, починаючи з | A |= r листків, у цьому разі виконують r-1 злиття. Злиття полягає в побудові нового дерева із двох наявних дерев (або листків) з найменшими ймовірностями. Причому листок або дерево з більшою ймовірністю- ліве піддерево, а сума ймовірностей лівого й правого піддерев дорівнює ймовірності отриманого дерева (її записують у правого піддерева. Список ймовірностей перед кожним злиттям упорядковують за спаданням.

Алгоритм Хаффамана належить до жадібних алгоритмів [1, 2, 4].

Приклад 7.6. Побудуємо дерево Хаффмана для розподілу ймовірностей Р =(0. 34, 0.18, 0.17, 0.16, 0.15). Оскільки всього п’ять

: 0.34

: 0.18

: 0.17

: 0.16

: 0.15

Рис. 7.3

a

б

в

г

Рис. 7.4

букв, то для побудови дерева потрібно зробитичотири злиття. На кожному кроці зливають два піддерева з найменшими ймовірностями. Отримують нове дерево із сумарною ймовірністю лівого й правого піддерев. Список ймовірностей упорядковують за спаданням. Листки зображають прямокутниками, у яких букви та їхні ймовірності відокремлюють двокрапкою (рис.7.3). Внутрішні вершини зображають кружечками, у яких зазначають суми ймовірностей їхніх синів. Динаміку роботи алгоритму відображено на рис.7.4 а-г.

Для того, щоб отримати елементарний код для певної букви, потрібно пройти єдиний простий шлях від кореня до відповідного листка, записуючи послідовність бітів. Унаслідок отримаємо таку оптимальну схему алфавітного кодування для заданого розділу ймовірностей → 00, → 10, → 010, 011. ▲

Загалом, оптимальнасхема не єдина. У табл.7.3 для розподілу ймовірностей Р =(0.4, 0.2, 0.2, 0.1, 0.1) наведено три різні оптимальні схеми ( (Р)=2.2).

Таблиця 7.3

Букви алфавіту	Імовірності	Схема 1	Схема 2	Схема3
	0.4
	0.2
	0.2
	0.1
	0.1