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

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

Акроним «LZW» указывает на фамилии изобретателей алгоритма: Лемпель, Зив и Велч, но многие утверждают, что, поскольку патент принадлежал Зиву[Источник?], то метод должен называться алгоритмом Зива — Лемпеля — Велча.

Содержание

Описание

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

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

Применение

На момент своего появления алгоритм LZW давал лучший коэффициэнт сжатия, для большинства приложений, чем любой другой хорошо известный метод того времени. Он стал первым широко используемым на компьютерах методом сжатия данных.

Алгоритм был реализован в программе compress, которая стала более-менее стандартной утилитой Unix-систем приблизительно в 1986 году. Несколько других популярных утилит-архиваторов также используют этот метод или близкие к нему.

В 1987 году алгоритм стал частью стандарта на формат изображений GIF. Он также может (опционально) использоваться в формате TIFF.

В настоящее время, реализация алгоритма содержится в программе Adobe Acrobat.

Пример

Данный пример показывает алгоритм LZW в действии, показывая состояние выходных данных и словаря на каждой стадии, как при кодировании, так и при раскодировании сообщения. С тем чтобы сделать изложение проще, мы ограничимся простым алфавитом — только заглавные буквы, без знаков препинания и пробелов. Сообщение, которое нужно сжать, выглядит следующим образом:

TOBEORNOTTOBEORTOBEORNOT#

Маркер # используется для обозначения конца сообщения. Тем самым, в нашем алфавите 27 символов (26 заглавных букв и #). Компьютер представляет это в виде групп бит, для представления каждого символа алфавита нам достаточно группы из 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     28: TO
O      15 =  01111     29: OB
B       2 =  00010     30: BE
E       5 =  00101     31: EO
O      15 =  01111     32: OR <--- начинаем использовать 6-битные группы
R      18 = 010010     33: RN
N      14 = 001110     34: NO
O      15 = 001111     35: OT
T      20 = 010100     36: TT
TO     28 = 011100     37: TOB
BE     30 = 011110     38: BEO
OR     32 = 100000     39: ORT
TOB    37 = 100101     40: TOBE
EO     31 = 011111     41: EOR
RN     33 = 100001     42: RNO
OT     35 = 100011     43: OT#
#       0 = 000000

Общая длина = 5*5 + 12*6 = 97 бит.

Таким образом, используя LZW мы сократили сообщение на 28 бит из 125 — это почти 22%. Если сообщение будет длиннее, то элементы словаря будут представлять всё более и более длинные части текста, благодаря чему повторяющиеся слова будут представлены очень компактно.

Декодирование

Теперь представим что мы получили закодированное сообщение, приведённое выше, и нам нужно его декодировать. Прежде всего, нам нужно знать начальный словарь, а последующие записи словаря мы можем реконструировать уже на ходу, поскольку они являются просто конкатенацией предыдущих записей.

Данные:     На выходе:     Новая запись:
                        Полная:      Частичная:
10100  = 20     T                    28: T?
01111  = 15     O       28: TO       29: O?
00010  = 2      B       29: OB       30: B?
00101  = 5      E       30: BE       31: E?
01111  = 15     O       31: EO       32: O?  <--- начинаем использовать 6-битные группы
010010 = 18     R       32: OR       33: R?
001110 = 14     N       33: RN       34: N?
001111 = 15     O       34: NO       35: O?
010100 = 20     T       35: OT       36: T?
011100 = 28     TO      36: TT       37: TO? <--- для 36, добавляем только первый элемент
011110 = 30     BE      37: TOB      38: BE?      следующего слова словаря
100000 = 32     OR      38: BEO      39: OR?
100101 = 37     TOB     39: ORT      40: TOB?
011111 = 31     EO      40: TOBE     41: EO?
100001 = 33     RN      41: EOR      42: RN?
100011 = 35     OT      42: RNO      43: OT?
000000 = 0      #

Единственная небольшая трудность может возникнуть, если новое слово словаря пересылается немедленно. В приведённом выше примере декодирования, когда декодер встречает первый символ, T, он знает, что слово 28 начинается с 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 был выдан американский патент 4,464,650, принадлежащий Sperry Corporation, позднее ставшей частью Unisys Corporation. На LZW в США были выданы два патента: 4 814 746, принадлежащий IBM, и патент Велча 4 558 302 (выдан 20 июня 1983 года), принадлежащий Sperry Corporation, позднее перешедший к Unisys Corporation. К настоящему времени, сроки всех патентов истекли.

Unisys, GIF и PNG

При разработке формата GIF в CompuServe не знали о существовании патента 4,558,302. В декабре 1994 года, когда в Unisys стало известно об использовании LZW в широко используемом графическом формате, эта компания распространила информацию о своих планах по взысканию лицензионных отчислений с коммерческих программ, имеющих возможность по созданию GIF-файлов. В то время формат был уже настолько широко распространён, что большинство компаний-производителей ПО не имели другого выхода кроме как заплатить. Эта ситуация стала одной из причин разработки графического формата PNG («PNG's Not Gif»), ставшего третьим по распространённости в WWW, после GIF и JPEG. В конце августа 1999 года Unisys прервала действие бесвозмездных лицензий на LZW для бесплатного и некоммерческого ПО, а также для пользователей нелицензированных программ, призвав League for Programming Freedom развернуть кампанию «сожжём все GIF'ы» и информировать публику об имеющихся альтернативах. Многие эксперты в области авторского права отмечали, что патент не распространяется на устройства, которые могут лишь расжимать LZW-данные, но не сжимать их; по этой причине, популярная утилита gzip может читать .Z-файлы, но не записывать их.

20 июня 2003 года истёк срок оригинального американского патента, что означает, что Unisys не может больше собирать по нему лицензионные отчисления. Аналогичные патенты в Европе, Японии и Канаде истекли в 2004 году.

См. также

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home