7.2  Алгоритм LZSS

 

Алгоритм LZSS є модифікацією алгоритму LZ77. Код алгоритму починається однобітовим префіксом, що відділяє код підрядка, що збігається, від незакодованого символу. Код складається з пари <i, j> - зсуву i у словнику підрядка, що збігається з початком буфера, і довжини j цього підрядка, як і для LZ77. Вікно зсовується рівно на довжину знайденого підрядка або на 1, якщо входження підрядка буфера у словнику не знайдено.

Довжина підрядка у алгоритмі LZSS завжди більше 0 і не може перевищувати розмір буфера F, тому довжина двійкового коду довжини підрядка, що збігається, j - це округлений до більшого цілого , а довжина коду зсуву i – округлений до більшого цілого.

Приклад 2 (а)  Закодуємо за алгоритмом LZSS рядок «КРАСНАЯ КРАСКА», розмір словника 8 байтів, буфера – 5 байтів.

Кодування повідомлення подане у табл. 2.15.

Таблиця 2.15

Словник (8 Бт)      Буфер (5 Бт)          Код

                li

0              1              2              3              4              5              6              7              1              2              3              4              5                            

.               .               .               .               .               .               .               .               К             Р             А             С             Н             0‘К’        9

.               .               .               .               .               .               .               К             Р             А             С             Н             А             0‘Р’         9

.               .               .               .               .               .               К             Р             А             С             Н             А             Я             0‘А’        9

.               .               .               .               .               К             Р             А             С             Н             А             Я                             0‘С’        9

.               .               .               .               К             Р             А             С             Н             А             Я                             К             0‘Н’        9

.               .               .               К             Р             А             С             Н             А             Я                             К             Р             1<5,1>    7

.               .               К             Р             А             С             Н             А             Я                             К             Р             А             0‘Я’        9

.               К             Р             А             С             Н             А             Я                             К             Р             А             С             0‘   ’        9

К             Р             А             С             Н             А             Я                             К             Р             А             С             К             1<0,4>    7

Н             А             Я                             К             Р             А             С             К             А             .               .               .               1<4,1>    7

А             Я                             К             Р             А             С             К             А             .               .               .               .               1<0,1>    7

Довжина отриманого коду Lcode= =79+47=91 (біт).

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

Приклад 2 (б)  Розпакуємо повідомлення 0‘K’0‘P’0‘A’0‘C’ 0‘H’1<5, 1>0‘Я’0‘  ’1<0, 4>1<4, 1>1<0, 1>, закодоване за алгоритмом LZSS, довжина словника 8 байтів.

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

Таблиця 2.16

Вхідний код

                Вихід      Словник

                               0              1              2              3              4              5              6              7

0‘K’        «К»         .               .               .               .               .               .               .               К

0‘P’         «Р»         .               .               .               .               .               .               К             Р

0‘A’        «А»         .               .               .               .               .               К             Р             А

0‘C’        «С»         .               .               .               .               К             Р             А             С

0‘H’        «Н»         .               .               .               К             Р             А             С             Н

1<5, 1>   «А»         .               .               К             Р             А             С             Н             А

0‘Я’        « Я »       .               К             Р             А             С             Н             А             Я

0‘  ’         «   »         К             Р             А             С             Н             А             Я            

1<0, 4>   «КРА »   Н             А             Я                             К             Р             А             С

1<4, 1>   «К»         А             Я                             К             Р             А             С             К

1<0, 1>   « »           Я                             К             Р             А             С             К             А

 

Алгоритми LZ77, LZSS мають такі очевидні недоліки:

1)            неможливість кодування повторюваних підрядків, що знаходяться на відстані, більшій за довжину словника;

2)            довжина підрядка, який можна закодувати, обмежується розміром буфера.

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