Таким чином, алгоритм Лемпеля-Зіва перетворює один потік вхідних символів на два паралельних потоки length та distance. Очевидно, що ці потоки є потоками символів в алфавітах L та D, і до них можна застосувати один із вищенаведених методів (RLE, кодування Хаффмена, арифметичне кодування). Це підводить нас до ідеї дворівневого кодування, найефективнішій серед усіх, що використовуються сьогодні на практиці. Під час реалізації цього методу необхідно домогтися узгодженого виводу обох потоків в один файл. Ця проблема зазвичай розв’язується шляхом почергового запису кодів символів із обох потоків.
Не можна не відзначити широко відмий алгоритм Лемпеля-Зіва-Велча (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), тобто це – літерно-інкрементний метод з літерно-розширюваним словником.
По суті, всі наведені вище методи зводяться до двох основних ідей:
- “скорочуй те, що зустрічається часто” (статистичні методи);
- “повторюй старе” (словарні методи).
І нарешті, наведемо спробу класифікації методів стискання інформації:
1. Кохманюк Д. “Сжатие информации: как это делается”, Index PRO, 1993 К., №№ 1-2.
2. Кричевский Р.Е. Сжатие и поиск информации. – М., Радио и связь, 1989.
3. Рябко Б.Я. Сжатие информации спомощью стопки книг. // Проблемы передачи информации.- 1980, т.16, №4. С.16-21.
4. Ziv J., Lempel A. Compression of individual sequences via variable-rate coding. – IEEE Transactions, IT-24. – No.5 (Sept.1978), pp. 530-536.