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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Опис[ред.ред. код]

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

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

Алгоритм[ред.ред. код]

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

В загальному випадку такаа ситуація з'являється, коли кодується послідовнясть виду cScSc, де c — це один символ, а S — рядок, причому слово cS вже є в словнику.

Патенти[ред.ред. код]

На алгоритм 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»), який став третім по поширеності[джерело не вказано 1927 днів] в WWW, після GIF і JPEG. Наприкінці серпня 1999 року Unisys перервала дію безкоштовних ліцензій на LZW для безкоштовного та некомерційнго ПЗ, а також для користувачів неліцензійних програм, закликавLeague for Programming Freedom розгорнути кампанію «спалимо всі GIF’и» і інформувати публіку про існуючі альтернативи. Багато експертів в області патентного права відмічали, що патент не розповсюджується на пристрої, які можуть лише розтискати LZW-дані, але не стискати їх; з цієї причини популярна утиліта gzip може читати .Z-файли, але не записувати їх.

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

Див. також[ред.ред. код]