Алгоритм Лемпеля — Зіва — Велча: відмінності між версіями

[неперевірена версія][неперевірена версія]
Вилучено вміст Додано вміст
мНемає опису редагування
CHINGO (обговорення | внесок)
мНемає опису редагування
Рядок 1:
{{переклад|en|Lempel–Ziv–Welch}}
'''Алгори́тм Ле́мпеля — Зіва — Ве́лча''' ('''{{lang-en|Lempel — Ziv — Welch}}''', '''LZW''') — це універсальний [[Стиснення_даних|алгоритм стиснення даних]] без втрат, створений Абрахамом Лемпелем ({{lang-en|Abraham Lempel}}), ЯкобомЯковом Зівом ({{lang-en|Jacob Ziv}}) і Террі Велчем ({{lang-en|Terry Welch}}). Він був опублікований Велчем в [[1984 році]] в якості покращеної реалізації алгоритму [[LZ78]], опублікованого Лемпелем і Зівом в [[1978 році]].
Алгоритм розроблений так, щоб його можна було швидко реалізувати, але він не обов'язково є оптимальним, оскільки він не проводить ніякого аналізу вхідних даних.
 
Акронім «LZW» вказує на прізвища винахідників алгоритму: Лемпель, Зів иі Велч, але багато хто стверджує, що, оскільки патент належав Зіву, то метод повинен називатися ''алгоритмом Зіва — Лемпеля — Велча''.
 
== Опис ==
 
Даний алгоритм при стисненні даних (кодуванні джерела) динамічно створює таблицю перетворення рядків: певним послідовностям символів (словам) ставляться у відповідність групи бітів фіксованої довжини (зазвичай 12-бітні). Таблиця ініціюється всіма 1-символьними рядками (у випадку 8-бітних символів – це 256 записів). По мірі кодування алгоритм переглядає текст символ за символом і зберігає кожен новий унікальний 2-символьний рядок в таблицю у вигляді пари код/символ, де код посилається на відповідний перший символ. Після того, як новий 2-символьний рядок збережений в таблиці, на вихід передається код першого символу. Коли на вході читається черговий символ, для нього по таблиці знаходиться рядок, що вже зустрічався, максимальної довжини, після чого в таблиці зберігається код цього рядка з наступним символом на вході; на вихід видається код цього рядка, а наступний символ використовується у якості початку наступного рядка.
 
Алгоритму декодування на вході потрібен лише закодований текст, оскільки він може відтворювати відповідну таблицю перетворень безпосередньо по закодованому тексту.
Рядок 13:
== Алгоритм ==
 
# Ініціалізація словника всіма можливими односимвольними фразами. Ініціалізація вхідної фрази W першим символом повідомленнямповідомлення.
# Знайти в словнику рядок W найбільшої довжини, яка співпадає з останніми прийнятими символами.
# Зчитати черговий символ K з кодованого повідомлення.
# Якщо КІНЕЦЬ_ПОВІДОМЛЕННЯ, то видати код для W, інакше - крок 5.
# Якщо фраза WK вже є в словнику, присвоітиприсвоїти вхідній фразі W значення WK і перейти до Кроку 3, інакше видати код W, додати WK в словник, присвоїти вхідній фразі W значення K і перейти до Кроку 3.
# Кінець.
 
Рядок 35:
Повідомлення, яке потрібно стиснути, виглядає наступним чином:
TOBEORNOTTOBEORTOBEORNOT#
Маркер '''#''' використовується для позначення кінця повідомлення. ТОтжеОтже в нашому алфавіті 27 символів (26 прописних букв від A до Z і #). Комп'ютер представляє це у вигляді груп бітів, для представлення кожного символу алфавіту нам достатньо групи з 5 бітів на символ. По мірі росту словника розмір груп повинен рости, щоб врахувати нові елементи. 5-бітні групи дають 2<sup>5</sup> = 32 можнивих комбинацій бітів, тому, коли в словнику з'явиться 33-є слово, алгоритм повинен перейти до 6-бітних груп. Зауважимо, що, оскільки використовується група з всіх нулів 00000, то 33-я група має код '''32'''. Початковий словник міститиме:
# = 00000
A = 00001
Рядок 74:
 
=== Декодування ===
ТеперьТепер уявімо, що ми отримале закодоване повідомлення, наведене вище, і нам потрібно його декодувати. Перш за все нам потрібно знати початковий словник, а подальші записи словника ми можео реконструювати вже на ходу, оскільки вони являються просто конкатенацією попередніх записів.
 
Дані: На выході: Новий запис:
Рядок 96:
000000 = 0 #
 
Єдина невелика складність може виникнути, якщо нове слово словника пересилається негайно. В приведеному вище прикладі декодування, коли декодер зустрічає перший символ, "'''T'''," він знає, що слово 27 починається з "T", але чим воно закінчується? Проілюстуємо проблему наступним прикладом. Ми декодуємо повідомлення "'''ABABA'''":
Дані: На выході: Новий запис:
Повний: Частковий:
Рядок 105:
101111 = 47 AB? <--- що нам з цим робити?
 
На перший погляд, для декодера це нерозв'язна задача. Ми знаємо наперед, щословомщо словом 47 повинно бути '''ABA''', яле як декодер дізнається про це?
Відмітимо, що слово 47 складається зі слова 29 плюс символ, що йде наступним. Таким чином, слово 47 закінчується на «символ, що йде наступним». Але, оскільки це слово посилається негайно, то воно повинно починатися з «символа, що йде наступним», і тому воно закінчується тим же символом, яким і починається, в даному випадку — '''A'''. Цей трюк дозводяє декодеру визначити, що слово 47 це '''ABA'''.
 
В загальному випадку такаатака ситуація з'являється, коли кодується послідовнястьпослідовність виду ''cScSc'', де ''c'' — це один символ, а ''S'' — рядок, причому слово ''cS'' вже є в словнику.
 
== Патенти ==
На алгоритм [[LZW]] і його варіації був виданий ряд патентів, як в США, так і в других країнах. На LZ78 був виданий американський патент {{US patent|4,464,650}}, що належить [[Sperry Corporation]], яка пізніше стала частиною [[Unisys Corporation]]. На LZW в США білибули видані два патенти: {{US patent|4,814,746}}, що належить [[IBM]] і патент Велча {{US patent|4,558,302}} (виданий [[20 червня]] [[1983 року]]), що належитьналежав Sperry Corporation, і пізніше перейшов до Unisys Corporation. На даний момент сроки всіх патентів збігли.
 
=== Unisys, GIF і PNG ===
При розробці формату [[GIF]] в CompuServe не знали про існування патенту {{US patent|4,558,302}}. В грудні 1994 року, колив Unisys стало відомо про використання LZW в широковживаному графічному форматі, ця компанія розповсюдила інформацію про свої плани по стягненню ліцензійних відрахувань з комерційних програм, які мають можливості створення GIF-файлів. В той час формат був вже настільки широко розповсюджений, що більшість компаній-виробників ПЗ не мали іншого виходу крім як заплатити. Ця ситуація стала однією з причин розробки графічного формату [[PNG]] (неофіційна розшифровка: «PNG’s Not GIF»), який став третім по поширеності {{нет АИ|3|07|2009}} в [[World Wide Web|WWW]], після GIF і [[JPEG]]. Наприкінці серпня 1999 року Unisys перервала дію безкоштовних ліцензій на LZW для безкоштовного та некомерційнго ПЗ, а також для користувачів неліцензійних програм, що закликав ''League for Programming Freedom'' розгорнути кампанію «спалимо всі GIF’и» і інформувати публіку про існуючі альтернативи. Багато експертів в області патентного права відмічали, що патент не розповсюджується на пристрої, які можуть лише розтискати LZW-дані, але не стискати їх; з цієї причини популярна утиліта [[gzip]] може читати .Z-файли, але не записувати їх.
 
[[20 червня]] [[2003 року]] закінчився срок оригінального американського патенту, що означає, що Unisys не може більше стягувати по ньому ліцензійні відрахування. Аналогічні патенти в Європі, Японії та Канаді закінчились в 2004 році.