Сімейство алгоритмів LZ78 (LZW, MW, AP, Y)

Не можна не відзначити широко відмий алгоритм Лемпеля-Зіва-Велча (Lempel-Ziv-Welch compression, LZW, LZ78). Алгоритм відрізняється високою швидкістю роботи при кодуванні та декодуванні, невибагливістю до пам’яті та проста апаратна реалізація. Недолік – менший коефіцієнт компресії порівняно зі схемою двоступеневого кодування. Наведемо принципи роботи цього алгоритму.

Створимо словник, що зберігає рядки тексту і містить близько 2-3-8 тисяч пронумерованих комірок. Запишемо до перших 256 комірок рядки, що складаються з одного символа, номер якого дорівнює номеру комірки. Алгоритм проглядає вхідний потік, розбиваючи його на підрядки і додаючи нові комірки в кінець словника.

Будемо зчитувати із вхідного потоку по одному символу, кожного разу перевіряючи, чи є вже зчитаний ланцюжок у словнику. Таким чином ми отримаємо рядок S – найдовший префікс вхідного тексту (якщо його розглядати як рядок In), який вже є у словнику. Нехай його знайдено в комірці з номером n. Виведемо число n у вихідний потік, змістимо вказівник вхідного потоку на length(S) символів наперед та додамо до словника нову комірку, що містить рядок Sc, де с – черговий символ на вході (відразу після S). За побудовою ланцюжка S ланцюжка Sc у словнику немає. Алгоритм перетворює потік символів на вході на потік індексів комірок словника на виході. При розмірі словника в 4096 комірок можна передавати 12 біт на індекс кожного ланцюжка, що знайдено.

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

Далі, кодер використовує дві операції зі словником: пошук рядка Sc, за умови, що рядок S є в словнику (та відома його позиція в ньому), а с – це наступний прочитаний символ, та додавання нової комірки, що містить цей рядок. Внаслідок цього можна обійтися структурою даних, що називається trie – деревом послідовного політерного пошуку.

Час роботи цього алгоритма лінійний за довжиною вхідного потоку та не залежить від розміру словника (для кожного символа, що зчитується, відбувається або один пошук у словнику, або додавання однієї нової комірки). Саме тому він є досить популярним в апаратних реалізаціях (приклад –протокол v42bis).

Кодер LZW додає до словника одну комірку для кожного розпізнаного ланцюжка (тому його можна назвати методом із фразо-розширюваним словником). Коли словник переповнюється, кодер може або припинити його заповнення (“заморозити” словник, як класичний LZW), або очистити (повністю – compress, частково – PKZIP shrinking). Розглянемо тепер три інших методи цього сімейства.

Алгоритм MW (Miller and Wegman), на відміну від LZW, утворює нові комірки словника шляхом склеювання двох рядків (тобто використовує фразо-інкрементний словник): розпізнавши за аналогією з LZW ланцюжок S на вході, він додає до словника нову комірку PS – конкатенацію ланцюжків Р (попереднього розпізнаного ланцюжка) та S (нового). Завдяки цьому він, як правило, швидше адаптується до тексту, але може пропустити деякі ланцюжки. Тому він стискає не набагато краще за LZW, а деколи навіть і гірше.

Алгоритм MW не є префіксним. Тому реалізація словника для нього є складним завданням: звичайно, ми можемо використовувати trie для політерного пошуку (для цього ми запам’ятаємо всі префікси всіх ланцюжків із словника), однак маємо додати до кожного вузла прапорець, що вказує, чи міститься поданий рядок у словнику. До того ж пошук по словнику може вимагати повернення: якщо словник містить рядки abc та abcde, але не містить рядка abcdef (який тільки-но прочитано зі входу), то нам доведеться спочатку зчитати його весь, щоб пересвідчитися,що в словнику його немає, а потім “прокрутити” вхідний потік назад на три символи.

Властивість префіксності можна повернути, не втративши адаптивності алгоритму MW, якщо під час розпізнавання чергового ланцюжка S після ланцюжка P додавати до словника не тільки сам ланцюжок PS (як алгоритм MW), а множину АР(P,S) – всі префікси PS, що довші за S. Маємо кодування АР (all prefixes), відкрите Сторером у 1988 р.

Алгоритм АР нарощує словник значно швидше, ніж MW. У той самий час, він зазвичай стискає краще, ніж MW.

Стосовно Y-кодування, відкритого Деніелом Бернстейном, то цей метод додає до словника один рядок на кожний прочитаний символ (подібно до АР), до того ж має властивість префіксності (подібно до LZW), тобто це – літерно-інкрементний метод з літерно-розширюваним словником.

Висновки.

По суті, всі наведені вище методи зводяться до двох основних ідей:

І нарешті, наведемо спробу класифікації методів стискання інформації:

Список використаної літератури.