Лекція 04. Інформаційна модель джерела дискретних повідомлень та засади його кодування
Курс “Теорія інформації та кодування”

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

Інформативність дискретних повідомлень
Принципи статистичного кодування із стисканням повідомлень
Метод статистичного кодування за Хаффманом
Особливості адаптивного статистичного кодування

4.1 Інформативність дискретних повідомлень

Модель дискретного джерела повідомлень
Для оцінювання інформативності дискретних повідомлень використовується модель так званого «дискретного джерела» рис.4.1.

Рисунок 4.1. Модель дискретного джерела повідомлень

Як і будь-яка модель, ця узагальнює представлення обєкту з позицій конкретної задачі і повинна бути зручною для практичного використання. В нашому випадку модель дискретного джерела повідомлень має надати досить прості формули для оцінювання інформативності. Це забезпечується наступним:

- вважається, що джерело повідомлень створює поcлідовність знаків, які належать алфавіту з обсягом N і характеризуються заданими імовірностями появи pi. Така послідовність вважається стаціонарною, тобто імовірності знаків не залежать від часу (подібно до того, що частоти появи різних букв алфавіту в тексті майже не залежать номеру сторінки з якої ви почали їх підраховувати);

- наявність імовірностей створює невизначеність при очікуванні будь-якого наступного знаку. Для розрахунку величини невизначеності використовується математична функція ентропії H, яка має розмірність біт/знак (надалі ми детально розглянемо цю функцію). Коли з'являється черговий знак послідовності, відповідна невизначеність Н усувається і замість неї маємо інформацію кількістю I=H;

- найбільш простою і водночас корисною є так звана модель джерела «без пам'яті», де поява знаків вважається незалежною від передісторіі, а їх імовірності p1...pN - безумовними (відповідно ентропія тут також називається безумовною). Зокрема саме таку модель використав Клод Шеннон для своїх досліджень щодо інформативності повідомлень та їх ефективного кодування;

- більш повна модель джерела «із пам'яттю» враховує наявність зв'язків між сусідніми знаками в послідовності (дійсно, наприклад імовірності появи різних типів букв в тексті вочевидь будуть різнитись в залежності від попередніх букв). В цій моделі властивості джерела задаються так званими умовними імовірностями — наприклад pi/j (зокрема в такому запису відображена імовірність появи i-го знаку алфавіту за умовою, що попереднім був знак j-го типу). Кількість попередніх знаків, що враховуються, називають також «глибиною пам'яті» k джерела. Відповідно ентропія в цьому випадку також зветься умовною — H(k). Вочевидь при врахуванні більшої глибини передисторії ентропія (а разом з нею інформативність джерела) може зменшуватись. Як ми далі побачимо, це важливо враховувати при стисканні коду повідомлень.

Визначення безумовної ентропії
Розглянемо спосіб визначення безумовної ентропії, розрахунок якої базується на безумовних імовірностях появи знаків (рис.4.2).

Рисунок 4.2. Формула для визначення безумовної ентропії

Формула для розрахунку безумовної інформаційної ентропії (надалі просто ентропії) була запропонована Клодом Шенноном і має вигляд:
Н = - Σ pi log2 pi (i = 1 ... N) (4.1)

Тут ентропія H визначається як середньозважене значення невизначностей появи окремих типів знаків Нi = - log2pi (як “вагові” коефіцієнти виступають їх імовірності pi). При цьому знак «-» компенсує від'ємність логарифмів дробних величин.

Легко бачити, що із зменшенням імовірності знаку розрахункова величина його інформативності зростає. Наприклад, імовірностям 1/2, 1/4 і 1/8 будуть відповідати значення інформативності 1, 2 і 3 біт/знак (саме таке потрібно від складових функції ентропії згідно підходу, де інформативність відповідає новізні та непрогнозованості).

Застосування логарифмів дозволяє узгодити статистичний та структурний підходи. Так в разі, коли ймовірності всіх N знаків алфавіту однакові (при цьому pi = 1/N), наведена формула ентропії дає значення інформативності Нi = - log2(1/N) = log2N. Тут значення інформативності знаків збігається з їх інформаційною ємністю.

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

Рисунок 4.3 Властивості безумовної ентропії

- значення функції не від'ємні (H>=0). Зокрема позитивні значення відповідають наявності невизначеності, а нульове — її відсутності;

- максимум функції ентропії (в загальному випадку Н=log2N, а для двійкового алфавіту на рис.4.7 Н=1) відповідає випадку, коли всі знаки однаково імовірні. Дійсно, в такому випадку немає підстав передбачати перевагу появи будь-якого знаку порівняно з іншими;

- мінімальне значення (Н=0) відповідає випадку, коли імовірність появи якогось одного знаку дорівнює одиниці, а всіх інших — нулю (це означає, що завжди з'являється саме такий знак і нема ніяких підстав очікувати інших).

Суттєво, що зміна значень H при змінах розподілу імовірностей знаків є дуже нерівномірною: ентропія суттєво зменшується тільки коли якісь знаки сильно переважають інші в імовірності появи (приклади на рис.4.3).

Розрахунок умовної ентропії
Обчислення умовної ентропії виконується з урахуванням умовних ймовірностей появи знаків (рис.4.4):

Рисунок 4.4 Розрахунок умовної ентропії

- зокрема, якщо відомо, що черговому знаку передував знак j-го типу, то відповідна «частна» ентропія може бути обчислена за формулою:
Н(1)j = - Σ pi/j log2 pi/j (j = 1 ... N) (4.3)
де pi/j - умовні ймовірності появи всіх i-х знаків після заданого j-го.

Тепер, усреднюючи значення Н(1)j з урахуванням їх "ваги" (імовірностей знаків), отримаємо значення умовної ентропії з глибиною історії в один крок k=1:
Н(1) = - Σ pj Σ pi/j log2 pi/j (i = 1 ... N, j = 1 ... N) (4.4)

Наступна формула дозволяє обчислити значення умовної ентропії з глибиною історії k = 2:
Н(2) = - Σ pi Σ pj Σ pi/j,l log2 pi/j,l (i = 1 ... N, j = 1 ... N, l = 1 ... N) (4.5)

Аналогічно обчислюються значення ентропії і при більших значеннях k.
При цьому кожен крок збільшення глибини історії означає зростання мірності таблиці умовних імовірностей. Зокрема, при k = 1 ми будемо працювати з двовимірної таблицею розміром nxn = n2, при k = 2 - з тривимірною розміром n3 і т.д. (Рис.4.4). Разом з тим кожне значення умовної ймовірності потрібно підраховувати. Очевидно, що зростання громіздкості обчислень на практиці обмежує глибину обліку передісторії знаків.

Контрольні питання
1) Охарактеризуйте модель джерела дискретних повідомлень: якими параметрами задається джерело в моделі з пам'яттю та без пам'яті; що характеризує величина ентропії і як вона ентропія пов'язана із інформацією; в чому різняться безумовна та умовна ентропія.
2) Запишіть формулу безумовної ентропії. Поясніть її зв'язок з формулою невизначеності появи окремих знаків.
3) Назвіть основні властивості функції безумовної ентропії. Яке її максимальне значення, наприклад, при обсязі алфавіту джерела N = 3, 2, 4) Використвуючи рис.4.4, поясніть формули для розрахунку умовної ентропії для випадків глибини історії k=1 та k=2. Як може впливати збільшення глибини історії на значення ентропії того самого джерела повідомлень.


4.2 Принципи статистичного кодування із стисканням повідомлень

Теорема Шеннона про ефективне кодування джерела повідомлень
Принципово важливим результатом ТІК є теорема про кодування джерела повідомлень, яка вказує на можливості та обмеження стискання коду. Ця теорема (рис 4.5), що доведена Клодом Шенноном, стверджує, що:

Можливе кодування, яке забезпечує наближення середньої довжини коду знака Lk до величини ентропії Н дискретного джерела з будь-якої необхідної точністю. З іншого боку, не існує способу, при якому середня довжина коду була б менше ентропії.

Рисунок 4.5. До теореми про ефективне кодування джерела повідомлень

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

На перший погляд твердження теореми Шеннона є майже тривіальними: якщо повернутись до метафори передачі “змісту” повідомлення (власно інформації) в “упаковці” (тобто в формі коду), то йдеться про те, що упаковку завжди можна створити такою, яка максимально щільно пасує змісту. Це досить очевидно, якщо фізично аналогією є наприклад транспортування рідини: упаковку завжди можна заповнити майже на 100%. Але якщо “змістом” будуть тверди предмети довільної форми (наприклад, предмети меблі), то домогтися ідеальної відповідності упаковки до зміста може виявитись просто неможливим. Отже твердження теореми дійсно не є інтуітивно очевидним.

Між тим в якості доказу справедливості теореми Клод Шеннон запропонував практичний метод кодування (таке кодування він назвав “ефективним”, маючи на увазі саме максимальне стискання коду). Надалі ми розглянемо такий метод докладно, а тут зосередимось на його ідеї. Якщо співставляти формули безумовної ентропії джерела та середньої довжини кодів знаків (рис.4.5), то стає очевидним: значення Lk буде прагнути до ентропії Н, якщо довжина коду кожного знаку li прагнутиме до його інформативності -log2pi. Відповідно збитковість кодування D (рис.4.5) буде прагнути до 0. Саме такий підхід реалізує статистичне стискання, зокрема за методом Шеннона.

Метод статистичного кодування Шеннона. Простий приклад
Практичний підхід, який дозволяє реалізувати ідею статистичного стискання, полягає в тому, щоб виділяти більш короткі коди більш імовірним знакам. Водночас потрібно забезпечити визначення меж кодів окремих знаків, які тепер мають різну довжину. Цим вимогам відповідає процедура кодування, що була запропонована Шенноном і майже одночасно Фано. Простий приклад такої процедури для алфавіту із N=4 наведений на рис.4.6.

Рисунок 4.6 Простий приклад статистичного кодування за методом Шеннона

Як можна бачити, в результаті статистичного кодування, збитковість D(ст)=(1,60-1,57)/1,60=0,02 (всього 2%). При цьому така збитковість для вихідного (побайтного) кодування має значення D(вих))=(8-1,57)/8=0,80 (80%). Тобто ефективність статистичного кодування в цьому прикладі є досить високою.

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

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

Доведення теореми Шеннона. Розгорнутий приклад кодування
В прикладі на рис.4.6 ми спостерігаємо суттєвий ефект від стискання коду, але тут присутня залишкова збитковість, яка не може бути усунена розглянутою процедурою кодування. Причина в тому, що середня довжина коду точно збігається із ентропією лише у випадках, якщо імовірності знаків дорівнюють від'ємним ступіням двійки (½, ¼ тощо). Дійсно, тільки за цією умови значення Hi = - log2pi будуть цілими і можуть точно збігатись із довжиною відповідних кодових ланцюжків li. Однак імовірності знаків для фактичного джерела вочевидь не завжди відповідають такій умові (як ми і бачили зокрема в прикладі на рис.4.6). Отже для доведення справедливості теореми Шеннону знадобився удосконалений спосіб кодування. Його суть пояснює приклад на рис 4.7.

Рисунок 4.7 Приклад статистичного кодування за узагальненою процедурою Шеннона

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

Так, в прикладі на рис.4.7. вихідний алфавіт включає тільки два види знаків Z1 та Z2 і попередня процедура кодування не здатна змінити середню довжину коду порівняно із рівномірним кодуванням (Lk=1 розряд/знак). Між тим при заданих в прикладі імовірностях знаків (0,8 та 0,2) ентропія джерела є значно меншою (H =0,72 біт/знак) і таким чином на цьому - умовно першому - рівні процедура кодування дає досить значну збитковість (D1=0,280).

Якщо перетворити алфавіт джерела, замінивши кожну з пар сусідніх вихідних знаків Zi Zj на знаки окремі Ak, то імовірності таких нових знаків будуть дорівнювати множенням імовірностей вихідних знаків в парах (зрозуміло, що така закономірність справедлива за умовою статистичної незалежності сусідніх знаків, тобто в межах моделі Джерела без пам'яті). В прикладі на рис.4.7 це призводить до зменшення середньої довжини коду знаків Ak до 1,56 (нагадаємо, що вони відповідають парам вихідних знаків, отже ентропія H=1,44 відвповідна H=0,72 для попереднього варіанту). Таким чином на цьому — умовно другому - рівні кодування збитковість значно зменшується (D2=0,077).

На наступному кроці перетворення алфавіт джерела може бути додатково розширений за рахунок утворення груп із трійок сусідніх знаків. При цьому в прикладі рис.4.7 збитковість кодування зменшиться аж до значення (D3=0,014).

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

Відзначимо, що запропонована процедура передбачає збільшення обсягу алфавіту Джерела в пропорції Nk, де k – номер кроку перетворення алфавіту. Таким чином при обсягах алфавіту, які широко використовуються, вона є дуже громіздкою і має суто теоретичне значення. В практиці зазвичай застосовується саме «однорівневий» варіант кодування без перетворення алфавіту.

Контрольні запитання
1) Сформулюйте теорему Шеннона про кодування джерела повідомлень.
2) За яких умов лімітом зменшення питомої довжини коду знаків слід вважати безумовну ентропію або умвону ентропію певного рівню.
3) Спираючись на рис.4.6, поясніть процедуру побудови коду Шеннона та оцінювання його ефективності.
4) Спираючись на рис.4.7, поясніть підхід, який доводить справедливість теореми Шеннона про кодування джерела. Чому подібний спосіб не використовується в практиці.

* 5) Побудуйте код за правилами Шеннона для обсягу алфавіту N=4 та значень імовірностей, які задасте за власним вибором. Розрахуйте відповідну безумовну ентропію та величину його збитковості.

4.3 Метод статистичного кодування за Хаффманом

Кодування за Хаффманом. Простий приклад
Код Хаффмана є вдосконаленим варіантом статистичного коду Шеннона-Фано і в такій якості він отримав значне поширення. Недоліком кодування за процедурою Шеннона є неоднозначність його результатів в деяких ситуаціях. Наприклад, якщо алфавіт включає знаки з імовірностями 0,30; 0,25; 0,10 тощо, то перша утворена група може включати два знаки із сумарною імовірністю 0,45 або три знаки із сумарною імовірністю 0,55 (сумарна імовірність для знаків другої групи буде відповідно 0,55 або 0,45). З позицій алгоритму Шеннона ці варіанти рівноправні, однак одержані для них коди можуть мати різну збитковість. Таким чином код, що побудований за процедурою Шеннона, не є гарантовано оптимальним.

Удосконалення ефективного кодування запропонував Девід Хаффман (на той момент студент Клода Шеннона). Його процедура, хоч і більш складна, гарантує оптимальне побудування коду для заданих імовірностей знаків. Отже саме процедура Хаффмана одержала розповсюдження і широко використовується донині. Процедуру побудови і застосування коду на простому прикладі ілюструє рис.4.8. Для наочності тут використані ті ж вихідні дані, що і в прикладі кодування по Шеннону-Фано (рис.4.6).

Рисунок 4.8 Простий приклад кодування за Хаффманом

Побудова коду (таблиці відповідності знаків та кодових ланцюжків) включає два етапи:
- на етапі 1 виконується перетворення вихідної таблиці ймовірностей знаків;
- на етапі 2 за даними перетвореної таблиці будується граф (дерево) коду і визначаються кодові ланцюжка знаків.

Етап 1 передбачає послідовне об'єднання ймовірностей в напрямку «від низу до верху» з використанням додаткових стовпчиків. При цьому на кожному кроці підсумовуються дві мінімальні ймовірності - аж до отримання 1 (дивись таблицю на рис.4.8). Нагадаємо, що при побудові коду Шеннона, навпаки, виконується розподіл знаків на групи в напрямку «зверху вниз». Саме така відмінність при кодуванні за Хаффменом гарантує оптимальне рішення в усіх випадках, хоча найчастіше ці два способи дають однаковий результат.

Етап 2 включає побудову «дерева» коду в порядку, зворотньому об'єднанню ймовірностей (на рис.4.8 справа). При цьому умовно вважаається, що в кожній парі гілок дерева вправо йде гілка з більшою вагою. Ця гілка асоціюється зі значенням кодового розряду «1», а протилежна їй - з «0». "Листами" дерева коду стають знаки алфавіту Джерела. Тепер код кожного знака утворюється як послідовність розрядів при русі від кореня дерева до даного листа (наприклад, код Z3 читається як 001). Як видно, в даному випадку код по Хаффмену і по Шеннону збігаються (порівняймо рис.4.8 і рис.4.6).

Кодування по Хаффмену. Розгорнутий приклад
Уточнимо деталі побудови і застосування коду на більш складному прикладі (рис.4.9):

Рисунок 4.9 Приклад кодування за Хаффменом (розгорнутий)

- по-перше, тут видно, що на кожному кроці об'єднання ймовірностей новий стовпчик перевпорядковувати по їх зменшенню. В результаті отримана на даному етапі сумарна ймовірність може виявитися в новому стовпці в будь-якій позиції;

- по-друге, структура дерева істотно відрізняється від попереднього прикладу. Тут з кореня «розвиваються» дві приблизно однаково потужні гілки. При цьому найкоротші коди стають двухразрядимі. Таке характерно для випадків, коли не один із знаків не зустрічається приблизно в половині випадків (тобто, типово).

На рисунку також показано приклад кодування ланцюжка з 10 довільних знаків і декодування відповідної кодової послідовності. При кодуванні ланцюжок вибирається з рядка, що відповідає знаку коду (наприклад, для першого знака в повідомленні Z2 вибирається код 01). Процедура відновлення дещо складніше: декодер повинен "дочекатися", коли на його вході накопичиться послідовність, яка присутня в одному з рядків таблиці. При цьому початком відліку є розпізнавання попереднього знаку. Наприклад, коли розпізнано перший знак Z*2, декодер залишається з стані очікування, прийнявши перший і другий 0 і лише коли з'явиться третя 1 (сформувався код 001), розпізнає другий знак Z*5. Нагадаємо, що такий спосіб можливий тільки для префіксних кодів.

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

Рисунок 4.10 Огляд напрямків ефективного статистичного кодування

Виділяються два основні підходи до статистичного кодування:

- при статичному кодуванні імовірності знаків визначаються за рахунок попереднього вивчання Джерела повідомлень. Цей спосіб може використовуватись, якщо імовірності знаків лишаються незмінними;

- динамічне кодування передбачає підрахунок імоверностей знаків безпосередньо в ході обробки повідомлень. Це дозволяє враховувати можливі зміни характеристик Джерела, а також визначати їх зарані невідомі значення.

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

- безпосереднє статичне кодування доречно, якщо алфавіт і статистичні характеристики джерела є стабільними і відомі одержувачу зарані. Це було можливо, наприклад при передачі тексту на визначеній мові. Але нині, коли в цифровому середовищі передаються повідомлення (файли) різних типів, умови стабільності складу та імовірностей знаків Джерела зазавичай не виконуються, а отже безпосереднє кодування за Хаффманом майже не застосовується;

- кодування із перетворенням алфавіту (яке часто називають також «моделюванням Джерела») дозволяє вирішити проблему. Наприклад, популярні методи стискання виявляють та компактно кодують ланцюжки знаків, що повторюються (як наприклад, слова в тексті). При цьому довжина цих ланцюжків має певні статистичні закономірності - більш короткі ланцюжки зустрічаються частіше, що обумовлює ефективність статистичного кодування. Подібні рішення нині широко застосовуються як компоненти комплексних методів стискання і надалі ми з ними зустрінемось.

Динамічне кодування може виконуватись в більш простому варіанті без врахування передісторії знаків, або в більш складному, але ефективному варіанті із таким врахуванням. При цьому:

- динамічне кодування без врахування передісторії виконується безпосередньо за алгоритмом Хаффмана, тобто із побудовою дерева коду (рис.4.8, 4.9). Однак така побудова відбувається за розрахунком фактичної кількості появи різних знаків. Такий спосіб забезпечує наближення середньої довжини коду до безумовної ентропії джерела для будь-яких повідомлень, навіть якщо їх імовірністні характеристики зарані невідомі;

- врахування передісторії знаків може забезпечуватись за рахунок підрахунку частот появи ланцюжків знаківї. Зокрема, в програмах архіваторах використовується так званий метод PPM (Prediction by Partial Matching — передбачення по частковому співпадінню), з яким ми більш детально познайомимось надалі. Такий підхід дозволяє наближати питому довжину коду знаків уже до умовної ентропії досить високих порядків, отже ефективність стискання тут є значно вищою. Платою вочевидь є суттєве ускладнення алгоритму.

Контрольні запитання
1) В чому полягає принципова перевага коду Хаффмена відносно кода Шеннона-Фано, завдяки якої він здобув широке практичне використання.
2) Спираючись на рис.4.8, поясніть процедуру побудування коду Хаффмана для простого прикладу.
3) Спираючись на рис.4.9, поясніть процедуру побудування коду Хаффмана для більш розгорнутого прикладу, а також кодування-декодування послідовнсті знаків.
* 4) Виконайте побудування коду Хаффмана і відповвідний приклад кодування-декодування фрагменту повідомлення для власних даних.
5) Поясніть суть статичного та динамічного способів кодування за Хаффманом, а також переваги і сфери застосування обох підходів.


4.4 Особливості адаптивного статистичного кодування

Адаптивне стискання без врахування передісторії
Цінність вивчення адаптивного кодування по Хаффману пов'язана насамперед із розумінням принципів, на які ми будемо спиратися в подальшому. Йдеться насамперед про взаємодію кодера і декодера, у яких спочатку відсутні дані про статистику знаків, однак заданий спільний алгоритм обробки (рис.4.11).

Рисунок 4.11 Узагальнена схема адаптивного кодування за Хаффманом

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

При першій появі будь-якого різновиду знаку кодер створює на дереві відповідний «лист» і привласнює знаку кодовий ланцюжок по вже знайомим нам правилам Хаффмана. Однак, оскільки для декодера даний код ще не відомий, по каналу передається звичайний вихідний байтовий код даного знаку (наприклад, в Unicode). Отримавши його і розпізнавши знак, декодер дублює всі дії з деревом на своєму боці. Очевидна не-економічність такого кодування не впливає істотного на підсумковий обсяг стисненого коду, оскільки воно використовується для кожного типу знака тільки один раз.

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

Приклад адаптивного кодування без врахування передісторії
Щоб повністю зрозуміти дію механізму динамічного статистичного кодування, розглянемо приклад кодування за таким алгоритмом послідовності знаків: Z1, Z3, Z1, Z2, Z1, Z2, Z1, Z4, Z1, Z3 (рис.4.12).

Рисунок 4.12 Приклад адаптивного кодування за Хаффманом

Кодування включає наступні кроки:

- спочатку на дереві коду (як на боці Кодера, так і у Декодера) є тільки один лист з ознакою закінчення повідомлення (знак ESC);

- при надходженні першого знака Z1 на дереві заводиться відповідна гілка з кодом "1". При цьому Декодеру передається вихідний код знака 'Z1', отримавши який він також вносить аналогічні зміни в своє дерево коду. На передачу першого знака витрачено 8 розрядів коду, але тепер при одержанні наступних знаків Z1 вони будуть кодуватися коротко;

- при надходженні наступного знака (Z3) ситуація повторюється. Однак шлях до нового знаку на дереві коду включає проміжний ділянку з кодом "0", тому Кодер передає 9 розрядів: 0'Z3'. Коли надходить ще один знак Z1, Кодер використовує для нього короткий однорозрядних код "1". При цьому модифікується лічильник надходження знаків даного типу;

- при надходженні знака Z2 знову заводиться новий лист дерева коду і в канал передається код 00'Z2' (10 розрядів). Оскільки Z2 надійшов пізніше, ніж Z3, його код 001 виявляється довшим;

- при надходженні знака Z1 він кодується одним розрядом "1" і збільшується лічильник його надходжень. Коли з'являється знак Z2, в канал передається його код 001. Після збільшення лічильника надходжень Z2 "обходить" знак Z3 по частоті появ, тому їх гілки на дереві коду міняються місцями. Надалі для Z2 буде використовуватися більш короткий код 01;

- в подальшому використовуються знайомі нам елементи алгоритму: надходження двох знаків Z1, які вже зустрічались, кодується "1"; для нового знака Z4 заводиться гілка з кодом 0001 а знак Z3 кодується як 001 в відповідності з його поточною позицією на дереві коду. Ознакою завершення повідомлення буде поява знака ESC, код якого на цей момент - 0000.

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

Контрольні запитання
1) В чому полягає особливість динамічного статистичного кодування порівняно із статичним.
2) Виходячи з рис.4.11, поясніть принцип побудови дерева кода у відсутності початкових даних про імовірності знаків.
3) Спираючись на рис.4.12, прокоментуйте покрокові дії кодера та декодера при появі декількох чергових знаків.

О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2020 • Теория информации и кодирования
UP