Алгоритм Лемпеля-Зіва-Велча

LZW, Алгори́тм Ле́мпеля — Зі́ва — Ве́лча (англ. Lempel–Ziv–Welch, LZW) — універсальний алгоритм стиснення даних без втрат, створений Авраамом Лемпелем (англ. Abraham Lempel), Яковом Зівом (англ. Jacob Ziv) і Террі Велчем (англ. Terry Welch). Опублікований Велчем 1984 року як покращена реалізація алгоритму LZ78, опублікованого Лемпелем і Зівом 1978 року.

Алгоритм Лемпеля — Зіва — Велча
Коротка назва	LZW
Названо на честь	Авраам Лемпель^[1], Яков Зів^[1] і Террі Велч^[1]
Ґрунтується на	LZ78^[d]
Першовідкривач або винахідник	Авраам Лемпель, Яков Зів і Террі Велч
Конструктор	Террі Велч
Алгоритм Лемпеля — Зіва — Велча у Вікісховищі

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

Акронім LZW вказує на прізвища винахідників алгоритму: Лемпел, Зів і Велч, але багато хто стверджує, що, оскільки патент належав Зіву, то метод повинен називатися алгоритмом Зіва — Лемпеля — Велча.

Опис

Даний алгоритм при стисненні даних (кодуванні джерела) динамічно створює таблицю перетворення рядків: певним послідовностям символів ставляться у відповідність групи бітів фіксованої довжини (зазвичай 12-бітні). Таблиця ініціюється всіма 1-символьними рядками. По мірі кодування алгоритм переглядає текст символ за символом і зберігає кожен новий унікальний 2-символьний рядок в таблицю у вигляді пари код/символ, де код посилається на відповідний перший символ. Після того, як новий 2-символьний рядок збережений в таблиці, на вихід передається код першого символу. Коли на вході читається черговий символ, для нього по таблиці знаходиться рядок, що вже зустрічався, максимальної довжини, після чого в таблиці зберігається код цього рядка з наступним символом на вході; на вихід видається код цього рядка, а наступний символ використовується як початок наступного рядка.

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

Алгоритм

1. Ініціалізація словника всіма можливими односимвольними фразами. Ініціалізація вхідної фрази ω першим символом повідомлення.
2. Знайти в словнику рядок ω найбільшої довжини, який збігається з останніми прийнятими символами.
3. Зчитати черговий символ K з кодованого повідомлення.
4. Якщо КІНЕЦЬ_ПОВІДОМЛЕННЯ, то видати код для ω, інакше — крок 5.
5. Якщо фраза ωK вже є в словнику, присвоїти вхідній фразі ω значення ωK і перейти до Кроку 3, інакше видати код ω, додати ωK в словник, присвоїти вхідній фразі ω значення K і перейти до Кроку 3.
6. Кінець.

Застосування

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

Алгоритм був реалізований в програмі compress, яка стала більш чи менш стандартною утилітою Unix-систем приблизно в 1986 році. Кілька інших популярних утиліт-архіваторів також використовують цей метод або близькі до нього.

1987 року алгоритм став частиною стандарту на формат зображень GIF. Він також може (опціонально) використовуватися в форматі TIFF.

На даний момент алгоритм утримується в стандарті PDF.

Приклад

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

TOBEORNOTTOBEORTOBEORNOT# 

Маркер # використовується для позначення кінця повідомлення. Отже в нашому алфавіті 27 символів (26 прописних букв від A до Z і #). Комп'ютер представляє це у вигляді груп бітів, для представлення кожного символу алфавіту нам достатньо групи з 5 бітів на символ. По мірі росту словника розмір груп повинен рости, щоб врахувати нові елементи. 5-бітні групи дають 2⁵ = 32 можливих комбінацій бітів, тому, коли в словнику з'явиться 33-тє слово, алгоритм повинен перейти до 6-бітних груп. Зауважимо, що, оскільки використовується група з всіх нулів 00000, то 33-тя група має код 32. Початковий словник міститиме:

# = 00000 A = 00001 B = 00010 C = 00011 . . . Z = 11010 

Кодування

Без використання алгоритму LZW, при передачі повідомлення у початковому вигляді — 25 символів по 5 бітів на кожен символ — воно займає 125 бітів. Порівняємо це з тим, що отримуємо при використанні LZW:

Символ: Бітовий код: Новий запис у словнику: (на виході) T 20 = 10100 O 15 = 01111 27: TO B 2 = 00010 28: OB E 5 = 00101 29: BE O 15 = 01111 30: EO R 18 = 10010 31: OR <--- з наступного символу починаємо використовувати 6-бітні групи N 14 = 001110 32: RN O 15 = 001111 33: NO T 20 = 010100 34: OT TO 27 = 011011 35: TT BE 29 = 011101 36: TOB OR 31 = 011111 37: BEO TOB 36 = 100100 38: ORT EO 30 = 011110 39: TOBE RN 32 = 100000 40: EOR OT 34 = 100010 41: RNO # 0 = 000000 42: OT# Загальна довжина = 6*5 + 11*6 = 96 бітів. 

Таким чином, використовуючи LZW ми скоротили повідомлення на 29 бітів з 125 — це майже 22 %. Якщо повідомлення буде довшим, то елементи словника будуть представляти все більш і більш довгі частини тексту, завдяки чому слова, що повторюються, будуть представлені дуже компактно.

Декодування

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

Дані: На виході: Новий запис: Повний: Частковий: 10100 = 20 T 27: T? 01111 = 15 O 27: TO 28: O? 00010 = 2 B 28: OB 29: B? 00101 = 5 E 29: BE 30: E? 01111 = 15 O 30: EO 31: O? 10010 = 18 R 31: OR 32: R? <---- починаємо використовувати 6-бітні групи 001110 = 14 N 32: RN 33: N? 001111 = 15 O 33: NO 34: O? 010100 = 20 T 34: OT 35: T? 011011 = 27 TO 35: TT 36: TO? <---- для 37 додаємо тільки перший елемент 011101 = 29 BE 36: TOB 37: BE? наступного слова словника 011111 = 31 OR 37: BEO 38: OR? 100100 = 36 TOB 38: ORT 39: TOB? 011110 = 30 EO 39: TOBE 40: EO? 100000 = 32 RN 40: EOR 41: RN? 100010 = 34 OT 41: RNO 42: OT? 000000 = 0 # 

Єдина невелика складність може виникнути, якщо нове слово словника пересилається негайно. В приведеному вище прикладі декодування, коли декодер зустрічає перший символ «T», він знає, що слово 27 починається з «T», але чим воно закінчується? Проілюструємо проблему наступним прикладом. Ми декодуємо повідомлення «ABABA»:

Дані: На виході: Новий запис: Повний: Частковий: . . . 011101 = 29 AB 46: (word) 47: AB? 101111 = 47 AB? <--- що нам з цим робити? 

На перший погляд, для декодера це нерозв'язна задача. Ми знаємо наперед, що словом 47 повинно бути ABA, але як декодер дізнається про це?

Відмітимо, що слово 47 складається зі слова 29 плюс символ, що йде наступним. Таким чином, слово 47 закінчується на «символ, що йде наступним». Але, оскільки це слово посилається негайно, то воно повинно починатися з «символу, що йде наступним», і тому воно закінчується тим же символом, яким і починається, в даному випадку — A. Цей трюк дозволяє декодеру визначити, що слово 47 це ABA.

У загальному випадку така ситуація з'являється, коли кодується послідовність виду KωKωK, де K — це один символ, а ω — рядок, причому слово Kω вже є в словнику.

Патенти

На алгоритм (LZW) і його варіації був виданий ряд патентів, як в США, так і в других країнах. На LZ78 був виданий американський патент U.S. Patent 4,464,650, що належить , яка пізніше стала частиною Unisys Corporation. На LZW в США були видані два патенти: U.S. Patent 4,814,746, що належить IBM і патент Велча U.S. Patent 4,558,302 (виданий 20 червня 1983 року), що належав Sperry Corporation і пізніше перейшов до Unisys Corporation. На даний момент строки всіх патентів минули.

Unisys, GIF і PNG

При розробці формату GIF в CompuServe не знали про існування патенту U.S. Patent 4,558,302. У грудні 1994 року, коли в Unisys стало відомо про використання LZW в широковживаному графічному форматі, ця компанія розповсюдила інформацію про свої плани по стягненню ліцензійних відрахувань з комерційних програм, які мають можливості створення GIF-файлів. В той час формат був вже настільки широко розповсюджений, що більшість компаній-виробників ПЗ не мали іншого виходу крім як заплатити. Ця ситуація стала однією з причин розробки графічного формату PNG (неофіційна розшифровка: «PNG's Not GIF»). Наприкінці серпня 1999 року Unisys перервала дію безкоштовних ліцензій на LZW для безкоштовного та некомерційного ПЗ, а також для користувачів неліцензійних програм, що закликав Лігу за вільне програмування (англ. League for Programming Freedom) розгорнути кампанію «спалимо всі GIF'и» і інформувати публіку про існуючі альтернативи. Багато експертів в області патентного права відмічали, що патент не розповсюджується на пристрої, які можуть лише розтискати LZW-дані, але не стискати їх; з цієї причини популярна утиліта gzip може читати .Z-файли, але не записувати їх.

20 червня 2003 року закінчився строк оригінального американського патенту, що означає, що Unisys не може більше стягувати по ньому ліцензійні відрахування. Аналогічні патенти в Європі, Японії та Канаді закінчились 2004 року.

Примітки

1. http://www.digitalpreservation.gov/formats/fdd/fdd000135.shtml
2. . Архів оригіналу за 30 березня 2022. Процитовано 26 серпня 2019.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()

Див. також

• LZ77 і LZ78
• LZMA