7.3  Алгоритм LZ78

 

Авторами LZ77 був розроблений алгоритм LZ78, позбавлений недоліків LZ77 і LZSS. Цей алгоритм не використовує вікно, а зберігає словник із фраз повідомлення, що вже проглянуто.

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

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

Приклад 3 (а)  Закодуємо за алгоритмом LZ78 рядок «КРАСНАЯ КРАСКА», використовуючи словник довжиною 16 фраз.

Кодування повідомлення ілюструється табл. 2.17.

 Таблиця 2.17

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

«»                           0

«К»         <0, ‘К’>  1

«Р»         <0, ‘Р’>  2

«А»         <0, ‘А’> 3

«С»         <0, ‘С’>  4

«Н»         <0, ‘Н’> 5

«АЯ»      <3, ‘Я’>  6

«   »         <0, ‘  ’>  7

«КP»       <1, ‘Р’>  8

«АС»      <3, ‘С’>  9

«КА»      <1, ‘А’> 10

Покажчик на будь-яку фразу словника розміром 16 фраз – це ціле число від 0 до 15, для кодування якого двійковим рівномірним кодом потрібно 4 біти. Отже, довжина отриманого коду повідомлення Lcode=10(4+8) = 120 (бітів).

Приклад 3 (б)  Розкодуємо повідомлення <0,‘К’><0,‘P’> <0,‘A’><0,‘C’><0,‘H’><3,‘Я’><0,‘  ’><1,‘P’><3,‘C’><1,‘A’>, закодоване за алгоритмом LZ78; довжина словника 16 фраз.

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

    Таблиця 2.18

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

                «»            0

<0, ‘К’>  «К»         1

<0, ‘Р’>  «Р»         2

<0, ‘А’> «А»         3

<0, ‘С’>  «С»         4

<0, ‘Н’> «Н»         5

<3, ‘Я’>  «АЯ»      6

<0, ‘  ’>  «  »          7

<1, ‘Р’>  «КP»       8

<3, ‘С’>  «АС»      9

<1, ‘А’> «КА»      10