Розділ 7  СЛОВНИКОВІ МЕТОДИ СТИСНЕННЯ ЗІВА-ЛЕМПЕЛА

 

Раніше нами розглядалися статистичні методи стиснення інформації. Словникові алгоритми мають менш математичне обґрунтування, але більш практичний характер. Майже усі словникові методи розроблені ізраїльськими вченими Якобом Зівом (Ziv) та Абрамом Лемпелем (Lempel) і були вперше опубліковані у 1977 році.

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

Всі словникові методи можна поділити на дві групи.

До першої групи належать алгоритми з використанням «ковзного» за повідомленням вікна, розділеного на дві нерівні за об'ємом частини: перша, більша за розміром, включає фрагмент повідомлення, що вже проглянуто, – ця частина використовується як словник, друга частина вікна, набагато менша, виступає як буфер, що містить ще незакодовані символи вхідного потоку. Звичайно розмір ковзного вікна займає декілька кілобайтів, а розмір буфера - не більше 100 байтів. Алгоритми цієї групи відшукують у словнику (більшій частині вікна) ланцюжки символів, що збігаються із вмістом буфера, і замінюють ці ланцюжки покажчиками на їхнє попереднє входження у повідомлення, тобто на вміст словника. Словник в неявному вигляді міститься у закодованих даних, а зберігаються покажчики на повторювані ланцюжки символів (підрядки), що зустрічаються у повідомленні.

Усі алгоритми першої групи словникових методів базуються на алгоритмі, що має назву за іменами його авторів і роком розроблення – LZ77. Найдосконаліший представник цієї групи –алгоритм LZSS, опублікований у 1982 році Сторером (Storer) та Шиманські (Szimanski).

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

Базовий алгоритм другої групи словникових методів – алгоритм LZ78, розроблений Зівом і Лемпелем у 1978 році. Найдосконаліший представник цієї групи словникових методів – алгоритм LZW, запропонований у 1984 році Тері Уелчем.