Лекція 05. Статистичне стискання повідомлень
Курс “Теорія інформації та кодування”

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

Класичні результати ТІК щодо стискання повідомлень
Практичний метод статистичного стискання. Кодування за Хаффманом
Динамічне стискання за Хаффманом
«Арифметичне» статистичне кодування

5.1 Класичні результати ТІК щодо стискання повідомлень

Теорема Шеннона про ефективне кодування джерела повідомлень
Принципово важливим результатом ТІК є теорема про кодування джерела повідомлень, яка вказує на можливості та обмеження стискання коду. Ця теорема (рис 5.1), що доведена Клодом Шенноном, стверджує, що:
Існує метод кодування, який забезпечує наближення середньої довжини коду знака Lk до величини ентропії Н дискретного джерела з будь-якої необхідної точністю. З іншого боку, не існує способу, при якому середня довжина коду була б менше ентропії.

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

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

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

Між тим в якості доказу справедливості теореми Клод Шеннон запропонував практичний метод кодування (таке кодування він назвав “ефективним”, маючи на увазі саме максимальне стискання коду). Надалі ми розглянемо такий метод.

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

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

Як можна бачити, в результаті ефективного кодування, середня довжина коду знаку Lk(еф) (розряд/знак) суттєво наблизилась до безумовної ентропії Н (біт/знак) порівняно із варіантом рівномірного кодування (коли для кожного із чотирьох знаків алфавіту використовувалось по два розряди Lk(рівн)=log24=2). А якщо порівняти цей результат із типовим вихідним кодуванням знаків (де, як ми знаємо, Lk(вих) = 8), то ефективність виглядає дійсно вражаючою (зрозуміло, що йдеться лише про даний приклад).

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

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

* В якості показника ефективність стискання коду зручно зручно використвувати збитковість кодування: D=(Lk — H)/Lk. Зокрема у випадку вихідного однобайтного кодування знаків для приклада на рис.5.2 одержуємо D(вих)=(8-1,57)/8=0,80 (збитковість біля 80%), для мінімального рівномірного кодування D(рівн)=(2-1,57)/2=0,22 (збитковість біля 22%), а для ефективного кодування за Шенноном D(еф)=(1,60-1,57)/1,60=0,02 (збитковість всього біля 2%).

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

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

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

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

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

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

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

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


5.2 Практичний метод статистичного стискання. Кодування за Хаффманом

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


5.3 Динамічне стискання за Хаффманом

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

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

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

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

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

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

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

Рисунок 5.8 Приклад динамічного кодування за Хаффманом

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

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

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

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

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

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

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

Динамічне кодування із врахуванням передісторії. Метод PPM
Цей метод базується на прогнозуванні ймовірностей наступних знаків на основі передісторії, а також їх кодуванні за допомогою таблиці Хаффмана, яка постійно коригується в міру зміни статистики. Нагадаємо, що популярним втіленням такого підходу є метод PPM (Prediction by Partial Matching — передбачення по частковому співпадінню). Особливості алгоритму ілюструє рис.5.9.

Рисунок 5.9 Схема кодування із урахуванням передісторії

На етапі А в міру обробки знаків повідомлень накопичуються оцінки їх умовних ймовірностей на різну глибину. Зокрема в описі методу PPM використаний термін "контекст глибини Ki". Зокрема, контексту K0 відповідають безумовні ймовірності знаків, контексту K1 - умовні ймовірності на глибину 1 знак, К2 - на глибину 2 знака і т.д.

На етапі Б кодер пророкує ймовірності появи різних знаків в наступній позиції з урахуванням різних контекстів. При цьому "старшим" контекстам з більш глибокої пам'яті присвоюються великі ваги, як більш інформативним. Наприклад, передбачена можливість знака може розраховуватися за формулою P = 0,1*P0 + 0,3*P1 + 0,6*P2, де P0, P1 і P2 ймовірності появи знаків відповідно в контекстах K0, K1 і K2 (в сучасних архіваторах використовуються контексти аж до рівнів 5-6). Виходячи з передбачених ймовірностей знаків кодер коригує таблицю Хаффмана.

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

Нагадаємо, що синхронізація досягається за рахунок використання загальних правил зміни таблиць на стороні Кодера і Декодера. В цілому прогнозний метод забезпечує максимальну ступінь стиснення для текстів - це і є доцільна сфера його використання.

Приклад кодування за методом PPM
На рис.5.10 відображено ключовий етап методу - прогноз ймовірностей знаків в черговий позиції:

Рисунок 5.10 Приклад кодування за Хаффманом із врахуванням передісторії

- в прикладі з 23 знаків фрази “коси косой, косой Косой” оброблено наразі 16 і прогнозується значення 17-го знака. При цьому умовно передбачається використання алфавіту зі 100 символів. Так що крім 7 вже видів знаків, що вже з'являлися, можуть з'явитися ще 93. Метод передбачає початкову ініціалізацію лічильників всіх знаків із 1, що враховується при підрахунку ймовірностей;

- виходячи з підрахунку безумовних ймовірностей (контекст К0) найбільш очікувано поява літери «o». З урахуванням попередньої літери (в контексті К1 це теж «o») швидше за все може з'явитися літера "з" і також імовірна "й". А ось в контексті К2 найбільш вірогідна поява "й" (раніше вона фіксувалася в складі ланцюжка "сой"). Облік значущості контекстів дає найбільшу ймовірність букві "й" (завдяки контексту К2) і високо оцінює і ймовірність "з" (завдяки К1). Інші знаки мають значно менші ймовірності;

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

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

Контрольні запитання
1) Спираючись на узагальнену схему рис.5.7, поясніть суть динамічного підходу до кодування за Хаффманом.
2) Спираючись на приклад кодування рис.5.8, поясніть послідовність кроків динамічного кодування за Хаффманом.
3) Спираючись на узагальнену схему рис.5.9 поясніть особливості динамічного кодування із врахуванням передісторії знаків (метод PPM).
4) Спираючись на приклад кодування рис.5.10, поясніть особливості прогнозування імовірностей наступних знаків при використанні методу PPM.
5) Порівняйте методи динамічного кодування із врахуванням передісторії знаків та без неї.


5.4 «Арифметичне» статистичне кодування

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

Рисунок 5.11 Порівняння кодування за Хаффманом та арифметичного кодування.

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

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

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

Процедура арифметичного кодування повідомлень
Розглянемо процедуру арифметичного кодування на прикладі. Нехай відомо, що в повідомленнях Джерела використовуються знаки чотирьох типів з імовірностями відповідно Z1 - 0.6; Z2 - 0.2; Z3 - 0.1; Z4 - 0.1. Знайдемо двійкове число, яке однозначно визначає послідовність знаків Z1, Z3, Z2, Z1. Процедуру ілюструє рис. 5.12.

Рисунок 5.12 Приклад кодування блоку знаків арифметичним кодом

Спочатку відрізок довжиною 1,0 (яка відповідає сумарній імовірності появи знаків) розмічений відповідно до імовірностей різних знаків (в даному випадку - інтервал від 0,0 до 0,6 відповідає знаку Z1, інтервал від 0,6 до 0,8 (довжиною 0,2) - знаку Z2, а два інтервали від 0,8 до 0,9 та від 0,9 до 1,0 (довжиною по 0,1) - відповідно знакам Z3 і Z4.

По ходу появи знаків поступово уточнюються межі інтервалу, який відповідає даному ланцюжку:

- поява знака Z1 означає, що шукане число буде знаходитися в інтервалі від 0,0 до 0,6 (рівень А на ріс.5.12). Надалі цей інтервал розділяється на відрізки, довжини яких пропорційні імовірностям знаків повідомлення (рівень Б);

- знаку Z3 на відрізку від 0,0 до 0,6 відповідає інтервал 0,48-0,54. Повторюється «розмітка» інтервалу в пропорціях ймовірності знаків (рівень В);

- знаку Z2 на відрізку від 0,48 до 0,54 відповідає інтервал 0,516-0,528. Для нього повторюється та сама процедура розподілу інтервалу (рівень Г);

знаку Z1 на відрізку від 0,516-0,528 відповідає інтервал 0,516-0,5232. Поява коду ESC означає, що повідомлення закінчено.

Тепер знаходиться двійкове число мінімальної довжини, яке належить даному відрізку. У прикладі це 0,10000101. Це число відповідає десятковому значенню 0,5195 (рис.5.12). Якби ми спробували використовувати більш короткий код, то вийшли б за межі відрізка від 0,5160 до 0,5232 (зокрема число 0,1000010 відповідає 0,515625, а 1000011 - 0,52348). При цьому, зрозуміло, досить передавати тільки значущі цифри знайденого числа: 10000101 (на рисунку виділені червоним).

В даному прикладі для передачі 4-х знаків використовується 8 розрядів (2 розряду на знак) + довжина ознаки кінця коду. Це виглядає значно гірше, ніж наприклад при кодуванні по Хаффмену при аналогічних вихідних даних (там ми отримували середнє значення довжини коду 1,6 розрядів/знак). Однак, чим більше довжина кодованого ланцюжка знаків, тим більше відчувається перевага арифметичного коду. В кінцевому рахунку середня довжина коду знака прагне до ентропії.

Декодування арифметичним кодом
Процедуру декодування розглянемо на тому ж прикладі послідовності знаків Z1, Z3, Z2, Z1 (рис. 5.13):

Рисунок 5.13 Приклад декодування «арифметичним» кодом

- з Каналу передачі Декодер отримав послідовність 10000101 (яка була знайдена в прикладі кодування в попередньому пункті). Їй відповідає двійкове число 0,10000101, а тому в свою чергу - десяткове число 0,5195;

- отримане значення 0,5195 належить інтервалу 0,0-0,6, отже перший знак повідомлення – знак Z1, якому відповідає цей інтервал;

- на відрізку 0,0-0,6, який відповідає знаку Z1, значення 0,5195 потрапляє в інтервал 0,48-0,54, значить наступний знак повідомлення - Z3;

- на відрізку 0,48-0,54, який відповідає знаку Z3 за умови, що перед цим з'явився Z1, значення 0,5195 потрапляє в інтервал 0,516-0,528, значить наступний знак повідомлення - Z2;

- на відрізку 0,516-0,528, що відповідає знаку Z2, який з'явився після Z1 і Z3, значення 0,5195 потрапляє в інтервал 0,516-0,5232, значить наступний знак повідомлення - Z1. Поява знака ESC означає закінчення декодування.

Контрольні запитання
1) Поясніть суть метода арифметичного кодування та його основну перевагу відносно кодування по Хаффману.
2) Спираючись на приклад на рис.5.12, поясніть процедуру кодування ланцюжка знаків двійковим числом для заданих параметрів арифметичного кода.
* 3) Поясніть спосіб визначення межі блоку знаків для кодування арифметичним кодом. Як такий спосіб впливає на збитковість кодування.
4) Спираючись на приклад на рис.5.13, поясніть процедуру декодування двікового числа у відповідний ланцюжок знаків.
5) Прокоментуйте механізм впливу довжини блоку арифметичного коду на щільність кодування та його швидкість.
О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

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

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

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

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