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

Алгори́тм Ле́мпеля — Зи́ва — Ве́лча (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-битные группы дают 2⁵ = 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 был выдан американский патент [www.google.com/patents/US4464650 U.S. Patent 4 464 650], принадлежащий Sperry Corporation, позднее ставшей частью Unisys Corporation. На LZW в США были выданы два патента: [www.google.com/patents/US4814746 U.S. Patent 4 814 746], принадлежащий IBM, и патент Велча [www.google.com/patents/US4558302 U.S. Patent 4 558 302] (выдан 20 июня 1983 года), принадлежащий Sperry Corporation, позднее перешедший к Unisys Corporation. К настоящему времени сроки всех патентов истекли.

Unisys, GIF и PNG

При разработке формата GIF в CompuServe не знали о существовании патента [www.google.com/patents/US4558302 U.S. Patent 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 году.

См. также

• LZ
• LZ77
• LZMA

Отрывок, характеризующий Алгоритм Лемпеля — Зива — Велча

– А слышали? – сказал Шиншин. – Князь Голицын русского учителя взял, по русски учится – il commence a devenir dangereux de parler francais dans les rues. [становится опасным говорить по французски на улицах.]
– Ну что ж, граф Петр Кирилыч, как ополченье то собирать будут, и вам придется на коня? – сказал старый граф, обращаясь к Пьеру.
Пьер был молчалив и задумчив во все время этого обеда. Он, как бы не понимая, посмотрел на графа при этом обращении.
– Да, да, на войну, – сказал он, – нет! Какой я воин! А впрочем, все так странно, так странно! Да я и сам не понимаю. Я не знаю, я так далек от военных вкусов, но в теперешние времена никто за себя отвечать не может.
После обеда граф уселся покойно в кресло и с серьезным лицом попросил Соню, славившуюся мастерством чтения, читать.
– «Первопрестольной столице нашей Москве.
Неприятель вошел с великими силами в пределы России. Он идет разорять любезное наше отечество», – старательно читала Соня своим тоненьким голоском. Граф, закрыв глаза, слушал, порывисто вздыхая в некоторых местах.
Наташа сидела вытянувшись, испытующе и прямо глядя то на отца, то на Пьера.
Пьер чувствовал на себе ее взгляд и старался не оглядываться. Графиня неодобрительно и сердито покачивала головой против каждого торжественного выражения манифеста. Она во всех этих словах видела только то, что опасности, угрожающие ее сыну, еще не скоро прекратятся. Шиншин, сложив рот в насмешливую улыбку, очевидно приготовился насмехаться над тем, что первое представится для насмешки: над чтением Сони, над тем, что скажет граф, даже над самым воззванием, ежели не представится лучше предлога.
Прочтя об опасностях, угрожающих России, о надеждах, возлагаемых государем на Москву, и в особенности на знаменитое дворянство, Соня с дрожанием голоса, происходившим преимущественно от внимания, с которым ее слушали, прочла последние слова: «Мы не умедлим сами стать посреди народа своего в сей столице и в других государства нашего местах для совещания и руководствования всеми нашими ополчениями, как ныне преграждающими пути врагу, так и вновь устроенными на поражение оного, везде, где только появится. Да обратится погибель, в которую он мнит низринуть нас, на главу его, и освобожденная от рабства Европа да возвеличит имя России!»
– Вот это так! – вскрикнул граф, открывая мокрые глаза и несколько раз прерываясь от сопенья, как будто к носу ему подносили склянку с крепкой уксусной солью. – Только скажи государь, мы всем пожертвуем и ничего не пожалеем.
Шиншин еще не успел сказать приготовленную им шутку на патриотизм графа, как Наташа вскочила с своего места и подбежала к отцу.
– Что за прелесть, этот папа! – проговорила она, целуя его, и она опять взглянула на Пьера с тем бессознательным кокетством, которое вернулось к ней вместе с ее оживлением.
– Вот так патриотка! – сказал Шиншин.
– Совсем не патриотка, а просто… – обиженно отвечала Наташа. – Вам все смешно, а это совсем не шутка…
– Какие шутки! – повторил граф. – Только скажи он слово, мы все пойдем… Мы не немцы какие нибудь…
– А заметили вы, – сказал Пьер, – что сказало: «для совещания».
– Ну уж там для чего бы ни было…
В это время Петя, на которого никто не обращал внимания, подошел к отцу и, весь красный, ломающимся, то грубым, то тонким голосом, сказал:
– Ну теперь, папенька, я решительно скажу – и маменька тоже, как хотите, – я решительно скажу, что вы пустите меня в военную службу, потому что я не могу… вот и всё…
Графиня с ужасом подняла глаза к небу, всплеснула руками и сердито обратилась к мужу.
– Вот и договорился! – сказала она.
Но граф в ту же минуту оправился от волнения.
– Ну, ну, – сказал он. – Вот воин еще! Глупости то оставь: учиться надо.
– Это не глупости, папенька. Оболенский Федя моложе меня и тоже идет, а главное, все равно я не могу ничему учиться теперь, когда… – Петя остановился, покраснел до поту и проговорил таки: – когда отечество в опасности.
– Полно, полно, глупости…
– Да ведь вы сами сказали, что всем пожертвуем.
– Петя, я тебе говорю, замолчи, – крикнул граф, оглядываясь на жену, которая, побледнев, смотрела остановившимися глазами на меньшого сына.
– А я вам говорю. Вот и Петр Кириллович скажет…
– Я тебе говорю – вздор, еще молоко не обсохло, а в военную службу хочет! Ну, ну, я тебе говорю, – и граф, взяв с собой бумаги, вероятно, чтобы еще раз прочесть в кабинете перед отдыхом, пошел из комнаты.
– Петр Кириллович, что ж, пойдем покурить…
Пьер находился в смущении и нерешительности. Непривычно блестящие и оживленные глаза Наташи беспрестанно, больше чем ласково обращавшиеся на него, привели его в это состояние.
– Нет, я, кажется, домой поеду…
– Как домой, да вы вечер у нас хотели… И то редко стали бывать. А эта моя… – сказал добродушно граф, указывая на Наташу, – только при вас и весела…
– Да, я забыл… Мне непременно надо домой… Дела… – поспешно сказал Пьер.
– Ну так до свидания, – сказал граф, совсем уходя из комнаты.
– Отчего вы уезжаете? Отчего вы расстроены? Отчего?.. – спросила Пьера Наташа, вызывающе глядя ему в глаза.
«Оттого, что я тебя люблю! – хотел он сказать, но он не сказал этого, до слез покраснел и опустил глаза.
– Оттого, что мне лучше реже бывать у вас… Оттого… нет, просто у меня дела.
– Отчего? нет, скажите, – решительно начала было Наташа и вдруг замолчала. Они оба испуганно и смущенно смотрели друг на друга. Он попытался усмехнуться, но не мог: улыбка его выразила страдание, и он молча поцеловал ее руку и вышел.
Пьер решил сам с собою не бывать больше у Ростовых.


Петя, после полученного им решительного отказа, ушел в свою комнату и там, запершись от всех, горько плакал. Все сделали, как будто ничего не заметили, когда он к чаю пришел молчаливый и мрачный, с заплаканными глазами.
На другой день приехал государь. Несколько человек дворовых Ростовых отпросились пойти поглядеть царя. В это утро Петя долго одевался, причесывался и устроивал воротнички так, как у больших. Он хмурился перед зеркалом, делал жесты, пожимал плечами и, наконец, никому не сказавши, надел фуражку и вышел из дома с заднего крыльца, стараясь не быть замеченным. Петя решился идти прямо к тому месту, где был государь, и прямо объяснить какому нибудь камергеру (Пете казалось, что государя всегда окружают камергеры), что он, граф Ростов, несмотря на свою молодость, желает служить отечеству, что молодость не может быть препятствием для преданности и что он готов… Петя, в то время как он собирался, приготовил много прекрасных слов, которые он скажет камергеру.
Петя рассчитывал на успех своего представления государю именно потому, что он ребенок (Петя думал даже, как все удивятся его молодости), а вместе с тем в устройстве своих воротничков, в прическе и в степенной медлительной походке он хотел представить из себя старого человека. Но чем дальше он шел, чем больше он развлекался все прибывающим и прибывающим у Кремля народом, тем больше он забывал соблюдение степенности и медлительности, свойственных взрослым людям. Подходя к Кремлю, он уже стал заботиться о том, чтобы его не затолкали, и решительно, с угрожающим видом выставил по бокам локти. Но в Троицких воротах, несмотря на всю его решительность, люди, которые, вероятно, не знали, с какой патриотической целью он шел в Кремль, так прижали его к стене, что он должен был покориться и остановиться, пока в ворота с гудящим под сводами звуком проезжали экипажи. Около Пети стояла баба с лакеем, два купца и отставной солдат. Постояв несколько времени в воротах, Петя, не дождавшись того, чтобы все экипажи проехали, прежде других хотел тронуться дальше и начал решительно работать локтями; но баба, стоявшая против него, на которую он первую направил свои локти, сердито крикнула на него:
– Что, барчук, толкаешься, видишь – все стоят. Что ж лезть то!
– Так и все полезут, – сказал лакей и, тоже начав работать локтями, затискал Петю в вонючий угол ворот.
Петя отер руками пот, покрывавший его лицо, и поправил размочившиеся от пота воротнички, которые он так хорошо, как у больших, устроил дома.
Петя чувствовал, что он имеет непрезентабельный вид, и боялся, что ежели таким он представится камергерам, то его не допустят до государя. Но оправиться и перейти в другое место не было никакой возможности от тесноты. Один из проезжавших генералов был знакомый Ростовых. Петя хотел просить его помощи, но счел, что это было бы противно мужеству. Когда все экипажи проехали, толпа хлынула и вынесла и Петю на площадь, которая была вся занята народом. Не только по площади, но на откосах, на крышах, везде был народ. Только что Петя очутился на площади, он явственно услыхал наполнявшие весь Кремль звуки колоколов и радостного народного говора.