Алгоритм Лемпеля — Зіва — Велча: відмінності між версіями
[неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Вислід (обговорення | внесок) мНемає опису редагування |
CHINGO (обговорення | внесок) мНемає опису редагування |
||
Рядок 1:
{{переклад|en|Lempel–Ziv–Welch}}
'''Алгори́тм Ле́мпеля — Зіва — Ве́лча''' ('''{{lang-en|Lempel — Ziv — Welch}}''', '''LZW''') — це універсальний [[Стиснення_даних|алгоритм стиснення даних]] без втрат, створений Абрахамом Лемпелем ({{lang-en|Abraham Lempel}}),
Алгоритм розроблений так, щоб його можна було швидко реалізувати, але він не обов'язково є оптимальним, оскільки він не проводить ніякого аналізу вхідних даних.
Акронім «LZW» вказує на прізвища винахідників алгоритму: Лемпель, Зів
== Опис ==
Даний алгоритм при стисненні даних (кодуванні джерела) динамічно створює таблицю перетворення рядків: певним послідовностям символів
Алгоритму декодування на вході потрібен лише закодований текст, оскільки він може відтворювати відповідну таблицю перетворень безпосередньо по закодованому тексту.
Рядок 13:
== Алгоритм ==
# Ініціалізація словника всіма можливими односимвольними фразами. Ініціалізація вхідної фрази W першим символом
# Знайти в словнику рядок W найбільшої довжини, яка співпадає з останніми прийнятими символами.
# Зчитати черговий символ K з кодованого повідомлення.
# Якщо КІНЕЦЬ_ПОВІДОМЛЕННЯ, то видати код для W, інакше - крок 5.
# Якщо фраза WK вже є в словнику,
# Кінець.
Рядок 35:
Повідомлення, яке потрібно стиснути, виглядає наступним чином:
TOBEORNOTTOBEORTOBEORNOT#
Маркер '''#''' використовується для позначення кінця повідомлення.
# = 00000
A = 00001
Рядок 74:
=== Декодування ===
Дані: На выході: Новий запис:
Рядок 96:
000000 = 0 #
Єдина невелика складність може виникнути, якщо нове слово словника пересилається негайно. В приведеному вище прикладі декодування, коли декодер зустрічає перший символ
Дані: На выході: Новий запис:
Повний: Частковий:
Рядок 105:
101111 = 47 AB? <--- що нам з цим робити?
На перший погляд, для декодера це нерозв'язна задача. Ми знаємо наперед,
Відмітимо, що слово 47 складається зі слова 29 плюс символ, що йде наступним. Таким чином, слово 47 закінчується на «символ, що йде наступним». Але, оскільки це слово посилається негайно, то воно повинно починатися з «символа, що йде наступним», і тому воно закінчується тим же символом, яким і починається, в даному випадку — '''A'''. Цей трюк дозводяє декодеру визначити, що слово 47 це '''ABA'''.
В загальному випадку
== Патенти ==
На алгоритм [[LZW]] і його варіації був виданий ряд патентів, як в США, так і в других країнах. На LZ78 був виданий американський патент {{US patent|4,464,650}}, що належить [[Sperry Corporation]], яка пізніше стала частиною [[Unisys Corporation]]. На LZW в США
=== 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 році.
|