Алгоритм LZW

Даний алгоритм (алгоритм LZW ⁷⁾ )є модифікацією іншого методу від Абрахама Лемпеля (Abraham Lempel) і Якоба Зива (Jacob Ziv) - LZ78 [56]. Автор модифікації - Терри Уэлч (Terry Welch) [51]. Словник у даному алгоритмі являє собою таблицю, що заповнюється ланцюжками елементів у міру роботи алгоритму. Причому під час декодування словник буде побудований автоматично, отже, немає потреби зберігати його разом зі стислою послідовністю. Звичайно таблиця инициализируется так, що перші рядки заповнені всіма різними ланцюжками з одного елемента. У процесі стиску відшукується найбільш довгий ланцюжок, уже записана в словник. Щораз, коли новий ланцюжок елементів не знайдений у словнику, вона додається в словник; при цьому записується код ланцюжка, для якої є збіг зі словником. У теорії на розмір таблиці не накладається обмежень, однак обмеження на розмір дозволяє поліпшити ступінь стиску, тому що накопичуються непотрібні (можливо, що більше не зустрічаються) ланцюжка. Чим більше входжень має таблиця, тим більше інформації потрібно виділяти для зберігання кодів. Відповідно резервується спеціальний код, що позначає очищення таблиці (точніше, приведення її до вихідного стану).

// elem - елемент, chain - ланцюжок елементів// in - вхід, out - вихід// Table - таблиця ланцюжків// Table.Find - повертає код, що відповідає// ланцюжку (0 інакше) str = ""; // порожній ланцюжокwhile(in.Read(elem)) // поки є дані{ // перевіряємо, є чи вже в таблиці новий ланцюжок if(Table.Find(chain + elem)) { // є // збережемо новий ланцюжок для майбутніх перевірок chain = chain + elem; } else { // немає // запишемо код, що відповідає chain out.Write(Table.Find(chain)); // додаємо в словник Table.Add(chain + elem); chain = elem; }}//залишається один неопрацьований ланцюжокout.Write(Table.Find(chain));

Лістинг 13.4. Алгоритм стиску LZW

Розглянемо приклад стиску алгоритмом. Будемо, як і в попередньому пункті, стискати рядок "TOBEORNOTTOBE". Нехай таблиця инициализирована 256 символами коду ASCII. Припускаємо, що таблиця може містити 512 входжень, тобто нам потрібно зберігати 9 біт для кожного коду; для зручності нехай вихідний словник виглядає так:

рядок	код
T
O
B
E
R
N
...	...
СLT

Тут CLT означає "очистити (инициализировать) таблицю".

самий довгий ланцюжок, що збігся, - "T", вихід - {1}, словник:

рядок	код
T
O
B
E
R
N
...	...
СLT
TO

самий довгий ланцюжок, що збігся, - "O", вихід - {2}, словник має такий вигляд:

рядок	код
...	...
OB

Далі подібним чином у вихід записується послідовність {3}{4}{1}{5}{6}{2}, після цього

самий довгий ланцюжок, що збігся, - "T", вихід: {1}, словник має такий вигляд:

рядок	код
...	...
TO
OB
BE
EO
OR
RN
NO
OT
TT

самий довгий ланцюжок, що збігся, - "TO", вихід: {257}, словник має такий вигляд:

рядок	код
...	...
TOB

самий довгий ланцюжок, що збігся, - "BE", вихід: {259}.

У результаті закодована послідовність виглядає так: {CLT}{1}{2}{3}{4}{1}{5}{6}{2}{1}{257}{259} (звичайно на початку закодованої послідовності записують код очищення таблиці для спрощення декодера). Отримана послідовність має обсяг 108 біт (без обліку позначення кінця послідовності), що більше, ніж вихідна (104 біта). У цьому випадку це обумовлено занадто малою довжиною вихідної послідовності. Однак уже згадуваний мал. 13.1 кодового дерева Хаффмена стискується за допомогою даного алгоритму з вихідних 420 кілобайт до290 кілобайт.

// chain - ланцюжок незакодованих елементів// in - вхід, out - вихід// lcode, code - елемент закодованої послідовності// Table - таблиця ланцюжків// Table.Get(code) - повертає ланцюжок з кодом code// Table.IsOccupied(code) - є чи запис у словнику для code// Firstelem(chain) - повертає перший елемент ланцюжка while(in.Read(code)) // поки є дані{ if(code == CLT) //прочитаний код очищення таблиці? { // да Table.Init(); If (!in.Read(code)) break; // більше немає інформації out.Write(Table.Find(code)); lcode = code; } else { // немає if(Table.IsOccupied(code)) { out.Write(Table.Find(code)); // заповнюємо словник новим ланцюжком Table.Add(Table.Find(lcode) + Firstelem(Table.Find(code))); lcode = code; } else { // code не має відповідного ланцюжка chain = Table.Find(lcode) + Firstelem(Table.Find(lcode)); out.Write (chain); // запишемо ланцюжок Table.Add (chain); // і додамо в таблицю lcode = code; } }}

Лістинг 13.5. Алгоритм декодування LZW

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

До достоїнств алгоритму можна віднести високий ступінь стиску й досить високу швидкість як стиску, так і разжатия. До недоліків донедавна відносили патентну захищеність алгоритму, однак із середини 2004 року цей недолік не актуальний.

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

Дата добавления: 2014-01-07