Розділ 6  АДАПТИВНИЙ АЛГОРИТМ ХАФФМЕНА З УПОРЯДКОВАНИМ ДЕРЕВОМ

 

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

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

На початку роботи алгоритму дерево містить тільки один спеціальний символ <ESC>, що завжди має частоту 0. Він необхідний для занесення в кодове дерево нового символу, що передається безпосередньо після <ESC>. При появі нового символу праворуч від вузла <ESC> додається лист і потім, якщо необхідно, дерево упорядковується. Ліві гілки кодового дерева позначаються 0, а праві - 1.

Наведемо приклад впорядкованого таким чином дерева Хаффмена (рис. 2.8 а). Додамо в це дерево дві букви «А», тоді вузли «A» і «D» повинні помінятися місцями (рис. 2.8 б). Якщо додати ще дві букви «А», то потрібно поміняти місцями спочатку вузол «А» та вузол - батько «D» і «В», а потім вузол «Е» і вузол - брат «Е» (рис. 2.8 в-г).

 

                Розглянемо приклади кодування/ декодування повідомлень за адаптивним алгоритмом Хаффмена.

Приклад 1  Побудуємо адаптивний код Хаффмена для повідомлення АССВСАААВС.

Процес кодування цього повідомлення подається табл. 2.11, а відповідні зміни кодового дерева показані на рис. 2.9. Домовимося символом в лапках позначати двійковий восьмибітовий код символу за таблицею ASCII+.

 

Таблиця 2.11 

Вхідні дані             Код         Довжина

коду        Номер

дерева

А             ‘A’          8              1

С             0‘C’        9              2

С             01            2              3

В             00‘B’      10            4

С             1              1              5

А             01            2              6

А             01            2              7

А             11            2              8

В             101          3              9

С             11            2             

                               =41     

1)

Довжина стиснутого повідомлення

Lадапт.Хаффмена = 41 (біт).

 

Довжина стиснутого  повідомлення у коді

ASCII+  LASCII+ =80 (бітів).

Рисунок 2. 9

Приклад 2  Розкодуємо повідомлення ‘X’0‘F’00‘Z’1111101 100‘A’111010, закодоване за адаптивним алгоритмом Хаффмена. Обчислимо довжини кодів стиснутого та нестиснутого (ASCII+) повідомлень.

Процес декодування ілюструється табл. 2.12 і рис. 2.10.

Таблиця 2.12

Код         Символ  Довжина

Коду       Номер

дерева

‘X’          X             8              1

1)

0‘F’         F             9              2

 

 

 

 

Продовження табл. 2.12

Код         Символ  Довжина

Коду       Номер

дерева

00‘Z’       Z             10            3

11            F             2              4

11            X             2              5

101          Z             3              6

100‘A’    A             11            7

11            X             2              8

10            F             2              9

10            F             2             

                               =51     

 

Довжина стиснутого повідомлення

Lадапт.Хаффмена =51 (біт).

 

Довжина нестиснутого повідомлення у коді ASCII+  LASCII+=80 (бітів).

 

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

Зразки розв'язування задач до розділу 6

 

Приклад  1  Закодувати повідомлення СИНЯЯ СИНЕВА  СИНИ за адаптивним алгоритмом Хаффмена. Обчислити довжини коду.

Розв'язання

                Процес кодування повідомлення і відповідні зміни кодового дерева подаються в табл. 1  і на рис. 1.

Таблиця 1

Вхідні

дані         Код         Довжина

Коду       Номер

дерева

С             ‘C’          8              1

И             0‘И’        9              2

Н             00‘Н’      10            3

Я             100‘Я’    11            4

Я             001          3              5

                100‘  ’     11            6

С             101          3              7

И             00            2              8

Н             101          3              9

Е             1100‘Е’   12            10

В             11000‘В’                13            11

А             10100‘А’                13            12

                1010        4              13

С             101          3              14

И             101          3              15

Н             101          3              16

И             111          3             

 

Довжина коду стиснутого повідомлення L(X)=114 (бітів).

Довжина ASCII+коду нестиснутого повідомлення L(X)=136(бітів).

Приклад 2  Розпакувати повідомлення ‘B’0‘D’00‘C’11111 110101011011110100101, закодоване за адаптивним алгоритмом Хаффмена. Обчислити довжину стиснутого і нестиснутого повідомлення у бітах.

Розв'язання

Процес декодування ілюструється таблицею 1, відповідні зміни кодового дерева – рис. 1.

Таблиця 1

Вхідний

код          Символ  Довжина

Коду       Номер дерева

‘B’          B             8              1

0‘D’        D             9              2

00‘C’      C             10            3

11            D             2              4

11            B             2              5

11            B             2              6

101          C             3              7

0              B             1              8

101          C             3              9

101          D             3              10

11            C             2              11

101          D             3              12

0              B             1              13

0              B             1              14

101          D             3             

=53     

1)                                           

 

                Отже, закодоване повідомлення BDCDBBCBCDCDBBD.

                Довжина стиснутого повідомлення L(X)=53 (біти).

                Довжина нестиснутого повідомлення в коді ASCII+

                L(X)=158=120 (бітів).