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

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

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

ОписаниеПравить

Данный алгоритм при кодировании (сжатии) сообщения динамически создаёт словарь фраз: определённым последовательностям символов (фразам) ставятся в соответствие группы битов (коды) фиксированной длины (например, 12-битные, как предлагается в исходной статье Велча). Словарь инициализируется всеми 1-символьными фразами (в случае 8-битных символов — это 256 фраз). По мере кодирования алгоритм просматривает текст символ за символом слева направо. При чтении алгоритмом очередного символа в данной позиции находится строка W максимальной длины, совпадающая с какой-то фразой из словаря. Затем код этой фразы подаётся на выход, а строка WK, где K — это символ, следующий за W во входном сообщении, вносится в словарь в качестве новой фразы и ей присваивается какой-то код (так как W выбрана жадно, WK ещё не содержится в словаре). Символ K используется в качестве начала следующей фразы. Более формально данный алгоритм можно описать следующей последовательностью шагов:

1. Инициализация словаря всеми возможными односимвольными фразами. Инициализация входной фразы W первым символом сообщения.
2. Если КОНЕЦ_СООБЩЕНИЯ, то выдать код для W и завершить алгоритм.
3. Считать очередной символ K из кодируемого сообщения.
4. Если фраза WK уже есть в словаре, то присвоить входной фразе W значение WK и перейти к Шагу 2.
5. Иначе выдать код W, добавить WK в словарь, присвоить входной фразе W значение K и перейти к Шагу 2.

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

РеализацияПравить

Примечательной особенностью алгоритма LZW является простота реализации, благодаря которой он до сих пор очень популярен, несмотря на зачастую худшую степень сжатия по сравнению с такими аналогами, как LZ77. Обычно LZW реализуется с помощью префиксного дерева, содержащего фразы из словаря: для нахождения W нужно просто прочитать как можно более длинную строку из корня дерева, затем для добавления новой фразы WK нужно присоединить к найденному узлу нового сына по символу K, а кодом фразы W может выступать индекс узла в массиве, содержащем все узлы.

Кодирование фразПравить

Использование для фраз кодов фиксированной длины (12 битов в описании Велча) может негативно сказаться на эффективности сжатия, так как, во-первых, для начальных кодируемых символов этот подход скорее будет раздувать данные, а не сжимать (если символ занимает 8 битов), и во-вторых, общий размер словаря (2¹²=4096) получается не так велик. Первая проблема решается кодированием выходной последовательности алгоритмом Хаффмана (возможно, адаптивным) или арифметическим кодированием. Для решения второй используют другие подходы.

Первый простой вариант — применить какой-нибудь оптимальный универсальный код типа кода Левенштейна или кода Элиаса. В таком случае теоретически словарь может расти неограниченно.

Другой более распространённый вариант — изменять максимальный возможный размер словаря с ростом числа фраз. Изначально, например, максимальный размер словаря полагается 2⁹ (2⁸ кодов при этом уже заняты фразами для кодирования 8-битовых одиночных символов) и на код фразы отводится 9 битов. Когда число фраз становится 2⁹, максимальный размер становится 2¹⁰ и на коды отводится 10 битов. И так далее. Таким образом, теоретически словарь может быть сколь угодно большим. Этот метод продемонстрирован в примере ниже (обычно, тем не менее, максимальный размер словаря ограничивается; например в LZC — популярной модификации LZW, рассматриваемой ниже — длины кодов растут от 9 до 16 битов.).

В большинстве реализаций последнего метода число битов, выделяемых на код фразы, увеличивается до добавления новой фразы WK, переполняющей словарь, но после записи на выход кода W. Например, пусть в данный момент в процессе работы алгоритма длина кода — p битов, и алгоритм собирается выдать код фразы W и добавить новую фразу WK в словарь; если код WK равен 2^p (то есть WK переполняет словарь), то сначала выдаётся p-битовый код W и только после этого p увеличивается на один, чтобы последующие коды занимали p+1 битов. Среди ранних реализаций LZW существуют такие, которые увеличивают p до выдачи кода W, то есть код W, выдаваемый перед добавлением WK в словарь, уже занимает p+1 битов (что не является необходимым, так как код W меньше 2^p). Такое поведение называется «ранним изменением» (early change). Эта путаница в реализациях побудила Adobe поддерживать оба варианта LZW в PDF (используются ли «ранние изменения», указывается с помощью специального флага в заголовке сжимаемых данных).

Переполнение словаряПравить

Так как коды в алгоритме LZW имеют фиксированную длину, размер словаря ограничен (при использовании кодов нефиксированной длины размер словаря ограничен объёмом доступной памяти). Возникает вопрос: что делать в случае переполнения словаря? Используют несколько стратегий.

1. Самый очевидный вариант — просто использовать построенный словарь без дальнейших модификаций. Ясно, что часто это плохая стратегия.
2. Авторы некогда популярной утилиты compress^[en] просто используют построенный словарь, пока степень сжатия остаётся приемлемой, а затем очищают его в случае ухудшения качества сжатия. Такая модификация LZW называется LZC (Lempel-Ziv-Compress, см. ниже).
3. П. Тисчер предложил перед вставкой в переполненный словарь новой фразы на очередном шаге алгоритма удалять из словаря фразу, которая дольше всего не использовалась (LRU, Least Recently Used). Такая модификация иногда называется LZT (Lempel-Ziv-Tischer, см. ниже).

ПримерПравить

Данный пример показывает алгоритм 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, и анализ этих двух методов сжатия аналогичен. При рассмотрении неограниченного словаря естественно предполагать, что выходные фразы кодируются кодами переменной длины, например, каким-нибудь универсальным кодом или фиксированным кодом, размер которого растёт вместе с максимальным размером словаря (см. раздел о реализации).

Асимптотическая оптимальностьПравить

Для теоретической оценки эффективности данный метод сжатия сравнивают с некоторой эталонной метрикой. К сожалению, идеальная эталонная метрика сжатия данных — Колмогоровская сложность — невычислима даже приблизительно, и поэтому любой алгоритм сжатия заведомо проигрывает в сравнении с ней. Лемпель и Зив предложили ослабленную версию Колмогоровской сложности — сжатие конечными автоматами. По техническим причинам данная метрика определяется для бесконечных строк. Зафиксируем конечный алфавит $\mathrm{\Sigma <!--\; \Sigma \; -->}$$\Sigma$ . Пусть дана бесконечная строка $x=x_1{x}_2\cdots <!--\; \cdots \; -->$$x=x_{1}x_{2}\cdots$  над $\mathrm{\Sigma <!--\; \Sigma \; -->}$$\Sigma$ . Обозначим через $\mathrm{L}\mathrm{Z}\mathrm{W}(x_1{x}_2\cdots <!--\; \cdots \; -->x_n)$$\mathrm {LZW} (x_{1}x_{2}\cdots x_{n})$  число битов в кодировке LZW с неограниченным словарём для строки $x_1{x}_2\cdots <!--\; \cdots \; -->x_n$$x_{1}x_{2}\cdots x_{n}$ . Отсюда имеем

$\mathrm{L}\mathrm{Z}\mathrm{W}(x_1{x}_2\cdots <!--\; \cdots \; -->x_n)\le <!--\; \le \; -->z{\log }_2<!--\; \; -->z+O(z{\log }_2<!--\; \; -->|\mathrm{\Sigma <!--\; \Sigma \; -->}|),$$\mathrm {LZW} (x_{1}x_{2}\cdots x_{n})\leq z\log _{2}z+O(z\log _{2}|\Sigma |),$ 

где $z$$z$  — это число фраз в LZW кодировке для $x_1{x}_2\cdots <!--\; \cdots \; -->x_n$$x_{1}x_{2}\cdots x_{n}$ . Зив показал, что

$\underset{n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim sup}\frac{\mathrm{L}\mathrm{Z}\mathrm{W}(x_1{x}_2\cdots <!--\; \cdots \; -->x_n)}{n{\log }_2<!--\; \; -->|\mathrm{\Sigma <!--\; \Sigma \; -->}|}\le <!--\; \le \; -->\mathrm{F}\mathrm{S}(x),$$\limsup \limits _{n\to \infty }{\frac {\mathrm {LZW} (x_{1}x_{2}\cdots x_{n})}{n\log _{2}|\Sigma |}}\leq \mathrm {FS} (x),$ 

где $\mathrm{F}\mathrm{S}(x)$$\mathrm {FS} (x)$  — это метрика сжатия конечными автоматами, определённая далее. Таким образом, коэффициент сжатия LZW (отношение $\mathrm{L}\mathrm{Z}\mathrm{W}(x_1{x}_2\cdots <!--\; \cdots \; -->x_n)$$\mathrm {LZW} (x_{1}x_{2}\cdots x_{n})$  к $n{\log }_2<!--\; \; -->|\mathrm{\Sigma <!--\; \Sigma \; -->}|$$n\log _{2}|\Sigma |$  — числу битов, занимаемых несжатой строкой) асимптотически ограничен $\mathrm{F}\mathrm{S}$$\mathrm {FS}$  и в этом смысле LZW оптимален. Более того, если размер словаря ограничен и при переполнении используется стратегия удаления наименее используемых фраз, LZW также асимптотически оптимален в следующем смысле:

$\underset{D\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim}\underset{n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim sup}\frac{{\mathrm{L}\mathrm{Z}\mathrm{W}}_D(x_1{x}_2\cdots <!--\; \cdots \; -->x_n)}{n{\log }_2<!--\; \; -->|\mathrm{\Sigma <!--\; \Sigma \; -->}|}\le <!--\; \le \; -->\mathrm{F}\mathrm{S}(x),$$\lim _{D\to \infty }\limsup \limits _{n\to \infty }{\frac {\mathrm {LZW} _{D}(x_{1}x_{2}\cdots x_{n})}{n\log _{2}|\Sigma |}}\leq \mathrm {FS} (x),$ 

где ${\mathrm{L}\mathrm{Z}\mathrm{W}}_D(x_1{x}_2\cdots <!--\; \cdots \; -->x_n)$$\mathrm {LZW} _{D}(x_{1}x_{2}\cdots x_{n})$  обозначает число битов в кодировке LZW со словарём, в котором содержатся не более $D$$D$  фраз, каждая фраза имеет длину не больше ${\log }_2^2<!--\; \; -->D$$\log _{2}^{2}D$  и при переполнении словаря выбрасывается реже всего использовавшаяся фраза (этот вариант похож на LZT; см. модификации). Отметим, что аналогичными свойствами обладают алгоритмы LZ78 и LZ77 (включая аналогичные варианты, соответственно, со словарём и скользящим окном ограниченного размера). Определим теперь $\mathrm{F}\mathrm{S}$$\mathrm {FS}$ .

Метрика $\mathrm{F}\mathrm{S}(x)$$\mathrm {FS} (x)$  во многом аналогична Колмогоровской сложности, но вместо полноценных машин Тьюринга в её определении используются машины Тьюринга с конечной памятью, то есть конечные автоматы. Для данного числа $s$$s$  обозначим через ${\mathcal{A}}_s$${\mathcal {A}}_{s}$  множество всех детерминированных автоматов Мили $A,$$A,$  которые имеют $s$$s$  состояний и перекодируют строки над алфавитом $\mathrm{\Sigma <!--\; \Sigma \; -->}$$\Sigma$  в бинарные последовательности, так что по выходу автомата можно восстановить исходную строку; более точно, на рёбрах автомата $A$$A$  записаны бинарные строки (возможно пустые), так что по любой конечной строке $y$$y$  над алфавитом $\mathrm{\Sigma <!--\; \Sigma \; -->}$$\Sigma$  автомат $A$$A$  приходит в некоторое состояние $v$$v$  и в процессе выдают бинарную последовательность $A(y)$$A(y)$ , и по последовательности $A(y)$$A(y)$  и состоянию $v$$v$  можно однозначно восстановить $y$$y$  (чтобы сжимающий автомат мог иметь пустые строки на рёбрах, строка $y$$y$  восстанавливается не только по последовательности $A(y)$$A(y)$ , но и по конечному состоянию $v$$v$ ). Для данной бесконечной строки $x=x_1{x}_2\cdots <!--\; \cdots \; -->$$x=x_{1}x_{2}\cdots$  определим:

$\mathrm{F}\mathrm{S}(x)=\underset{s\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim}\underset{n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim sup}\underset{A\in <!--\; \in \; -->{\mathcal{A}}_s}{min}\frac{|A(x_1{x}_2\cdots <!--\; \cdots \; -->x_n)|}{n{\log }_2<!--\; \; -->|\mathrm{\Sigma <!--\; \Sigma \; -->}|},$$\mathrm {FS} (x)=\lim _{s\to \infty }\limsup \limits _{n\to \infty }\min \limits _{A\in {\mathcal {A}}_{s}}{\frac {|A(x_{1}x_{2}\cdots x_{n})|}{n\log _{2}|\Sigma |}},$ 

где $|A(y)|$$|A(y)|$  обозначает число битов в $A(y)$$A(y)$ . Таким образом, $\mathrm{F}\mathrm{S}(x)$$\mathrm {FS} (x)$  представляет собой оценку на наименьший возможный коэффициент сжатия, которого можно достигнуть при сжатии строки $x$$x$  конечными автоматами. Заметим, что из-за неограниченности словаря алгоритм LZW не может быть смоделирован с помощью автомата Мили, в отличие от алгоритма LZW с ограниченным словарём с не более чем $D$$D$  фразами длины не более ${\log }_2^2<!--\; \; -->D$$\log _{2}^{2}D$  (размер такого автомата Мили, естественно, зависит от $D$$D$ ).

Неоптимальность числа фразПравить

Метрика сжатия конечными автоматами, хоть и является естественной, не так эффективна, как может показаться на первый взгляд. Так, асимптотически оптимальным по отношению к $\mathrm{F}\mathrm{S}$$\mathrm {FS}$  является любой алгоритм сжатия, который разбивает данную строку $x=x_1{x}_2\cdots <!--\; \cdots \; -->x_n$$x=x_{1}x_{2}\cdots x_{n}$  на различные фразы $f_1{f}_2\cdots <!--\; \cdots \; -->f_k$$f_{1}f_{2}\cdots f_{k}$  (то есть $f_i\ne <!--\; \ne \; -->f_j$$f_{i}\neq f_{j}$  при $i<j<k$ ) и затем кодирует $x$$x$ , используя $k{\log }_2<!--\; \; -->k+O(k{\log }_2<!--\; \; -->|\mathrm{\Sigma <!--\; \Sigma \; -->}|)$$k\log _{2}k+O(k\log _{2}|\Sigma |)$  битов. Ясно, что алгоритм, удовлетворяющий таким слабым критериям, вовсе не обязан быть эффективным на практике. Вдобавок, метрика сжатия конечными автоматами не отражает способности многих методов сжатия заменять длинные повторяющиеся фрагменты в данных ссылками на место, где такой фрагмент встретился впервые (у конечного автомата просто не достанет памяти для сравнения длинных фрагментов). Именно этот механизм зачастую является причиной эффективности сжатия больших объёмов данных на практике, и как показано далее, LZW (и LZ78) достаточно плохо справляются с данной задачей в худшем случае по сравнению, например, с LZ77.

Алгоритм LZW с неограниченным размером словаря разлагает данную конечную строку $x=x_1{x}_2\cdots <!--\; \cdots \; -->x_n$$x=x_{1}x_{2}\cdots x_{n}$  на фразы $p_1{p}_2\cdots <!--\; \cdots \; -->p_z$$p_{1}p_{2}\cdots p_{z}$ , так что каждая фраза $p_k$$p_{k}$  либо является символом, либо равна $p_{h}a$$p_{h}a$ , где $h$$h$  — какое-то число меньшее $k$$k$ , а $a$$a$  — это первый символ фразы $p_{h+1}$$p_{h+1}$ . Существуют и другие разложения вида $p_1{p}_2\cdots <!--\; \cdots \; -->p_z$$p_{1}p_{2}\cdots p_{z}$  для строки $x$$x$  и естественно возникает вопрос: насколько хорошо разложение, построенное жадным алгоритмом LZW?

Пусть $z_o$$z_{o}$  обозначает минимальное число, такое что строка $x$$x$  представима в виде разложения $p_1^{\prime }{p}_2^{\prime }\cdots <!--\; \cdots \; -->p_{z_o}^{\prime }$$p'_{1}p'_{2}\cdots p'_{z_{o}}$ , в котором каждая строка $p_k^{\prime }$$p'_{k}$  либо является символом, либо равна $p_h^{\prime }a$$p'_{h}a$ , где $h$$h$  — какое-то число меньшее $k$$k$ , а $a$$a$  — первый символ строки $p_{h+1}^{\prime }$$p'_{h+1}$ . Сержио Де Агостино и Рикардо Сильвестри доказали, что в худшем случае $z$$z$  может быть больше $z_o$$z_{o}$  в $\mathrm{\Omega <!--\; \Omega \; -->}(n^{1/4})$$\Omega (n^{1/4})$  раза, даже если алфавит содержит всего лишь два символа (они также показали, что $z\le <!--\; \le \; -->z_o\cdot <!--\; \cdot \; -->O(n^{1/4}),$$z\leq z_{o}\cdot O(n^{1/4}),$  то есть данная оценка оптимальна). Иными словами, жадная стратегия даёт в данном случае результаты очень далёкие от оптимальных. Частично оправдывает подход LZW то, что построение оптимального разложения с $z_o$$z_{o}$  фразами является NP-полной задачей, как показали Де Агостино и Сторер.

Другой естественный вопрос: насколько хорош LZW по сравнению с LZ77? Известно, что LZ77 жадным образом разлагает строку $x$$x$  на фразы $f_1{f}_2\cdots <!--\; \cdots \; -->f_w$$f_{1}f_{2}\cdots f_{w}$ , так что каждая фраза $f_h$$f_{h}$  либо является символом, либо является подстрокой строки $f_1{f}_2\cdots <!--\; \cdots \; -->f_{h-<!--\; -\; -->1}$$f_{1}f_{2}\cdots f_{h-1}$ . Хуке, Лори, Ре и Чарикар и др. показали, что в худшем случае $z$$z$  может быть в $\mathrm{\Omega <!--\; \Omega \; -->}((n/\log <!--\; \; -->n{)}^{1/2})$$\Omega ((n/\log n)^{1/2})$  раз больше, чем $w$$w$ . С другой стороны, известно, что $z$$z$  всегда не меньше $w$$w$ , и даже более того, $z_o$$z_{o}$  всегда не меньше $w$$w$ . Иными словами, LZW и даже «оптимальная» версия LZW, содержащая $z_o$$z_{o}$  фраз, не может быть лучше LZ77 (по крайней мере существенно — обратите внимание, что здесь обсуждается число фраз, а не способ их кодирования), а в некоторых патологических случаях может быть катастрофически хуже.

ПрименениеПравить

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

Алгоритм (а точнее его модификация, LZC, см. ниже) был реализован в программе compress^[en], которая стала более или менее стандартной утилитой Unix-систем приблизительно в 1986 году. Несколько других популярных утилит-архиваторов также используют этот метод или близкие к нему.

В 1987 году алгоритм стал частью стандарта на формат изображений GIF. Он также может (опционально) использоваться в формате TIFF. Помимо этого, алгоритм применяется в протоколе модемной связи v.42bis и стандарте PDF (хотя по умолчанию большая часть текстовых и визуальных данных в PDF сжимается с помощью алгоритма Deflate).

ПатентыПравить

На алгоритм LZW и его вариации был выдан ряд патентов, как в США, так и в других странах. На LZ78 был выдан американский патент U.S. Patent 4 464 650, принадлежащий Sperry Corporation, позднее ставшей частью Unisys Corporation. На LZW в США были выданы два патента: U.S. Patent 4 814 746, принадлежащий IBM, и патент Велча U.S. Patent 4 558 302 (выдан 20 июня 1983 года), принадлежащий Sperry Corporation, позднее перешедший к Unisys Corporation. К настоящему времени сроки всех патентов истекли.

Unisys, GIF и PNGПравить

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

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

МодификацииПравить

• LZC (1985, Thomas S. W., McKie J., Davies S., Turkowski K., Woods J. A. и Orost J. W.) — одна из наиболее известных практических реализаций LZW, представленная в утилите compress^[en] (Lempel-Ziv-Compress). LZC использует от 9 до 16 битов для кодов фраз (число битов растёт с ростом размера словаря, см. раздел о реализации); когда словарь переполняется, LZC просто продолжает его использование без дальнейшей модификации, но при этом алгоритм следит за степенью сжатия данных и, когда сжатие с текущим словарём становится неприемлемо плохим, LZC очищает словарь и продолжает работу. LZC сжимает хуже, чем LZW, но зато скорость сжатия выше.
• LZT (1985, Tischer P.) — другой известный вариант LZW. При переполнении словаря LZT продолжает работу, но каждый раз перед вставкой новой фразы в словарь, он удаляет фразу, которая соответствует дольше всего не используемому листу в префиксном дереве, содержащем все фразы. В реализации LZT все листья помещаются в связный список, и каждый раз после использования в ходе сжатия листья перемещаются в голову списка; таким образом, листья, которые не использовались дольше всего, находятся в хвосте списка (дальнейшие детали очевидны).
• LZMW (1985, Виктор Миллер^[en] и Марк Вегман^[en]) — находит во входном потоке самую длинную строку, которая уже имеется в словаре (обозначим её W), выдаёт на выход код W, а затем добавляет в словарь строку VW, где V — это строка из словаря, код которой был выдан на предыдущем шаге (изначально V является пустой строкой). Таким образом, строки в словаре растут быстрее, чем в исходном варианте LZW, и на практике часто удаётся получить лучшее качество сжатия. Миллер и Вегман также предложили в случае недостатка памяти удалять из словаря фразы, которые редко используются, так же как это делается в LZT.
• LZAP (1988, Джеймс Сторер) — модификация LZMW, отличающаяся тем, что на каждом шаге в словарь добавляется не только строка VW, но и строки VW₁, VW₂, …, VW_|W|-1, где W_i — это префикс W длины i. («AP» в «LZAP» означает «all prefixes», то есть «все префиксы».) Например, если V = wiki и W = pedia — то есть на предыдущем шаге алгоритм нашёл в словаре строку wiki, а на данном нашёл pedia — то алгоритм добавит в словарь строку wikipedia, как сделал бы LZMW, но также добавит строки wikip, wikipe, wikiped, wikipedi. Алгоритм LZAP проще для реализации, чем LZMW, но в то же время он сохраняет большинство преимуществ LZMW за исключением того, что коды словарных строк занимают больше места, потому что словарь более раздут.

См. такжеПравить

• LZ
• LZ77
• LZMA

ЛитератураПравить

• Arnold R., Bell T.^[en]. A corpus for the evaluation of lossless compression algorithms // IEEE Data Compression Conference. — 1997. — С. 201–210. — doi:10.1109/DCC.1997.582019.
• Bell T.^[en], Witten I. H.^[en], Cleary J. G.^[en]. Modeling for text compression // ACM Computing Surveys^[en]. — 1989. — Т. 21, № 4. — С. 557–591. — doi:10.1145/76894.76896.
• Charikar M., Lehman E., Lehman A., Liu D., Panigrahy R., Prabhakaran M., Sahai A., shelat a. The smallest grammar problem // IEEE Transactions on Information Theory^[en]. — 2005. — Т. 51, № 7. — С. 2554—2576. — doi:10.1109/TIT.2005.850116.
• De Agostino S., Silvestri R. A worst-case analysis of the LZ2 compression algorithm // Information and Computation^[en]. — 1997. — Т. 139, № 2. — С. 258–268. — doi:10.1006/inco.1997.2668.
• De Agostino S., Storer J. A. On-line versus off-line computation in dynamic text compression // Information Processing Letters^[en]. — 1996. — Т. 59, № 3. — С. 169–174. — doi:10.1016/0020-0190(96)00068-3.
• Hucke D., Lohrey M., Reh C. P. The smallest grammar problem revisited // String Processing and Information Retrieval (SPIRE). — 2016. — Т. 9954. — С. 35–49. — doi:10.1007/978-3-319-46049-9_4.
• Lempel A., Ziv J. Compression of individual sequences via variable-rate coding // IEEE Transactions on Information Theory^[en]. — 1978. — Т. 24, № 5. — С. 530–536. — doi:10.1109/TIT.1978.1055934.
• Miller V. S^[en], Wegman M. N.^[en]. Variations on a theme by Ziv and Lempel // Combinatorial algorithms on words. — 1985. — Т. 12. — С. 131–140. — doi:10.1007/978-3-642-82456-2_9.
• Sheinwald D. On the Ziv-Lempel proof and related topics // Proceedings of the IEEE^[en]. — 1994. — Т. 82, № 6. — С. 866–871. — doi:10.1109/5.286190.
• Storer J. A. Data Compression: Methods and Theory. — New York, USA: Computer Science Press, 1988. — 413 с. — ISBN 0-7167-8156-5.
• Welch T. A. A technique for high-performance data compression // Computer. — 1984. — Т. 6, № 17. — С. 8–19. — doi:10.1109/MC.1984.1659158.
• Ziv J. A constrained-dictionary version of LZ78 asymptotically achieves the finite-state compressibility with a distortion measure // IEEE Information Theory Workshop. — 2015. — С. 1–4. — doi:10.1109/ITW.2015.7133077.
• Adobe Systems Incorporated. Document management — Portable document format — Part 1: PDF 1.7 (англ.). PDF 1.7 specification. Adobe (1 июля 2008). Дата обращения: 26 января 2018.