Просмотр кода страницы Алгоритм Лемпеля — Зива — Велча

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

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

== Описание ==
Данный алгоритм при кодировании (сжатии) сообщения динамически создаёт словарь фраз: определённым последовательностям символов (фразам) ставятся в соответствие группы битов (коды) фиксированной длины (например, 12-битные, как предлагается в исходной статье Велча{{sfn|Welch|1984}}). Словарь инициализируется всеми 1-символьными фразами (в случае 8-битных символов — это 256 фраз). По мере кодирования алгоритм просматривает текст символ за символом слева направо. При чтении алгоритмом очередного символа в данной позиции находится строка <math>W</math> максимальной длины, совпадающая с какой-то фразой из словаря. Затем код этой фразы подаётся на выход, а строка <math>WK</math>, где <math>K</math> — это символ, следующий за <math>W</math> во входном сообщении, вносится в словарь в качестве новой фразы и ей присваивается какой-то код (так как <math>W</math> выбрана [[Жадный алгоритм|жадно]], <math>WK</math> ещё не содержится в словаре). Символ <math>K</math> используется в качестве начала следующей фразы. Более формально данный алгоритм можно описать следующей последовательностью шагов:

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

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

== Реализация ==
Примечательной особенностью алгоритма LZW является простота реализации, благодаря которой он до сих пор очень популярен, несмотря на зачастую худшую степень сжатия по сравнению с такими аналогами, как [[LZ77]]{{sfn|Arnold, Bell|1997}}. Обычно LZW реализуется с помощью [[Префиксное дерево|префиксного дерева]], содержащего фразы из словаря: для нахождения <math>W</math> нужно просто прочитать как можно более длинную строку из корня дерева, затем для добавления новой фразы <math>WK</math> нужно присоединить к найденному узлу нового сына по символу <math>K</math>, а кодом фразы W может выступать индекс узла в массиве, содержащем все узлы.

=== Кодирование фраз ===
Использование для фраз кодов фиксированной длины (12 битов в описании Велча{{sfn|Welch|1984}}) может негативно сказаться на эффективности сжатия, так как, во-первых, для начальных кодируемых символов этот подход скорее будет раздувать данные, а не сжимать (если символ занимает 8 битов), и во-вторых, общий размер словаря (<math>2^{12}=4096</math>) получается не так велик. Первая проблема решается кодированием выходной последовательности [[Код Хаффмана|алгоритмом Хаффмана]] (возможно, [[Адаптивный алгоритм Хаффмана|адаптивным]]) или [[Арифметическое кодирование|арифметическим кодированием]]. Для решения второй используют другие подходы.

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

Другой более распространённый вариант — изменять максимальный возможный размер словаря с ростом числа фраз.{{sfn|Bell, Witten, Cleary|1989|loc=раздел 3.4.6}} Изначально, например, максимальный размер словаря полагается 2<sup>9</sup> (2<sup>8</sup> кодов при этом уже заняты фразами для кодирования 8-битовых одиночных символов) и на код фразы отводится 9 битов. Когда число фраз становится 2<sup>9</sup>, максимальный размер становится 2<sup>10</sup> и на коды отводится 10 битов. И так далее. Таким образом, теоретически словарь может быть сколь угодно большим. Этот метод продемонстрирован в [[#Пример|примере]] ниже (обычно, тем не менее, максимальный размер словаря ограничивается; например в LZC — популярной модификации LZW, рассматриваемой ниже — длины кодов растут от 9 до 16 битов).

В большинстве реализаций последнего метода число битов, выделяемых на код фразы, увеличивается до добавления новой фразы <math>WK</math>, переполняющей словарь, но после записи на выход кода <math>W</math>. Например, пусть в данный момент в процессе работы алгоритма длина кода — <math>p</math> битов, и алгоритм собирается выдать код фразы <math>W</math> и добавить новую фразу <math>WK</math> в словарь; если код <math>WK</math> равен <math>2^p</math> (то есть <math>WK</math> переполняет словарь), то сначала выдаётся <math>p</math>-битовый код W и только после этого  <math>p</math>увеличивается на один, чтобы последующие коды занимали <math>p+1</math> битов. Среди ранних реализаций LZW существуют такие, которые увеличивают <math>p</math> до выдачи кода <math>W</math>, то есть код <math>W</math>, выдаваемый перед добавлением <math>WK</math> в словарь, уже занимает <math>p+1</math> битов (что не является необходимым, так как код <math>W</math> меньше <math>2^p</math>). Такое поведение называется «ранним изменением» (early change). Эта путаница в реализациях побудила [[Adobe]] поддерживать оба варианта LZW в PDF (используются ли «ранние изменения», указывается с помощью специального флага в заголовке сжимаемых данных).{{sfn|PDF 1.7 specification|loc=раздел 7.4.4.3}}

=== Переполнение словаря ===
Так как коды в алгоритме LZW имеют фиксированную длину, размер словаря ограничен (при использовании кодов нефиксированной длины размер словаря ограничен объёмом доступной памяти). Возникает вопрос: что делать в случае переполнения словаря? Используют несколько стратегий:
# Самый очевидный вариант — просто использовать построенный словарь без дальнейших модификаций.{{sfn|Welch|1984}} Ясно, что часто это плохая стратегия.
# Авторы некогда популярной утилиты {{iw|compress}} просто используют построенный словарь, пока степень сжатия остаётся приемлемой, а затем очищают его в случае ухудшения качества сжатия. Такая модификация LZW называется LZC (Lempel-Ziv-Compress, см. ниже).{{sfn|Bell, Witten, Cleary|1989|loc=раздел 3.4.8}}
# П. Тисчер предложил перед вставкой в переполненный словарь новой фразы на очередном шаге алгоритма удалять из словаря фразу, которая дольше всего не использовалась (LRU, Least Recently Used). Такая модификация иногда называется LZT (Lempel-Ziv-Tischer, см. ниже).{{sfn|Bell, Witten, Cleary|1989|loc=раздел 3.4.9}}

== Пример ==
Данный пример показывает алгоритм LZW в действии, показывая состояние выходных данных и словаря на каждой стадии, как при кодировании, так и при раскодировании сообщения. С тем чтобы сделать изложение проще, мы ограничимся простым алфавитом — только заглавные буквы, без знаков препинания и пробелов. Сообщение, которое нужно сжать, выглядит следующим образом:
 TOBEORNOTTOBEORTOBEORNOT#
Маркер <code>''#''</code> используется для обозначения конца сообщения. Тем самым, в нашем алфавите 27 символов (26 заглавных букв от A до Z и символ #). Компьютер представляет это в виде групп бит, для представления каждого символа алфавита нам достаточно группы из 5 бит на символ. По мере роста словаря, размер групп должен расти, с тем чтобы учесть новые элементы. 5-битные группы дают <math>2^5 = 32</math> возможных комбинации бит, поэтому, когда в словаре появится 33-е слово, алгоритм должен перейти к 6-битным группам. Заметим, что, поскольку используется группа из всех нулей <code>00000</code>, то 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 =  01110     32: RN
 O      15 =  01111     33: NO
 T      20 =  10100     34: OT
 TO     27 =  11011     35: TT
 BE     29 =  11101     36: TOB
 OR     31 =  11111     37: BEO
 TOB    36 = 100100     38: ORT
 EO     30 =  11110     39: TOBE
 RN     32 = 100000     40: EOR
 OT     34 = 100010     41: RNO
 #       0 =  00000     42: OT#
 
 Общая длина = 13*5 + 3*6 = 83 бит.

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

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

 Данные:     На выходе:     Новая запись:
                         Полная:      Частичная:
  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-битные группы
  01110 = 14     N       32: RN       33: N?
  01111 = 15     O       33: NO       34: O?
  10100 = 20     T       34: OT       35: T?
  11011 = 27     TO      35: TT       36: TO? <---- для 37, добавляем только первый элемент
  11101 = 29     BE      36: TOB      37: BE?      следующего слова словаря
  11111 = 31     OR      37: BEO      38: OR?
 100100 = 36     TOB     38: ORT      39: TOB?
  11110 = 30     EO      39: TOBE     40: EO?
 100000 = 32     RN      40: EOR      41: RN?
 100010 = 34     OT      41: RNO      42: OT?
  00000 = 0      #

Единственная небольшая трудность может возникнуть, если новое слово словаря пересылается немедленно. В приведённом выше примере декодирования, когда декодер встречает первый символ, <code>T</code>, он знает, что слово 27 начинается с T, но чем оно заканчивается? Проиллюстрируем проблему следующим примером. Мы декодируем сообщение <code>ABABA</code>:
 Данные:     На выходе:     Новая запись:
                         Полная:      Частичная:
 .
 .
 .
 011101 = 29     AB      46: (word)   47: AB?
 101111 = 47     AB?  <--- что нам с этим делать?

На первый взгляд, для декодера это неразрешимая ситуация. Мы знаем наперёд, что словом 47 должно быть <code>ABA</code>, но как декодер узнает об этом? Заметим, что слово 47 состоит из слова 29 плюс символ, идущий следующим. Таким образом, слово 47 заканчивается на «символ, идущий следующим». Но, поскольку это слово посылается немедленно, то оно должно начинаться с «символа, идущего следующим», и поэтому оно заканчивается тем же символом, что и начинается, в данном случае — <code>A</code>. Этот трюк позволяет декодеру определить, что слово 47 — это <code>ABA</code>.

В общем случае, такая ситуация появляется, когда кодируется последовательность вида <math>cScSc</math>, где <math>c</math> — это один символ, а <math>S</math> — строка, причём слово <math>cS</math> уже есть в словаре.

== Теоретическая оценка эффективности ==
Теоретические свойства LZW с неограниченным словарём в целом такие же, как и у LZ78, и анализ этих двух методов сжатия аналогичен. При рассмотрении неограниченного словаря естественно предполагать, что выходные фразы кодируются кодами переменной длины, например, каким-нибудь [[Универсальный код|универсальным кодом]] или фиксированным кодом, размер которого растёт вместе с максимальным размером словаря (см. раздел о [[#Реализация|реализации]]).

=== Асимптотическая оптимальность ===
Для теоретической оценки эффективности данный метод сжатия сравнивают с некоторой эталонной метрикой. К сожалению, идеальная эталонная метрика сжатия данных — [[Колмогоровская сложность]] — [[Вычислимая функция|невычислима]] даже приблизительно, и поэтому любой алгоритм сжатия заведомо проигрывает в сравнении с ней. Лемпель и Зив предложили ослабленную версию Колмогоровской сложности — ''сжатие конечными автоматами''{{sfn|Lempel, Ziv|1978}}. По техническим причинам данная метрика определяется для бесконечных строк. Зафиксируем конечный алфавит <math>\Sigma</math>. Пусть дана бесконечная строка <math>x = x_1 x_2 \cdots</math> над <math>\Sigma</math>. Обозначим через <math>\mathrm{LZW}(x_1 x_2 \cdots x_n)</math> число битов в кодировке LZW с неограниченным словарём для строки <math>x_1 x_2 \cdots x_n</math>. Отсюда имеем:
: <math>\mathrm{LZW}(x_1 x_2 \cdots x_n) \le z \log_2 z + O(z \log_2 |\Sigma|),</math>
где <math>z</math> — это число фраз в LZW кодировке для <math>x_1 x_2 \cdots x_n</math>. Зив показал{{sfn|Ziv|2015}}, что
: <math>\limsup\limits_{n \to \infty} \frac{\mathrm{LZW}(x_1 x_2 \cdots x_n)}{n\log_2 |\Sigma|} \le \mathrm{FS}(x),</math>
где <math>\mathrm{FS}(x)</math> — это метрика сжатия конечными автоматами, определённая далее{{sfn|Lempel, Ziv|1978}}. Таким образом, [[Сжатие данных#Коэффициент сжатия|коэффициент сжатия]] LZW (отношение <math>\mathrm{LZW}(x_1 x_2 \cdots x_n)</math> к <math>n \log_2 |\Sigma|</math> — числу битов, занимаемых несжатой строкой) асимптотически ограничен <math>\mathrm{FS}</math> и в этом смысле LZW оптимален. Более того, если размер словаря ограничен и при переполнении используется стратегия удаления наименее используемых фраз, LZW также асимптотически оптимален в следующем смысле:{{sfn|Ziv|2015}}
: <math>\lim_{D \to \infty} \limsup\limits_{n \to \infty} \frac{\mathrm{LZW}_D(x_1 x_2 \cdots x_n)}{n\log_2 |\Sigma|} \le \mathrm{FS}(x),</math>
где <math>\mathrm{LZW}_D(x_1 x_2 \cdots x_n)</math> обозначает число битов в кодировке LZW со словарём, в котором содержатся не более <math>D</math> фраз, каждая фраза имеет длину не больше <math>\log_2^2 D</math> и при переполнении словаря выбрасывается реже всего использовавшаяся фраза (этот вариант похож на LZT; см. [[#Модификации|модификации]]). Отметим, что аналогичными свойствами обладают алгоритмы LZ78 и LZ77 (включая аналогичные варианты, соответственно, со словарём и скользящим окном ограниченного размера){{sfn|Ziv|2015}}. Определим теперь <math>\mathrm{FS}</math>.

Метрика <math>\mathrm{FS}(x)</math> во многом аналогична Колмогоровской сложности, но вместо полноценных [[Машина Тьюринга|машин Тьюринга]] в её определении используются машины Тьюринга с конечной памятью, то есть конечные автоматы. Для данного числа <math>s</math> обозначим через <math>\mathcal{A}_s</math> множество всех детерминированных [[Автомат Мили|автоматов Мили]] <math>A,</math> которые имеют <math>s</math> состояний и перекодируют строки над алфавитом <math>\Sigma</math> в бинарные последовательности, так что по выходу автомата можно восстановить исходную строку; более точно, на рёбрах автомата <math>A</math> записаны бинарные строки (возможно пустые), так что по любой конечной строке <math>y</math> над алфавитом <math>\Sigma</math> автомат <math>A</math> приходит в некоторое состояние <math>v</math> и в процессе выдают бинарную последовательность <math>A(y)</math>, и по последовательности <math>A(y)</math> и состоянию <math>v</math> можно однозначно восстановить <math>y</math> (чтобы сжимающий автомат мог иметь пустые строки на рёбрах, строка <math>y</math> восстанавливается не только по последовательности <math>A(y)</math>, но и по конечному состоянию <math>v</math>{{sfn|Sheinwald|1994}}). Для данной бесконечной строки <math>x = x_1 x_2 \cdots</math> определим:{{sfn|Ziv|2015}}
: <math>\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|},</math>
где <math>|A(y)|</math> обозначает число битов в <math>A(y)</math>. Таким образом, <math>\mathrm{FS}(x)</math> представляет собой оценку на наименьший возможный коэффициент сжатия, которого можно достигнуть при сжатии строки <math>x</math> конечными автоматами. Заметим, что из-за неограниченности словаря алгоритм LZW не может быть смоделирован с помощью автомата Мили, в отличие от алгоритма LZW с ограниченным словарём с не более чем <math>D</math> фразами длины не более <math>\log_2^2 D</math> (размер такого автомата Мили, естественно, зависит от <math>D</math>).

=== Неоптимальность числа фраз ===
Метрика сжатия конечными автоматами, хоть и является естественной, не так эффективна, как может показаться на первый взгляд. Так, асимптотически оптимальным по отношению к <math>\mathrm{FS}</math> является любой алгоритм сжатия, который разбивает данную строку <math>x = x_1 x_2 \cdots x_n</math> на различные фразы <math>f_1 f_2 \cdots f_k</math> (то есть <math>f_i \ne f_j</math> при <math>i < j < k</math>) и затем кодирует <math>x</math>, используя <math>k \log_2 k + O(k\log_2 |\Sigma|)</math> битов{{sfn|Sheinwald|1994}}. Ясно, что алгоритм, удовлетворяющий таким слабым критериям, вовсе не обязан быть эффективным на практике. Вдобавок, метрика сжатия конечными автоматами не отражает способности многих методов сжатия заменять длинные повторяющиеся фрагменты в данных ссылками на место, где такой фрагмент встретился впервые (у конечного автомата просто не достанет памяти для сравнения длинных фрагментов). Именно этот механизм зачастую является причиной эффективности сжатия больших объёмов данных на практике, и как показано далее, LZW (и LZ78) достаточно плохо справляются с данной задачей в худшем случае по сравнению, например, с LZ77.

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

Пусть <math>z_o</math> обозначает минимальное число, такое что строка <math>x</math> представима в виде разложения <math>p'_1 p'_2 \cdots p'_{z_o}</math>, в котором каждая строка <math>p'_k</math> либо является символом, либо равна <math>p'_h a</math>, где <math>h</math> — какое-то число меньшее <math>k</math>, а <math>a</math> — первый символ строки <math>p'_{h+1}</math>. Сержио Де Агостино и Рикардо Сильвестри{{sfn|De Agostino, Silvestri|1997}} доказали, что в худшем случае <math>z</math> может быть больше <math>z_o</math> в [[«O» большое и «o» малое|<math>\Omega(n^{1/4})</math>]] раза, даже если алфавит содержит всего лишь два символа (они также показали, что <math>z \le z_o \cdot O(n^{1/4}),</math> то есть данная оценка оптимальна). Иными словами, жадная стратегия даёт в данном случае результаты очень далёкие от оптимальных. Частично оправдывает подход LZW то, что построение оптимального разложения с <math>z_o</math> фразами является [[NP-полная задача|NP-полной задачей]], как показали Де Агостино и Сторер{{sfn|De Agostino, Storer|1996}}.

Другой естественный вопрос: насколько хорош LZW по сравнению с [[LZ77]]? Известно, что LZ77 жадным образом разлагает строку <math>x</math> на фразы <math>f_1 f_2 \cdots f_w</math>, так что каждая фраза <math>f_h</math> либо является символом, либо является подстрокой строки <math>f_1 f_2 \cdots f_{h-1}</math>. Хуке, Лори, Ре{{sfn|Hucke, Lohrey, Reh|2016}} и Чарикар и др.{{sfn|Charikar et al.|2005}} показали, что в худшем случае <math>z</math> может быть в <math>\Omega((n / \log n)^{1/2})</math> раз больше, чем <math>w</math>. С другой стороны, известно, что <math>z</math> всегда не меньше <math>w</math>, и даже более того, <math>z_o</math> всегда не меньше <math>w</math>.{{sfn|Charikar et al.|2005}} Иными словами, LZW и даже «оптимальная» версия LZW, содержащая <math>z_o</math> фраз, не может быть лучше LZ77 (по крайней мере существенно — обратите внимание, что здесь обсуждается число фраз, а не способ их кодирования), а в некоторых патологических случаях может быть катастрофически хуже.

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

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

В [[1987 год]]у алгоритм стал частью стандарта на формат изображений [[GIF]]. Он также может (опционально) использоваться в формате [[TIFF]]. Помимо этого, алгоритм применяется в [[Протоколы модемной связи#V.42bis|протоколе модемной связи v.42bis]] и стандарте [[PDF]]{{sfn|PDF 1.7 specification|loc=раздел 7.4.4}} (хотя по умолчанию большая часть текстовых и визуальных данных в PDF сжимается с помощью алгоритма [[Deflate]]).

== Патенты ==
На алгоритм [[LZW]] и его вариации был выдан ряд патентов, как в США, так и в других странах. На LZ78 был выдан американский патент {{US patent|4464650}}, принадлежащий [[Sperry Corporation]], позднее ставшей частью [[Unisys Corporation]]. На LZW в США были выданы два патента: {{US patent|4814746}}, принадлежащий [[IBM]], и патент Велча {{US patent|4558302}} (выдан [[20 июня]] [[1983 год]]а), принадлежащий Sperry Corporation, позднее перешедший к Unisys Corporation. К настоящему времени сроки всех патентов истекли.

=== Unisys, GIF и PNG ===
При разработке формата [[GIF]] в CompuServe не знали о существовании патента {{US patent|4558302}}. В декабре 1994 года, когда в Unisys стало известно об использовании LZW в широко используемом графическом формате, эта компания распространила информацию о своих планах по взысканию лицензионных отчислений с коммерческих программ, имеющих возможность по созданию GIF-файлов. В то время формат был уже настолько широко распространён, что большинство компаний — производителей ПО не имело другого выхода, кроме как заплатить. Эта ситуация стала одной из причин разработки графического формата [[PNG]] (неофициальная расшифровка: «PNG’s Not GIF»<ref>{{Cite web |url=https://people.apache.org/~jim/NewArchitect/webrevu/1997/05_09/designers/05_09_97_1.html |title=Web Review: PNG's NOT GIF!|access-date=2018-10-18 |archive-date=2022-03-30 |archive-url=https://web.archive.org/web/20220330031000/https://people.apache.org/~jim/NewArchitect/webrevu/1997/05_09/designers/05_09_97_1.html |deadlink =no }}</ref>). В конце августа 1999 года Unisys прервала действие безвозмездных лицензий на LZW для бесплатного и некоммерческого ПО<ref>{{Cite web |url=http://people.ds.cam.ac.uk/jw35/docs/gif_patent.html |title=The Unisys LZW Patent and GIF files<!-- Заголовок добавлен ботом --> |access-date=2018-10-18 |archive-date=2018-10-19 |archive-url= https://web.archive.org/web/20181019001445/http://people.ds.cam.ac.uk/jw35/docs/gif_patent.html |deadlink=no }}</ref>, а также для пользователей нелицензированных программ, понудив ''League for Programming Freedom'' развернуть кампанию «сожжём все GIF’ы»<ref>{{Cite web |url= https://news.slashdot.org/story/99/08/29/0722236/unisys-enforcing-gif-patents |title=Unisys Enforcing GIF Patents - Slashdot<!-- Заголовок добавлен ботом --> |access-date=2018-10-18 |archive-date=2018-10-18 |archive-url=https://web.archive.org/web/20181018201819/https://news.slashdot.org/story/99/08/29/0722236/unisys-enforcing-gif-patents |deadlink=no }}</ref> и информировать публику об имеющихся альтернативах. Многие эксперты в области патентного права отмечали, что патент не распространяется на устройства, которые могут лишь разжимать LZW-данные, но не сжимать их; по этой причине популярная утилита [[gzip]] может читать .Z-файлы, но не записывать их.

[[20 июня]] [[2003 год]]а истёк срок оригинального американского патента, что означает, что Unisys не может больше собирать по нему лицензионные отчисления. Аналогичные патенты в Европе, Японии и Канаде истекли в 2004 году.<!--<ref>http://freesoftwaremagazine.com/articles/gif_now_finally_free/</ref>-->

== Модификации ==
* LZC (1985, Thomas S. W., McKie J., Davies S., Turkowski K., Woods J. A. и Orost J. W.){{sfn|Bell, Witten, Cleary|1989|loc=раздел 3.4.8}} — одна из наиболее известных практических реализаций LZW, представленная в утилите {{iw|compress}} (Lempel-Ziv-Compress). LZC использует от 9 до 16 битов для кодов фраз (число битов растёт с ростом размера словаря, см. раздел о [[#Реализация|реализации]]); когда словарь переполняется, LZC просто продолжает его использование без дальнейшей модификации, но при этом алгоритм следит за степенью сжатия данных и, когда сжатие с текущим словарём становится неприемлемо плохим, LZC очищает словарь и продолжает работу. LZC сжимает хуже, чем LZW, но зато скорость сжатия выше.
* LZT (1985, Tischer P.){{sfn|Bell, Witten, Cleary|1989|loc=раздел 3.4.9}} — другой известный вариант LZW. При переполнении словаря LZT продолжает работу, но каждый раз перед вставкой новой фразы в словарь, он удаляет фразу, которая соответствует дольше всего не используемому листу в [[Префиксное дерево|префиксном дереве]], содержащем все фразы. В реализации LZT все листья помещаются в связный список, и каждый раз после использования в ходе сжатия листья перемещаются в голову списка; таким образом, листья, которые не использовались дольше всего, находятся в хвосте списка (дальнейшие детали очевидны).
* LZMW (1985, [[Миллер, Виктор (математик)|Виктор Миллер]] и {{iw|Вегман, Марк|Марк Вегман|en|Mark N. Wegman}}){{sfn|Miller, Wegman|1985}} — находит во входном потоке самую длинную строку, которая уже имеется в словаре (обозначим её W), выдаёт на выход код W, а затем добавляет в словарь строку VW, где V — это строка из словаря, код которой был выдан на предыдущем шаге (изначально V является пустой строкой). Таким образом, строки в словаре растут быстрее, чем в исходном варианте LZW, и на практике часто удаётся получить лучшее качество сжатия. Миллер и Вегман также предложили в случае недостатка памяти удалять из словаря фразы, которые редко используются, так же как это делается в LZT.
* LZAP (1988, Джеймс Сторер){{sfn|Storer|1988}} — модификация LZMW, отличающаяся тем, что на каждом шаге в словарь добавляется не только строка VW, но и строки VW<sub>1</sub>, VW<sub>2</sub>, …, VW<sub>|W|-1</sub>, где W<sub>i</sub> — это префикс W длины i. («AP» в «LZAP» означает «all prefixes», то есть «все префиксы».) Например, если V = ''wiki'' и W = ''pedia'' — то есть на предыдущем шаге алгоритм нашёл в словаре строку ''wiki'', а на данном нашёл ''pedia'' — то алгоритм добавит в словарь строку ''wikipedia'', как сделал бы LZMW, но также добавит строки ''wikip'', ''wikipe'', ''wikiped'', ''wikipedi''. Алгоритм LZAP проще для реализации, чем LZMW, но в то же время он сохраняет большинство преимуществ LZMW за исключением того, что коды словарных строк занимают больше места, потому что словарь более раздут.

== См. также ==
* [[LZ]]
* [[LZ77]]
* [[LZMA]]

== Примечания ==
{{примечания|25em}}

== Литература ==
* {{статья
  |автор=Arnold R., {{iw|Белл, Тим (учёный)|Bell T.|en|Tim Bell (computer scientist)}}
  |заглавие= A corpus for the evaluation of lossless compression algorithms
  |издание= IEEE Data Compression Conference
  |страницы=201–210
  |год=1997
  |ref=Arnold, Bell
  |doi=10.1109/DCC.1997.582019
}}
* {{статья
  |автор={{iw|Белл, Тим (учёный)|Bell T.|en|Tim Bell (computer scientist)}}, {{iw|Виттен, Иан|Witten I. H.|en|Ian H. Witten}}, {{iw|Клири, Джон|Cleary J. G.|en|John G. Cleary}}
  |заглавие= Modeling for text compression
  |издание= {{iw|ACM Computing Surveys}}
  |номер=4
  |том=21
  |страницы=557–591
  |год=1989
  |ref=Bell, Witten, Cleary
  |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
  |издание= {{iw|IEEE Transactions on Information Theory}}
  |номер=7
  |том=51
  |страницы=2554—2576
  |год=2005
  |ref=Charikar et al.
  |doi=10.1109/TIT.2005.850116
}}
* {{статья
  |автор=De Agostino S., Silvestri R.
  |заглавие= A worst-case analysis of the LZ2 compression algorithm
  |издание= {{iw|Information and Computation}}
  |номер=2
  |том=139
  |страницы=258–268
  |год=1997
  |ref=De Agostino, Silvestri
  |doi=10.1006/inco.1997.2668
}}
* {{статья
  |автор=De Agostino S., Storer J. A.
  |заглавие= On-line versus off-line computation in dynamic text compression
  |издание= {{iw|Information Processing Letters}}
  |номер=3
  |том=59
  |страницы=169–174
  |год=1996
  |ref=De Agostino, Storer
  |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)
  |том=9954
  |страницы=35–49
  |год=2016
  |ref=Hucke, Lohrey, Reh
  |doi=10.1007/978-3-319-46049-9_4
}}
* {{статья
  |автор=[[Лемпель, Авраам|Lempel A.]], [[Зив, Яаков|Ziv J.]]
  |заглавие= Compression of individual sequences via variable-rate coding
  |издание= {{iw|IEEE Transactions on Information Theory}}
  |номер=5
  |том=24
  |страницы=530–536
  |год=1978
  |ref=Lempel, Ziv
  |doi=10.1109/TIT.1978.1055934
}}
* {{статья
  |автор={{iw|Миллер, Виктор (криптограф)|Miller V. S|en|Victor S. Miller}}, {{iw|Вегман, Марк|Wegman M. N.|en|Mark N. Wegman}}
  |заглавие= Variations on a theme by Ziv and Lempel
  |издание= Combinatorial algorithms on words
  |том=12
  |страницы=131–140
  |год=1985
  |ref=Miller, Wegman
  |doi=10.1007/978-3-642-82456-2_9
}}
* {{статья
  |автор=Sheinwald D.
  |заглавие= On the Ziv-Lempel proof and related topics
  |издание= {{iw|Proceedings of the IEEE}}
  |номер=6
  |том=82
  |страницы=866–871
  |год=1994
  |ref=Sheinwald
  |doi=10.1109/5.286190
}}
* {{книга
  |автор=Storer J. A.
  |заглавие= Data Compression: Methods and Theory
  |издательство= Computer Science Press
  |место= New York, USA
  |год=1988
  |страниц=413
  |isbn=0-7167-8156-5
  |ref=Storer
}}
* {{статья
  |автор=[[Велч, Терри|Welch T. A.]]
  |заглавие= A technique for high-performance data compression
  |издание= Computer
  |номер=17
  |том=6
  |страницы=8–19
  |год=1984
  |ref=Welch
  |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
  |страницы=1–4
  |год=2015
  |ref=Ziv
  |doi=10.1109/ITW.2015.7133077
}}
* {{cite web
  |url=https://www.adobe.com/content/dam/acom/en/devnet/pdf/pdfs/PDF32000_2008.pdf
  |title=Document management — Portable document format — Part 1: PDF 1.7  
  |author=Adobe Systems Incorporated
  |date=2008-07-01
  |work=PDF 1.7 specification 
  |publisher=Adobe
  |accessdate=2018-01-26
  |ref=PDF 1.7 specification
  |lang=en
}}

{{методы сжатия}}
{{Форматы архивов}}

[[Категория:Алгоритмы сжатия без потерь]]
[[Категория:Алгоритмы сжатия с использованием словаря]]
[[Категория:Патент истёк]]
[[Категория:2004 год в науке]]
[[Категория:2003 год в науке]]
[[Категория:1983 год в науке]]
[[Категория:2003 год в праве]]
[[Категория:2004 год в праве]]