Изменения

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

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

Алгоритм был реализован в программе compressЭтот метод позволяет достичь одну из наилучших степеней сжатия среди других существующих методов сжатия графических данных, которая стала более при полном отсутствии потерь или менее стандартной утилитой Unix-систем приблизительно искажений в 1986 годуисходных файлах. Многие другие утилиты-архиваторы В настоящее время используется в файлах формата TIFF, PDF, GIF, PostScript и других, а также используют этот метод или близкие к немуотчасти во многих популярных программах сжатия данных (ZIP, ARJ, LHA).

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

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

== Алгоритм =Кодирование ===* Начало.* ''' Шаг 1. ''' Все возможные символы заносятся в словарь. Во входную фразу <tex>X</tex> заносится первый символ сообщения.* ''' Шаг 2. ''' Считать очередной символ <tex>Y</tex> из сообщения.* ''' Шаг 3. ''' Если <tex>Y</tex> {{---}} это символ конца сообщения, то выдать код для <tex>X</tex>, иначе: ** Если фраза <tex>XY</tex> уже имеется в словаре, то присвоить входной фразе значение <tex>XY</tex> и перейти к ''' Шагу 2 ''', ** Иначе выдать код для входной фразы <tex>X</tex>, добавить <tex>XY</tex> в словарь и присвоить входной фразе значение <tex>Y</tex>. Перейти к ''' Шагу 2. '''* Конец.

# Инициализация словаря всеми возможными односимвольными фразами=== Декодирование ===* Начало. Инициализация входной фразы ω первым символом * ''' Шаг 1. ''' Все возможные символы заносятся в словарь. Во входную фразу <tex>X</tex> заносится первый код декодируемого сообщения.# * ''' Шаг 2. ''' Считать очередной символ K код <tex>Y</tex> из кодируемого сообщения.# * ''' Шаг 3. ''' Если КОНЕЦ_СООБЩЕНИЯ<tex>Y</tex> {{---}} это конец сообщения, то выдать код для ωсимвол, соответствующий коду <tex>X</tex>, иначе: # ** Если фраза ωK уже есть фразы под кодом <tex>XY</tex> нет в словаре, присвоить входной фразе значение ωK и перейти к Шагу 2вывести фразу, иначе выдать код ωсоответствующую коду <tex>X</tex>, добавить ωK а фразу с кодом <tex>XY</tex> занести в словарь, . ** Иначе присвоить входной фразе значение K код <tex>XY</tex> и перейти к ''' Шагу 2'''.* Конец.

Данный Рассмотрим пример показывает алгоритм LZW в действии, показывая состояние выходных данных и словаря на каждой стадии, как при кодировании, так сжатия и при раскодировании декодирования сообщения. С тем чтобы сделать изложение проще, мы ограничимся алфавитом из трех буквСначала создадим начальный словарь единичных символов.СообщениеВ стандартной кодировке ASCII имеется <tex>256</tex> различных символов, которое нужно сжатьпоэтому, выглядит следующим образом: ABCABCABCABCABCABC#Маркер '''#''' используется для обозначения конца сообщения. Тем самымтого, чтобы все они были корректно закодированы (если нам неизвестно, какие символы будут присутствовать в нашем алфавите 4 символаисходном файле, а какие — нет), начальный размер кода будет равен <tex>8</tex> битам. Компьютер представляет это Если нам заранее известно, что в виде групп битисходном файле будет меньшее количество различных символов, для представления каждого символа алфавита нам достаточно группы из 2 то вполне разумно уменьшить количество бит на символ. По мере роста словаряЧтобы инициализировать таблицу, размер групп должен растимы установим соответствие кода <tex>0</tex> соответствующему символу с битовым кодом <tex>00000000</tex>, тогда <tex>1</tex>соответствует символу с тем чтобы учесть новые элементы. 2-битные группы дают 2кодом <suptex>200000001</suptex> = 4 возможные комбинации бит, поэтому, когда в словаре появится 5-е слово, алгоритм должен перейти к 3-битным группами т.д. Заметим, что, поскольку используется группа из всех нолей 00, то 5-я группа имеет код '''4'''до кода <tex>255</tex>. Начальный словарь будет содержать: {| class="wikitable" border = 1, style="float:right; text-align: right; margin-left: auto; margin-right: auto;"

! Символ !! Битовый код !! НомерКод

| # a || 00 000 || 0

| A b || 01 001 || 1

| B c || 10 010 || 2

| C d || 11 011 || 3|-| e || 100 || 4

Без использования алгоритма LZWПусть мы сжимаем последовательность <tex>abacabadabacabae</tex>. * '''Шаг 1: '''Тогда, согласно изложенному выше алгоритму, мы добавим к изначально пустой строке <tex>a</tex> и проверим, есть ли строка <tex>a</tex> в таблице. Поскольку мы при передаче сообщения как оно есть — 18 символов по инициализации занесли в таблицу все строки из одного символа, то строка <tex>a</tex> есть в таблице. * '''Шаг 2 бит на каждый — оно займёт 36 бит: '''Далее мы читаем следующий символ <tex>b</tex> из входного потока и проверяем, есть ли строка <tex>ab</tex> в таблице. Такой строки в таблице пока нет.Добавляем в таблицу <tex>\langle5\rangle</tex> <tex>ab</tex>. В поток: <tex>\langle0\rangle</tex>;* '''Шаг 3: '''<tex>ba</tex> — нет. В таблицу: <tex>\langle6\rangle</tex> <tex>ba</tex>. Сравним это с темВ поток: <tex>\langle1\rangle</tex>;* '''Шаг 4: '''<tex>ac</tex> — нет. В таблицу: <tex>\langle7\rangle</tex> <tex>ac</tex>. В поток: <tex>\langle0\rangle</tex>;* '''Шаг 5: '''<tex>ca</tex> — нет. В таблицу: <tex>\langle8\rangle</tex> <tex>ca</tex>. В поток: <tex>\langle2\rangle</tex>;* '''Шаг 6: '''<tex>ab</tex> — есть в таблице; <tex>aba</tex> — нет. В таблицу: <tex>\langle9\rangle</tex> <tex>aba</tex>. В поток: <tex>\langle5\rangle</tex>;* '''Шаг 7: '''<tex>ad</tex> — нет. В таблицу: <tex>\langle10\rangle</tex> <tex>ad</tex>. В поток: <tex>\langle0\rangle</tex>;* '''Шаг 8: '''<tex>da</tex> — нет. В таблицу: <tex>\langle11\rangle</tex> <tex>da</tex>. В поток: <tex>\langle3\rangle</tex>;* '''Шаг 9: '''<tex>aba</tex> — есть в таблице; <tex>abac</tex> — нет. В таблицу: <tex>\langle12\rangle</tex> <tex>abac</tex>. В поток: <tex>\langle9\rangle</tex>;* '''Шаг 10: '''<tex>ca</tex> — есть в таблице; <tex>cab</tex> — нет. В таблицу: <tex>\langle13\rangle</tex> <tex>cab</tex>. В поток: <tex>\langle8\rangle</tex>;* '''Шаг 11: '''<tex>ba</tex> — есть в таблице; <tex>bae</tex> — нет. В таблицу: <tex>\langle14\rangle</tex> <tex>bae</tex>. В поток: <tex>\langle6\rangle</tex>;* '''Шаг 12: '''И, наконец последняя строка <tex>e</tex>, за ней идет конец сообщения, что получается при использовании LZW:поэтому мы просто выводим в поток <tex>\langle4\rangle</tex>.

! scope="col" width="7em" rowspan="2" colspan="2" | Расширенный словарь! rowspan="2" | КомментарииСловарь

| style="text-align: center;" | Aab| style="text-align: center;" | B| 1 || 01| style="border-right: none;" | 4:| style="border-left: none;" | AB| style="text-align: left;" | |-| style="text-align: center;" | Ba| style="text-align: center;" | Cb| 2 0 || 10000

| style="border-left: none;" | BC ||ab

| style="text-align: center;" | Cba| style="text-align: center;" | Ab| 3 style="text-align: center;" | a| 1 || 11001

| style="border-left: none;" | CA ||ba

| style="text-align: center;" | ABac| style="text-align: center;" | Ca| 4 style="text-align: center;" | c| 0 || 100000

| style="border-left: none;" | ABC ||ac

| style="text-align: center;" | CAca| style="text-align: center;" | Bc| 6 style="text-align: center;" | a| 2 || 110010

| style="border-left: none;" | CAB ca|-|style="text-align: center;" | ab| style="text-align: center;" | a| style="text-align: center;" | b| - || -| style="border-right: none;" | -| style="border-left: none;" | -

| style="text-align: center;" | BCaba| style="text-align: center;" | Ab| style="text-align: center;" | a| 5 || 1010101

| style="border-left: none;" | BCA| style="text-align: left;" | aba

| style="text-align: center;" | ABCad| style="text-align: center;" | Aa| 7 style="text-align: center;" | d| 0 || 1110000

| style="border-left: none;" | ABCAad

| style="text-align: center;" | ABCAda| style="text-align: center;" | Bd| 10 style="text-align: center;" | a| 3 || 10100011

| style="border-left: none;" | ABCAB ||da

| style="text-align: center;" | BCab| style="text-align: center;" | #a| 5 style="text-align: center;" | b| - || -| style="border-right: none;" | -| style="border-left: none;" | -|-| style="text-align: center;" | aba| style="text-align: center;" | b| style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" |-| 101-| style="text-align: center;" | abac| style="text-align: center;" | a| style="text-align: center;" | c| 9 || 1001| style="border-right: none;" | 12:| style="border-left: none;" |abac|-| style="text-align: center;" | выводим текущую последовательностьca| style="text-align: center;" | c| style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" | -|-| style="text-align: center;" | cab| style="text-align: center;" | a| style="text-align: center;" | b| 8 || 1000| style="border-right: none;" | 13:| style="border-left: none;" | cab|-| style="text-align: center;" | ba| style="text-align: center;" | b| style="text-align: center;" | a| - || -| style="border-right: none;" | -| style="border-left: none;" | -|-| style="text-align: center;" | bae| style="text-align: center;" | a| style="text-align: center;" | e| 6 || 0110| style="border-right: none;" | 14:| style="border-left: none;" | bae

| style="text-align: center;" |e| style="text-align: center;" || 0 || 000000e| style="bordertext-rightalign: nonecenter;" |-| 4 || 0100| style="border-leftright: none;" |-| style="textborder-alignleft: centernone;" | и останавливаем кодирование-

Длина закодированного текста Итак, мы получаем закодированное сообщение <tex>0 1 0 2 5 0 3 9 8 6 4</tex> и его битовый эквивалент <tex>000 001 000 010 0101 0000 0011 1001 1000 0110 0100</tex>. Каждый символ исходного сообщения был закодирован группой из трех бит, сообщение содержало <tex>16</tex> символов, следовательно длина сообщения составляла <tex>3 \cdot 16 = 25 битов48</tex> бит.

Таким образомЗакодированное же сообщение так же сначала кодировалось трехбитными группами, а при появлении в словаре восьмого слова — четырехбитными, итого длина сообщения составила <tex>4 \cdot 3 + 7 \cdot 4 = 40</tex> бит, используя LZW мы сократили сообщение что на 11 <tex>8</tex> бит из 36 — это почти 30 %. Если сообщение будет длиннее, то элементы словаря будут представлять всё более и более длинные части текста, благодаря чему повторяющиеся слова будут представлены очень компактнокороче исходного.

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

| 01 000 || 10| style="text-align: center;" | Aa| style="border-right: none;" || style="border-left: none;" || style="border-right: none;" | 4:| style="border-left: none;" | A? |||-| 10 || 2| style="text-align: center;" | B| style="border-right: none;" | 4:| style="border-left: none;" | AB

| style="border-left: none;" | Ba? ||

| 11 001 || 31| style="text-align: center;" | Cb

| style="border-left: none;" | BCab

| style="border-left: none;" | Cb? ||

| 100 000 || 40| style="text-align: center;" | ABa

| style="border-left: none;" | CAba

| style="border-left: none;" | ABa? ||

| 110 010 || 62| style="text-align: center;" | CAc

| style="border-left: none;" | ABCac

| style="border-left: none;" | CAc? ||

| 101 0101 || 5| style="text-align: center;" | BCab

| style="border-left: none;" | CABca| style="border-right: none;" | 329:| style="border-left: none;" | Rab?| style="text-align: left;" | создали код 31 (последний, содержащий 5 бит)

| 111 0000 || 70| style="text-align: center;" | Na| style="border-right: none;" | 329:| style="border-left: none;" | RNaba| style="border-right: none;" | 3310:| style="border-left: none;" | Na?|-| 0011 || 3| style="text-align: center;" | d| style="border-right: none;" | 10:| style="border-left: none;" | начинаем использовать 6 битad| style="border-right: none;" | 11:| style="border-left: none;" | d?|-| 1001 || 9| style="text-align: center;" | aba| style="border-right: none;" | 11:| style="border-left: none;" | da| style="border-right: none;" | 12:| style="border-left: none;" | aba?

| style="text-align: center;" | Oca| style="border-right: none;" | 3312:| style="border-left: none;" | NOabac| style="border-right: none;" | 3413:| style="border-left: none;" | Oca? ||

| 101 0110 || 56| style="text-align: center;" | Tba| style="border-right: none;" | 3413:| style="border-left: none;" | OTcab| style="border-right: none;" | 3514:| style="border-left: none;" | Tba? ||

| 011011 0100 || 274| style="text-align: center;" | TOe| style="border-right: none;" | 3514:| style="border-left: none;" | TTbae| style="border-right: none;" | 36:-| style="border-left: none;" | TO? ||-

| 011101 } === Примечание === Для повышения степени сжатия изображений данным методом часто используется одна “хитрость” реализации этого алгоритма. Некоторые файлы, подвергаемые сжатию с помощью LZW, имеют часто встречающиеся цепочки одинаковых символов, например <tex>aaaaaaaaaaaaa... </tex> или <tex>303030</tex> … и т. п. Их непосредственное сжатие будет генерировать выходной код <tex>005000600007...</tex>. Спрашивается, можно ли в этом частном случае повысить степень сжатия? Оказывается, это возможно, если оговорить некоторые действия: Мы знаем, что для каждого кода надо добавлять в таблицу строку, состоящую из уже присутствующей там строки и символа, с которого начинается следующая строка в потоке.*''' ''' Пусть словарь состоит из слов : <tex>a, b, c, d, e</tex>. Будем кодировать строку <tex> aaaaaaaaaa </tex>*''' ''' Итак, кодировщик заносит первую <tex>a</tex> в строку, ищет и находит <tex>a</tex> в словаре под номером <tex>\langle0\rangle</tex>. Добавляет в строку следующую <tex>a</tex>, находит, что <tex>aa</tex> нет в словаре. Тогда он добавляет запись <tex>\langle5\rangle</tex>: <tex>aa</tex> в словарь и выводит метку <tex>\langle0\rangle</tex> (<tex>a</tex>) в выходной поток. *''' '''Далее строка инициализируется второй <tex>a</tex>, то есть принимает вид <tex>a?</tex> вводится третья <tex>a</tex>, строка вновь равна <tex>aa</tex>, которая теперь имеется в словаре. *''' '''Если появляется четвертая <tex>a</tex>, то строка <tex>aa?</tex> равна <tex>aaa</tex>, которой нет в словаре. Словарь пополняется этой строкой, а на выход идет метка <tex>\langle5\rangle</tex> (<tex>aa</tex>). *''' '''После этого строка инициализируется третьей <tex>a</tex>, и т.д. и т.п. Дальнейший процесс вполне ясен.  [[Файл:LZW-img.jpg|center|Работа алгоритма LZW]] {| class="wikitable" border = 1, style="text-align: center; margin-left: auto; margin-right: auto;"|- bgcolor=#EEEEEE! Слово !! Номер в словаре|-| a || <tex>\langle0\rangle</tex>|-| b || <tex>\langle1\rangle</tex>|-| c || <tex>\langle2\rangle</tex>|-| d || <tex>\langle3\rangle</tex>|-| e || <tex>\langle4\rangle</tex>|} {| class="wikitable" border =1, style="text-align: center; margin-left: auto; margin-right: auto;"|- bgcolor =#EEEEEE! scope="col" width="6em" rowspan="2" | Текущая строка! scope="col" width="6em" rowspan="2" | Текущий символ! scope="col" width="4em" rowspan="2" | Следующий символ! colspan="2" | Вывод! scope="col" width="7em" rowspan="2" colspan="2" |Словарь|- bgcolor =#EEEEEE! Код || Биты|-| style="text-align: center;" | aa| style="text-align: center;" | 29a| style="text-align: center;" | BEa| 0 || 000| style="border-right: none;" | 365:| style="border-left: none;" | TOBaa|-| style="text-align: center;" | aa| style="text-align: center;" | a| style="text-align: center;" | a| - || -| style="border-right: none;" | 37:-| style="border-left: none;" | BE?-|-| style="text-align: center;" | aaa| style="text-align: center;" | a| style="text-align: center;" | a| 5 || 101| style="border-right: none;" | 6:| style="border-left: none;" | 36 = TO + 1й символ (B) aaa

| 011111 || 31| style="text-align: center;" | ORa| style="bordertext-rightalign: nonecenter;" | 37:a| style="bordertext-leftalign: nonecenter;" | BEOa| - || -| style="border-right: none;" | 38:-| style="border-left: none;" | OR?| style="text-align: left;" | следующей полученной последовательности (BE)

| 100100 || 36| style="text-align: center;" | TOBaa| style="bordertext-rightalign: nonecenter;" | 38:a| style="bordertext-leftalign: nonecenter;" | ORTa| - || -| style="border-right: none;" | 39:-| style="border-left: none;" | TOB? ||-

| 011110 || 30| style="text-align: center;" | EOaaa| style="bordertext-rightalign: nonecenter;" | 39:a| style="bordertext-leftalign: nonecenter;" | TOBEa| - || -| style="border-right: none;" | 40:-| style="border-left: none;" | EO? ||-

| 100000 || 32| style="text-align: center;" | RNaaaa| style="bordertext-rightalign: nonecenter;" | 40:a| style="bordertext-leftalign: nonecenter;" | EORa| 6 || 110| style="border-right: none;" | 417:| style="border-left: none;" | RN? ||aaaa

| 100010 || 34| style="text-align: center;" | OTa| style="bordertext-rightalign: nonecenter;" | 41:a| style="bordertext-leftalign: nonecenter;" | RNOa| - || -| style="border-right: none;" | 42:-| style="border-left: none;" | OT? ||-

| 000000 || 0| style="text-align: center;" | #aa| style="bordertext-rightalign: nonecenter;" | a| style="bordertext-leftalign: nonecenter;" |a| - || -| style="border-right: none;" |-| style="border-left: none;" | ||- 

Единственная небольшая трудность может возникнутьВ результате на выходе получаем последовательность <tex>0567</tex>. При кодировании использовались только трехбитные группы. Длина закодированного сообщения составила <tex> 4 \cdot 3 = 12 </tex> бит, если новое слово словаря пересылается немедленночто на <tex> 7 \cdot 3 - 12 = 9</tex> бит короче кодирования стандартным методом LZW. В приведённом выше примере декодированияМожно показать, когда декодер встречает что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код – это <tex>\langle0\rangle</tex>, которому соответствует символ<tex>a</tex>. Затем читает код <tex>\langle5\rangle</tex>, '''T'''но этого кода в его таблице нет. Но мы уже знаем, он знаетчто такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что слово 27 начинается считанной последовательности, то есть <tex>a</tex>. Поэтому он добавит в свою таблицу строку <tex>aa</tex> с Tкодом <tex>\langle5\rangle</tex>, а в выходной поток поместит <tex>aa</tex>. И так может быть раскодирована вся цепочка кодов. Мало того, описанное выше правило кодирования мы можем применять в общем случае не только к подряд идущим одинаковым символам, но чем оно заканчивается? Проиллюстрируем проблему следующим примероми к последовательностям, у которых очередной добавляемый символ равен первому символу цепочки. Мы декодируем сообщение '''ABABA''': Данные: На выходе: Новая запись: Полная: Частичная:=== Преимущества алгоритма LZW ===  * Алгоритм является однопроходным. * Для декомпрессии не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов. . 011101 = 29 AB 46: (word) 47: AB?== Недостатки алгоритма LZW === 101111 = 47 AB? <--- что нам с этим делать?* Алгоритм не проводит анализ входных данных.

В общем случае, такая ситуация появляется, когда кодируется последовательность вида ''cScSc'', где ''c'' — это один символ, а ''S'' — строка, причём слово ''cS'' уже есть в словаре* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%BC%D0%BF%D0%B5%D0%BB%D1%8F_%E2%80%94_%D0%97%D0%B8%D0%B2%D0%B0_%E2%80%94_%D0%92%D0%B5%D0%BB%D1%87%D0%B0 Википедия {{---}} Алгоритм Лемпеля {{---}} Зива {{---}} Велча]

== Патенты ==На алгоритм LZW и его вариации был выдан ряд патентов, как в США, так и в других странах* [http://en. wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch К настоящему времени, сроки всех патентов истекли.Wikipedia {{---}} Lempel {{---}} Ziv {{---}} Welch]

=== Unisys, GIF и PNG ===При разработке формата GIF в CompuServe не знали о существовании патента* [http://compression. В декабре 1994 года, когда в Unisys стало известно об использовании LZW в широко используемом графическом формате, эта компания распространила информацию о своих планах по взысканию лицензионных отчислений с коммерческих программ, имеющих возможность по созданию GIF-файловru/download/articles/rev_univ/semenyuk_2001_econom_encoding. pdf Семенюк В то время формат был уже настолько широко распространён, что большинство компаний-производителей ПО не имели другого выхода кроме как заплатить. Эта ситуация стала одной из причин разработки графического формата PNG (неофициальная расшифровка: «PNG’s Not GIF»), ставшего третьим по распространённости в Интеренете, после GIF и JPEG. В конце августа 1999 года Unisys прервала действие безвозмездных лицензий на LZW для бесплатного и некоммерческого ПО, а также для пользователей нелицензированных программ, призвав ''League for Programming Freedom'' развернуть кампанию «сожжём все GIF’ы» и информировать публику об имеющихся альтернативах. Многие эксперты в области патентного права отмечали, что патент не распространяется на устройства, которые могут лишь разжимать LZW{{--данные, но не сжимать их; по этой причине, популярная утилита gzip может читать .Z-файлы, но не записывать их.}} Экономное кодирование дискретной информации]

20 июня 2003 года истёк срок оригинального американского патента, что означает, что Unisys не может больше собирать по нему лицензионные отчисления* [http://algolist. Аналогичные патенты в Европе, Японии manual.ru/compress/standard/lzw.php Метод LZW {{---}} сжатия данных {{---}} алгоритмы и Канаде истекли в 2004 году.методы]

* [http://ruwww.wikipediaalgoritmy.orginfo/wiki/LZW Wikipedia | picture5.html Алгоритм LZW{{---}} Понятие алгоритма]

* [http[Категория: Дискретная математика и алгоритмы]][[Категория://en.wikipedia.org/wiki/LZW Wikipedia | LZWАлгоритмы сжатия]]