Вікіпедія

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

Інтерактивний перегляд історії
[неперевірена версія][неперевірена версія]
← Попереднє редагуванняНаступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
CHINGO (обговорення | внесок)
57 редагувань
Немає опису редагування
стильові правлення
Рядок 15:
 
# Ініціалізація словника всіма можливими односимвольними фразами. Ініціалізація вхідної фрази ω першим символом повідомлення.
# Знайти в словнику рядок ω найбільшої довжини, якаякий співпадаєзбігається з останніми прийнятими символами.
# Зчитати черговий символ K з кодованого повідомлення.
# Якщо КІНЕЦЬ_ПОВІДОМЛЕННЯ, то видати код для ω, інакше - крок 5.
Рядок 33:
== Приклад ==
 
Даний приклад показує алгоритм LZW в дії, зображуючи стан вихідних даних і словника на кожній стадаїстадії, як при кодуванні, так і при розкодуванні повідомлення. Щоб зробити вкладення простішим, ми обмежимося простим алфавітом — тільки прописні букви, без знаків пунктуації і пробілів.
Повідомлення, яке потрібно стиснути, виглядає наступним чином:
TOBEORNOTTOBEORTOBEORNOT#
Маркер '''#''' використовується для позначення кінця повідомлення. Отже в нашому алфавіті 27 символів (26 прописних букв від A до Z і #). Комп'ютер представляє це у вигляді груп бітів, для представлення кожного символу алфавіту нам достатньо групи з 5 бітів на символ. По мірі росту словника розмір груп повинен рости, щоб врахувати нові елементи. 5-бітні групи дають 2<sup>5</sup> = 32 можнивихможливих комбинаційкомбінацій бітів, тому, коли в словнику з'явиться 33-є слово, алгоритм повинен перейти до 6-бітних груп. Зауважимо, що, оскільки використовується група з всіх нулів 00000, то 33-я група має код '''32'''. Початковий словник міститиме:
# = 00000
A = 00001
Рядок 72:
Загальна довжина = 6*5 + 11*6 = 96 бітів.
 
Таким чином, використовуєчивикористовуючи LZW ми скоротили повідомлення на 29 бітів з 125 — це майже 22 %. Якщо повідомлення буде довшим, то елементи словника будуть представляти все більш і більш довгі частини тексту, завдяки чому слова, що повторюються, будуть представлені дуже компактно.
 
=== Декодування ===
Тепер уявімо, що ми отрималеотримали закодоване повідомлення, наведене вище, і нам потрібно його декодувати. Перш за все нам потрібно знати початковий словник, а подальші записи словника ми можемо реконструювати вже на ходу, оскільки вони являються просто конкатенацією попередніх записів.
 
Дані: На выходівиході: Новий запис:
Повний: Частковий:
10100 = 20 T 27: T?
Рядок 97:
000000 = 0 #
 
Єдина невелика складність може виникнути, якщо нове слово словника пересилається негайно. В приведеному вище прикладі декодування, коли декодер зустрічає перший символ "'''T'''" він знає, що слово 27 починається з "T", але чим воно закінчується? ПроілюстуємоПроілюструємо проблему наступним прикладом. Ми декодуємо повідомлення "'''ABABA'''":
Дані: На выходівиході: Новий запис:
Повний: Частковий:
.
Рядок 106:
101111 = 47 AB? <--- що нам з цим робити?
 
На перший погляд, для декодера це нерозв'язна задача. Ми знаємо наперед, що словом 47 повинно бути '''ABA''', ялеале як декодер дізнається про це?
Відмітимо, що слово 47 складається зі слова 29 плюс символ, що йде наступним. Таким чином, слово 47 закінчується на «символ, що йде наступним». Але, оскільки це слово посилається негайно, то воно повинно починатися з «символасимволу, що йде наступним», і тому воно закінчується тим же символом, яким і починається, в даному випадку — '''A'''. Цей трюк дозводяєдозволяє декодеру визначити, що слово 47 це '''ABA'''.
 
ВУ загальному випадку така ситуація з'являється, коли кодується послідовність виду KωKωK, де K — це один символ, а ω — рядок, причому слово Kω вже є в словнику.
 
== Патенти ==
Рядок 115:
 
=== 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 році.
Отримано з https://uk.wikipedia.org/wiki/Алгоритм_Лемпеля_—_Зіва_—_Велча