7.4  Алгоритм LZW

 

Алгоритм LZW є модифікацією LZ78. Алгоритм починає роботу зі словника розміром 4К, що містить за адресами від 0 до 255 посилання на окремі символи (таблиця ASCII+), а від 256 до 4095 - посилання на підрядки завдовжки більше одного символу. У процесі кодування текст розбивається на підрядки, де кожний новий підрядок є найдовшою фразою, що збігається, що вже проглянуто, плюс один символ. Новий підрядок кодується індексом його префікса (фрази словника) і символом, що порушив збіг, після чого нова фраза заноситься у словник (таблицю рядків). При переповнюванні словника з нього видаляється або найменш уживана фраза, або усі підрядки завдовжки більше одного символу.

Наведемо покроковий опис алгоритму кодування.

Крок 1  Ініціалізація словника усіма можливими односимвольними фразами (звичайно це 256 символів ASCII+). Ініціалізація вхідної фрази w першим символом повідомлення.

Крок 2  Зчитування наступного символу K повідомлення.

Крок 3  Якщо це символ-КІНЕЦЬ_ПОВІДОМЛЕННЯ

    Видати код для w

      КІНЕЦЬ.

  Якщо фраза wK вже є у словнику

    Привласнити вхідній фразі w значення wK

    Перейти до кроку 2

  Інакше

   Видати код w

    Додати wK у словник

   Привласнити вхідній фразі w значення символу K

   Перейти до кроку 2. 

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

Приклад 4 (а)  Закодуємо за алгоритмом LZW рядок «КРАСНАЯ КРАСКА». Розмір словника 500 фраз.

Процес кодування повідомлення показаний у табл. 2.19.

Таблиця 2.19

Вхідна фраза wK

(словник)               Код w     Індекс фрази

ASCII+                  0 – 255

«КP»       0‘К’        256

«РА»      0‘Р’         257

«АС»      0‘А’        258

«СН»      0‘С’        259

«НА»      0‘Н’        260

«АЯ»      0‘А’        261

«Я   »      0‘Я’        262

«   К»      0‘  ’         263

«КРА»    <256>     264

«АСК»   <258>     265

«КА»      0‘К’        266

«А»         0‘А’       

Довжина отриманого коду Lcode=12=108 (б).

Наведемо процедуру кодування за алгоритмом LZW:

Read a character K

Set w=K

 Loop

   read a character K

    if wK exists in the dictionary

       w=wK

    Else    

      output the code for w

      add wK to the string table

      w=K

 End loop.

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

При декодуванні за алгоритмом LZW потрібно дотримуватися такого правила: словник поповнюється тільки після зчитування першого символу фрази, що розкодовується із наступного за поточним коду.

Приклад 4 (б)  Розпакуємо повідомлення 0'К'0'Р'0'А'0'С' 0'Н'0'А'0'Я'0'  '<256><258>0'К'0'А', закодоване за алгоритмом LZW; довжина словника 500 фраз.

Розпаковування повідомлення подане у табл. 2.20.

Таблиця 2.20

Вхідний

код          Вихід      Словник Індекс фрази

                               ASCII+   0 – 255

0‘К’        «К»         «КP»       256

0‘Р’         «Р»         «РА»      257

0‘А’        «А»         «АС»      258

0‘С’        «С»         «СН»      259

0‘Н’        «Н»         «НА»      260

0‘А’        «А»         «АЯ»      261

0‘Я’        «Я»         «Я   »      262

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

Вхідний

код          Вихід      Словник Індекс фрази

0‘  ’         «   »         «   К»      263

<256>     «КР»       «КРА»    264

<258>     «АС»      «АСК»   265

0‘К’        «К»         «КА»      266

0‘А’        «А»         «А»        

 

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

 

 

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

 

Приклад 1  Закодувати повідомлення СИНЯЯ СИНЕВА СИНИ, використовуючи словникові алгоритми LZ77, LZSS, розмір словника – 12 байтів, буфера – 4 байти. Обчислити довжини кодів.

Розв'язання

                Закодуємо повідомлення за алгоритмом LZ77 (табл.1).

Таблиця 1

Словник (12)         Буфер (4)               Код

0              1              2              3              4              5              6              7              8              9              10            11            1              2              3              4               

.               .               .               .               .               .               .               .               .               .               .               .               С             И             Н             Я                <0, 0, ‘С’>

.               .               .               .               .               .               .               .               .               .               .               С             И             Н             Я             Я                <0, 0, ‘И’>

.               .               .               .               .               .               .               .               .               .               С             И             Н             Я             Я                             <0, 0, ‘Н’>

.               .               .               .               .               .               .               .               .               С             И             Н             Я             Я                             С                <0, 0, ‘Я’>

.               .               .               .               .               .               .               .               С             И             Н             Я             Я                             С             И                <11,1,‘  ’>

.               .               .               .               .               .               С             И             Н             Я             Я                             С             И             Н             Е                <6, 3, ‘Е’>

.               .               С             И             Н             Я             Я                             С             И             Н             Е             В             А                            С                <0, 0, ‘В’>

.               С             И             Н             Я             Я                             С             И             Н             Е             В             А                            С             И                <0, 0, ‘А’>

С             И             Н             Я             Я                             С             И             Н             Е             В             А                            С             И             Н                <5, 4, ‘И’>

                С             И             Н             Е             В             А                            С             И             Н             И                                                                           

 

                Отже, код повідомлення такий: <0, 0, ‘С’> <0, 0, ‘И’> <0, 0, ‘Н’> <0, 0, ‘Я’> <11, 1, ‘  ’> <6, 3, ‘Е’> <0, 0, ‘В’> <0, 0, ‘А’> <5, 4, ‘И’>.

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

(бітів).

                Довжина нестиснутого повідомлення LASCII+=178=136 (бітів).

               

                Закодуємо повідомлення за алгоритмом LZSS (табл.2).

Таблиця 2

Словник (12)         Буфер (4)               Код

0              1              2              3              4              5              6              7              8              9              10            11            1              2              3              4               

.               .               .               .               .               .               .               .               .               .               .               .               С             И             Н             Я                0‘С’

.               .               .               .               .               .               .               .               .               .               .               С             И             Н             Я             Я                0‘И’

.               .               .               .               .               .               .               .               .               .               С             И             Н             Я             Я                             0‘Н’

.               .               .               .               .               .               .               .               .               С             И             Н             Я             Я                             С                0‘Я’

.               .               .               .               .               .               .               .               С             И             Н             Я             Я                             С             И                1<11,1>

.               .               .               .               .               .               .               С             И             Н             Я             Я                             С             И             Н                0‘  ’

.               .               .               .               .               .               С             И             Н             Я             Я                             С             И             Н             Е                1<6,3>

.               .               .               С             И             Н             Я             Я                             С             И             Н             Е             В             А                             0‘Е’

.               .               С             И             Н             Я             Я                             С             И             Н             Е             В             А                            С                0‘В’

.               С             И             Н             Я             Я                             С             И             Н             Е             В             А                            С             И                0‘А’

С             И             Н             Я             Я                             С             И             Н             Е             В             А                            С             И             Н                1<5,4>

Я                             С             И             Н             Е             В             А                            С             И             Н             И                                                            1<10,1>

 

                Отже, код повідомлення такий: 0‘С’ 0‘И’ 0‘Н’ 0‘Я’  1<11, 1> 0‘  ’ 1<6, 3> 0‘Е’ 0‘В’ 0‘А’ 1<5, 4> 1<10, 1>.

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

                (бітів).

                Довжина нестиснутого повідомлення LASCII+=178=136 (бітів).

Приклад 2  Розпакувати повідомлення, закодовані за алгоритмами LZ77 і LZSS, і обчислити довжини їх кодів:

 повідомлення стиснуте за алгоритмом LZ77 (розмір словника – 12 байтів, буфера – 4 байти). Код повідомлення такий: <0, 0, ‘A’> <0, 0,‘F’><0, 0,‘X’><9, 2,‘F’><8, 1, ‘F’><6, 2,‘X’><4, 3,‘A’>;

 повідомлення стиснуте за алгоритмом LZSS (розмір словника – 12 байтів, буфера – 4 байти). Код повідомлення такий: 0‘A’0‘F’  0‘X’ 1<9, 2>1<8, 2> 1<6, 3> 1<4, 4> 1<9, 1>.

Розв'язання

а)             Декодування повідомлення за алгоритмом LZ77 подане такою таблицею (табл. 1):

Таблиця 1

Вхідний

код          Вихідна фраза       Словник (12 байтів)

                               0              1              2              3              4              5              6              7              8              9              10            11

<0, 0, ‘A’>             “A”         .               .               .               .               .               .               .               .               .               .               .               A

<0, 0, ‘F’>              “F”          .               .               .               .               .               .               .               .               .               .               A             F

<0, 0, ‘X’>             “X”         .               .               .               .               .               .               .               .               .               A             F             X

<9, 2, ‘F’>              “AFF”     .               .               .               .               .               .               A             F             X             A             F             F

<8, 1, ‘F’>              “XF”       .               .               .               .               A             F             X             A             F             F             X             F

<6, 2, ‘X’>             “XAX”   .               A             F             X             A             F             F             X             F             X             A             X

<4, 3, ‘A’>             “AFFA”  A             F             F             X             F             X             A             X             A             F             F             A

 

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

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

 (бітів).

                Довжина нестиснутого повідомлення LASCII+=158=120 (бітів).

               

б)            Процес декодування повідомлення за алгоритмом LZSS ілюструється такою таблицею (табл. 2):

Таблиця 2

Вхідний

код          Вихідна фраза       Словник (12 байтів)

                               0              1              2              3              4              5              6              7              8              9              10            11

0‘A’        “A”         .               .               .               .               .               .               .               .               .               .               .               A

0‘F’         “F”          .               .               .               .               .               .               .               .               .               .               A             F

0‘X’        “X”         .               .               .               .               .               .               .               .               .               A             F             X

1<9, 2>   “AF”       .               .               .               .               .               .               .               A             F             X             A             F

1<8, 2>   “FX”       .               .               .               .               .               A             F             X             A             F             F             X

1<6, 3>   “FXA”    .               .               A             F             X             A             F             F             X             F             X             A

1<4, 4>   “XAFF”  X             A             F             F             X             F             X             A             X             A             F             F

1<9, 1>   “A”         A             F             F             X             F             X             A             X             A             F             F             A

 

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

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

                 (бітів).

                Довжина нестиснутого повідомлення LASCII+=158=120 (бітів).

Приклад 3  Закодувати повідомлення СИНЯЯ СИНЕВА СИНИ, використовуючи алгоритми LZ78 (розмір словника – 16 фраз), LZW (словник ASCII+ і 16 фраз). Обчислити довжину кодів.

Розв'язання

                Закодуємо повідомлення за алгоритмом LZ78 (табл. 1):

                                        Таблиця 1

Вхідна

фраза      Код         Позиція

словника

“”                            0

“С”          <0, ‘С’>  1

“И”         <0, ‘И’> 2

“Н”         <0, ‘Н’> 3

“Я”          <0, ‘Я’>  4

“Я   ”       <4, ‘  ’>  5

“СИ”       <1, ‘И’> 6

“НЕ”       <3, ‘Е’>  7

“В”          <0, ‘В’>  8

“А”         <0, ‘А’> 9

“   ”         <0, ‘  ’>  10

“СИН”    <6, ‘Н’> 11

“И”         <0, ‘И’>

 

                Отже, отримуємо такий код: <0, ‘С’> <0, ‘И’> <0, ‘Н’> <0, ‘Я’> <4, ‘  ’> <1, ‘И’> <3, ‘Е’> <0, ‘В’> <0, ‘А’> <0, ‘  ’> <6, ‘Н’> <0, ‘И’>.

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

                               (біти).

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

 

                Закодуємо повідомлення за алгоритмом LZW (табл. 2):

                                       Таблиця 2

Вхідна

фраза      Код         Позиція

словника

ASCII+                  0 - 255

“СИ”       0‘С’        256

“ИН”      0‘И’        257

“НЯ”       0‘Н’        258

“ЯЯ”       0‘Я’        259

“Я   ”       0‘Я’        260

“   С”       0‘  ’         261

“СИН”    <256>     262

“НЕ”       0‘Н’        263

“ЕВ”       0‘Е’         264

“ВА”       0‘В’        265

“А   ”      0‘А’        266

“   СИ”    <261>     267

“ИНИ”   <257>     268

“И”         0‘И’       

 

                Отже, LZW-код повідомлення такий: 0‘С’ 0‘И’ 0‘Н’ 0‘Я’ 0‘Я’ 0‘  ’ <256> 0‘Н’ 0‘Е’ 0‘В’ 0‘А’ <261> <257> 0‘И’.

                Довжина коду (бітів).

Приклад 4  Розпакувати повідомлення, закодовані за алгоритмами LZ78 і LZW. Обчислити довжину їх кодів.

Повідомлення стиснуте за алгоритмом LZ78 (словник містить 16 фраз). Код стиснутого повідомлення такий: <0, ‘A’> <0, ‘F’> <0, ‘X’> <1, ‘F’> <2, ‘X’> <5, ‘A’> <3, ‘A’> <2, ‘F’> <0, ‘A’>;

Повідомлення стиснуте за алгоритмом LZW (словник містить таблицю ASCII+ і 16 фраз). Код стиснутого повідомлення такий: 0‘A’ 0‘F’ 0‘X’ <256> <257> <257> 0‘A’ <258> 0‘F’ 0‘F’ 0‘A’.

Розв'язання

а)             Розпакуємо код повідомлення, стиснутого за алгоритмом LZ78 (табл. 1):

                                   Таблиця 1

Вхідний

код          Вихідна фраза

(словник)               Позиція

словника

                “”            0

<0, ‘A’> “A”         1

<0, ‘F’>  “F”          2

<0, ‘X’> “X”         3

<1, ‘F’>  “AF”       4

<2, ‘X’> “FX”       5

<5, ‘A’> “FXA”    6

<3, ‘A’> “XA”      7

<2, ‘F’>  “FF”        8

<0, ‘A’> “A”        

 

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

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

Довжина нестиснутого повідомлення LASCII+=158=120 (бітів).

б)            Розпакуємо повідомлення за алгоритмом LZW (табл.2):

                               Таблиця 2

Вхідний

код          Вихідна

фраза      Словник Позиція

словника

                               ASCII+   0 – 255

0‘A’        “A”         “AF”       256

0‘F’         “F”          “FX”       257

0‘X’        “X”         “XA”      258

<256>     “AF”       “AFF”     259

<257>     “FX”       “FXF”     260

<257>     “FX”       “FXA”    261

0‘A’        “A”         “AX”      262

<258>     “XA”      “XAF”    263

0‘F’         “F”          “FF”        264

0‘F’         “F”          “FA”       265

0‘A’        “A”                        

 

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

Довжина стиснутого повідомлення  Lcode=11*9=99 (бітів).

Задачі до розділу 7

 

Закодувати повідомлення AABCDAACCCCDBB, використовуючи словникові алгоритми стиснення LZ77 і LZSS (словник - 12 байтів, буфер – 4 байти). Обчислити довжину у бітах отриманих кодів.

Закодувати повідомлення КИБЕРНЕТИКИ, використовуючи словникові алгоритми стиснення LZ77 і LZSS (словник - 12 байтів, буфер – 4 байти). Обчислити довжину у бітах отриманих кодів.

Закодувати повідомлення СТРАННЫЙ СТРАННИК, використовуючи словникові алгоритми стиснення LZ77 і LZSS (словник - 12 байтів, буфер – 4 байти). Обчислити довжину у бітах отриманих кодів.

Закодувати повідомлення BDCBDDCDCBCBDDBDBDBC, використовуючи словникові алгоритми стиснення LZ77 і LZSS (словник - 12 байтів, буфер – 4 байти). Обчислити довжину у бітах отриманих кодів.

Розпакувати повідомлення і обчислити довжину їх кодів:

повідомлення стиснуте за алгоритмом LZ77 (словник – 12 байтів, буфер – 4 байти), код повідомлення такий: 0, 0, ‘A’ 11, 1, ‘B’ 0, 0, ‘C’ 0, 0, ‘D’ 7, 2,‘C’ 11,1,‘C’ 5, 2, ‘B’ 0, 0, ‘B’;

повідомлення стиснуте за алгоритмом LZSS (словник – 12 байтів, буфер – 4 байти), код повідомлення такий: 0‘A’ 111, 1 0‘B’ 0‘C’ 0‘D’ 17, 2 18, 1 111, 1 110, 2 15, 1 12, 1 111, 1.

Розпакувати повідомлення і обчислити довжину їх кодів:

повідомлення стиснуте за алгоритмом LZ77 (словник – 12 байтів, буфер – 4 байти), код повідомлення: 0,0,‘/’ 0,0,‘W’ 0,0,‘E’ 0,0,‘D’ 8,3,‘/’ 5,4,‘W’ 8,1,‘B’ 8,3,‘E’ 4,4,‘/’ 4,4,‘E’;

повідомлення стиснуте за алгоритмом LZSS (словник – 12 байтів, буфер – 4 байти), код повідомлення такий: 0‘/’ 0‘W’ 0‘E’ 0‘D’ 18,3 15,4 18,3 0‘B’ 18,3 10,4 14,4 14,2 110,1.

Розпакувати повідомлення і обчислити довжину їх кодів:

Повідомлення стиснуте за алгоритмом LZ77 (словник – 12 байтів, буфер – 4 байти), код повідомлення 0,0,‘В’ 0,0,‘О’ 0,0,‘  ’ 0,0,‘Д’ 8,2,‘Р’ 0,0,‘Е’ 6,1,‘Т’ 8,1,‘А’ 4,1,‘А’ 6,1,‘Н’ 9,2,‘Т’ 3,3,‘Е’ 6,1,‘Д’ 6,1,‘О’ 6,1,‘А’;

Повідомлення стиснуте за алгоритмом LZSS (словник – 12 байтів, буфер – 4 байти), код повідомлення 0‘В’ 0‘О’ 0‘  ’ 0‘Д’ 1<8,2>0‘Р’ 0‘Е’1<6,1>0‘Т’ 1<8,1>0‘А’1<4,1>1<10,1>1<6,1>0‘Н’ 1<9,2> 1<3,4> 0‘Е’ 1<6,1> 0‘Д’ 1<6,1> 0‘О’ 1<6,1> 1<4,1>. 

Закодувати повідомлення AABCDAACCCCDBB, використовуючи словникові алгоритми стиснення LZ78 (словник - 16 фраз) і LZW (словник – ASCII+ і 16 фраз). Обчислити довжину отриманих кодів.

Закодувати повідомлення КИБЕРНЕТИКИ, використовуючи словникові алгоритми стиснення LZ78 (словник - 16 фраз) і LZW (словник – ASCII+ і 16 фраз). Обчислити довжину отриманих кодів.

Закодувати повідомлення СТРАННЫЙ СТРАННИК, використовуючи словникові алгоритми LZ78 (словник - 16 фраз) і LZW (словник – ASCII+ і 16 фраз). Обчислити довжину у бітах отриманих кодів.

Закодувати повідомлення BDCBDDCDCBCBDDBDBDBC, використовуючи словникові алгоритми LZ78 (словник - 16 фраз) і LZW (словник – ASCII+ і 16 фраз). Обчислити довжини у бітах отриманих кодів.

Розпакувати повідомлення і обчислити довжину їх кодів:

повідомлення стиснуте за алгоритмом LZ78 (словник – 16 фраз). Код повідомлення такий: 0,‘A’ 1,‘B’ 0,‘C’ 0,‘D’ 1,‘А’ 3,‘C’ 6,‘D’ 0,‘B’ 0,‘B’;

повідомлення стиснуте за алгоритмом LZW (словник ASCII+ і 16 фраз). Код повідомлення такий: 0‘A’ 0‘A’ 0‘B’ 0‘C’ 0‘D’ 256 0‘C’ 262 259 0‘B’ 0‘B’.

Розпакувати повідомлення і обчислити довжину їх кодів:

повідомлення стиснуте за алгоритмом LZ78 (словник – 16 фраз). Код стиснутого повідомлення: 0,‘/’ 0,‘W’ 0,‘E’ 0,‘D’ 1,‘W’ 3,‘/’ 2,‘E’ 4,‘/’ 7,‘B’ 5,‘E’ 6,‘W’ 3,‘B’ 10,‘E’ 1,‘E’;

повідомлення стиснуте за алгоритмом LZW (словник ASCII+ і 16 фраз). Код стиснутого повідомлення такий: 0‘/’ 0‘W’ 0‘E’ 0‘D’ 256 0‘E’ 260 259 257 0‘B’ 260 261 264 266 0‘/’ 0‘E’.

Розпакувати повідомлення і обчислити довжину їх кодів:

повідомлення стиснуте за алгоритмом LZ78 (словник – 32 фрази). Код стиснутого повідомлення такий: 0,‘В’ 0,‘О’ 0,‘  ’ 0,‘Д’ 1,‘О’ 0,‘Р’ 0,‘E’ 3,‘Т’ 6,‘А’ 1,‘А’ 3,‘Н’ 0,‘А’ 8,‘Р’ 12,‘В’ 7,‘  ’  4,‘Р’ 2,‘В’ 0,‘А’;

повідомлення стиснуте за алгоритмом LZW (словник ASCII+ і 32 фрази).Код стиснутого повідомлення такий: 0‘В’ 0‘О’0‘  ’0‘Д’256 0‘Р’ 0‘Е’ 0‘  ’ 0‘Т’ 0‘Р’ 0‘А’ 0‘В’ 0‘А’ 0‘  ’ 0‘Н’ 268 264 266 262 0‘Д’ 0‘Р’ 0‘О’ 267.