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

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

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

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

Акронім 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-бітні групи дають 25 = 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, що належить Sperry Corporation, яка пізніше стала частиною 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»)[2]. Наприкінці серпня 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. https://people.apache.org/~jim/NewArchitect/webrevu/1997/05_09/designers/05_09_97_1.html

Див. також
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.