Лемпель – Зив – Уэлч

Lempel-Ziv-Welch ( LZW ) — универсальный сжатия данных без потерь, алгоритм созданный Авраамом Лемпелем , Джейкобом Зивом и Терри Уэлчем . Он был опубликован Уэлчем в 1984 году как улучшенная реализация алгоритма LZ78 , опубликованного Лемпелем и Зивом в 1978 году. Алгоритм прост в реализации и потенциально может обеспечить очень высокую пропускную способность в аппаратных реализациях. Это алгоритм Unix утилиты сжатия файлов compress , который используется в формате изображений GIF .

Алгоритм

Сценарий, описанный в статье Уэлча 1984 года. кодирует последовательности 8-битных данных как 12-битные коды фиксированной длины. Коды от 0 до 255 представляют собой односимвольные последовательности, состоящие из соответствующего 8-битного символа, а коды с 256 по 4095 создаются в словаре для последовательностей, встречающихся в данных по мере их кодирования. На каждом этапе сжатия входные байты собираются в последовательность до тех пор, пока следующий символ не составит последовательность без кода в словаре. Код последовательности (без этого символа) добавляется в выходные данные, а новый код (для последовательности с этим символом) добавляется в словарь.

Идея была быстро адаптирована к другим ситуациям. Например, в изображении, основанном на таблице цветов, естественный алфавит символов представляет собой набор индексов таблицы цветов, а в 1980-х годах многие изображения имели небольшие таблицы цветов (порядка 16 цветов). Для такого сокращенного алфавита полные 12-битные коды давали плохое сжатие, если только изображение не было большим, поэтому была введена идея кода переменной ширины : коды обычно начинаются на один бит шире, чем кодируемые символы, и по мере того, как каждый размер кода Когда код исчерпан, ширина кода увеличивается на 1 бит до некоторого заданного максимума (обычно 12 бит). При достижении максимального значения кода кодирование продолжается с использованием существующей таблицы, но новые коды для добавления в таблицу не генерируются.

Дальнейшие усовершенствования включают резервирование кода, указывающего, что кодовая таблица должна быть очищена и восстановлена ​​в исходное состояние («код очистки», обычно первое значение сразу после значений отдельных символов алфавита), а также код, указывающий конец данных («стоп-код», обычно на один больше, чем чистый код). Чистый код позволяет повторно инициализировать таблицу после ее заполнения, что позволяет кодировке адаптироваться к изменению шаблонов во входных данных. Интеллектуальные кодировщики могут контролировать эффективность сжатия и очищать таблицу, когда существующая таблица больше не соответствует входным данным.

Поскольку коды добавляются способом, определяемым данными, декодер имитирует построение таблицы по мере того, как он видит результирующие коды. Крайне важно, чтобы кодер и декодер согласовали тип используемого LZW: размер алфавита, максимальный размер таблицы (и ширину кода), используется ли кодирование переменной ширины, начальный размер кода и следует ли использовать и стоп-коды (и какие значения они имеют). Большинство форматов, использующих LZW, включают эту информацию в спецификацию формата или предоставляют для нее явные поля в заголовке сжатия данных.

Кодирование

Здесь показано высокоуровневое представление алгоритма кодирования:

1. Инициализируйте словарь, чтобы он содержал все строки длины один.
2. самую длинную строку W , соответствующую текущему вводу. Найдите в словаре
3. Выдайте индекс словаря для W на вывод и удалите W из ввода.
4. Добавьте W , а затем следующий символ во входных данных словаря.
5. Перейдите к шагу 2.

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

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

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

Здесь показано высокоуровневое представление алгоритма декодирования:

1. Инициализируйте словарь, чтобы он содержал все строки длины один.
2. Прочитайте следующий закодированный символ: он закодирован в словаре?
   1. Да:
      1. соответствующую строку W. Выведите на вывод
      2. с первым символом W. Объедините предыдущую строку, отправленную на вывод , Добавьте это в словарь.
   2. Нет:
      1. Объединить предыдущую строку, отправленную на вывод, с ее первым символом. Назовите эту строку V .
      2. Добавьте V в словарь и выведите V на вывод.
3. Повторяйте шаг 2 до конца входной строки.

Алгоритм декодирования работает, считывая значение из закодированного ввода и выводя соответствующую строку из словаря. Однако полный словарь не нужен, нужен только начальный словарь, содержащий односимвольные строки (и который обычно жестко запрограммирован в программе, а не отправляется вместе с закодированными данными). Вместо этого полный словарь перестраивается в процессе декодирования следующим образом: после декодирования значения и вывода строки декодер объединяет его с первым символом следующей декодируемой строки (или первым символом текущей строки, если следующая не может быть декодировано; поскольку, если следующее значение неизвестно, то это должно быть значение, добавленное в словарь в этой итерации, и поэтому его первый символ совпадает с первым символом текущей строки) и обновляет словарь. с новой строкой. Затем декодер переходит к следующему вводу (который уже был прочитан на предыдущей итерации) и обрабатывает его, как и раньше, и так далее, пока не исчерпает входной поток.

Коды переменной ширины

Если используются коды переменной ширины, кодер и декодер должны быть осторожны, чтобы изменить ширину в одних и тех же точках закодированных данных, чтобы они не расходились во мнениях относительно границ между отдельными кодами в потоке. В стандартной версии кодер увеличивает ширину с p до p +1, когда встречается последовательность ω+ s , которой нет в таблице (так что для нее необходимо добавить код), но следующий доступный код в таблице есть 2 ^п (первый код требует p + 1 бит). Кодер выдает код для ω шириной p (поскольку этот код не требует p + 1 бит), а затем увеличивает ширину кода так, чтобы следующий выдаваемый код имел ширину p + 1 бит.

Декодер всегда отстает на один код от кодера при построении таблицы, поэтому, когда он видит код для ω, он генерирует запись для кода 2. ^п − 1. Поскольку это точка, в которой кодер увеличивает ширину кода, декодер должен также увеличить ширину здесь — в точке, где он генерирует наибольший код, умещающийся в p битах.

К сожалению, некоторые ранние реализации алгоритма кодирования увеличивают ширину кода, а затем выдают ω с новой шириной вместо старой, так что для декодера это выглядит так, будто ширина изменяется на один код слишком рано. Это называется «ранними изменениями»; это вызвало такую ​​​​путаницу, что Adobe теперь разрешает обе версии в файлах PDF, но включает явный флаг в заголовок каждого потока, сжатого LZW, чтобы указать, используются ли ранние изменения. Из форматов графических файлов, поддерживающих сжатие LZW, TIFF использует раннее изменение, а GIF и большинство других — нет.

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

Порядок упаковки

Поскольку создаваемые коды обычно не попадают в границы байтов, кодер и декодер должны договориться о том, как коды упаковываются в байты. Двумя распространенными методами являются LSB-first (« сначала наименее значимый бит ») и MSB-first (« сначала наиболее значимый бит »). При упаковке LSB-first первый код выравнивается так, что младший значащий бит кода попадает в младший значащий бит первого байта потока, а если код имеет более 8 бит, оставшиеся старшие биты выравнивается по младшим битам следующего байта; дальнейшие коды упаковываются, начиная с младшего значащего бита, который еще не используется в текущем байте потока, и при необходимости переходя к дальнейшим байтам. Упаковка с приоритетом MSB выравнивает первый код так, что его старший бит попадает в старший бит первого байта потока, а переполнение выравнивается со старшим битом следующего байта; дальнейшие коды записываются со старшим битом, который еще не используется в текущем байте потока.

В файлах GIF используется порядок упаковки «сначала младший бит». В файлах TIFF и PDF используется порядок упаковки «сначала MSB».

Пример

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

Открытый текст, который необходимо закодировать (из алфавита, в котором используются только заглавные буквы):

TOBEORNOTTOBEORTOBEORNOT#

В алфавите открытого текста 26 символов (заглавные буквы от A до Z ). # используется для обозначения кода остановки: кода вне алфавита открытого текста, который запускает специальную обработку. Мы произвольно присваиваем им значения от 1 до 26 для букв и 0 для стоп-кода «#». (В большинстве разновидностей LZW стоп-код помещается после алфавита данных, но в базовом алгоритме этого не требуется. Кодеру и декодеру нужно только согласовать, какое значение он имеет.)

Компьютер визуализирует их как строки битов . Пятибитные коды необходимы для создания достаточных комбинаций, охватывающих этот набор из 27 значений. Словарь инициализируется этими 27 значениями. По мере роста словаря коды должны увеличиваться в ширину, чтобы вместить дополнительные записи. 5-битный код дает 2 ⁵ = 32 возможных комбинации битов, поэтому при создании 33-го словарного слова алгоритм должен в этот момент переключиться с 5-битных строк на 6-битные строки (для всех значений кода, включая те, которые ранее выводились только с пятью битами). Обратите внимание, что поскольку используется нулевой код 00000 и он помечен как «0», 33-я запись словаря помечена как 32 . (Изменение ширины кода не влияет на ранее сгенерированный вывод, но как только в словаре генерируется 6-битное значение, оно, вероятно, может быть следующим выдаваемым кодом, поэтому ширина последующего вывода смещается до 6 бит, чтобы приспособиться к этому. )

Таким образом, исходный словарь состоит из следующих статей:

Символ	Двоичный	Десятичный
#	00000	0
А	00001	1
Б	00010	2
С	00011	3
Д	00100	4
И	00101	5
Ф	00110	6
Г	00111	7
ЧАС	01000	8
я	01001	9
Дж	01010	10
К	01011	11
л	01100	12
М	01101	13
Н	01110	14
ТО	01111	15
П	10000	16
вопрос	10001	17
Р	10010	18
С	10011	19
Т	10100	20
В	10101	21
V	10110	22
В	10111	23
Х	11000	24
И	11001	25
С	11010	26

Кодирование

Буферизировать входные символы последовательности ω до тех пор, пока ω + следующий символ не исчезнет в словаре. Введите код для ω и добавьте ω + следующий символ в словарь. Начните буферизацию снова со следующего символа. (Кодируемая строка: «TOBEORNOTTOBEORTOBEORNOT#».)

Текущая последовательность	Следующий символ	Выход		Расширенный словарь		Комментарии
		Код	Биты
НУЛЕВОЙ	Т
Т	ТО	20	10100	27:	К	27 = первый доступный код после 0 до 26.
ТО	Б	15	01111	28:	OB
Б	И	2	00010	29:	БЫТЬ
И	ТО	5	00101	30:	ЭО
ТО	Р	15	01111	31:	ИЛИ
Р	Н	18	10010	32:	РН	32 требует 6 бит, поэтому для следующего вывода используйте 6 бит.
Н	ТО	14	001110	33:	НЕТ
ТО	Т	15	001111	34:	OT
Т	Т	20	010100	35:	ТТ
К	Б	27	011011	36:	ГЛУБОКИЙ
БЫТЬ	ТО	29	011101	37:	ЖИТЬ
ИЛИ	Т	31	011111	38:	РАСПОЛОЖЕНИЕ
ГЛУБОКИЙ	И	36	100100	39:	БЫТЬ
ЭО	Р	30	011110	40:	МУН
РН	ТО	32	100000	41:	РНО
OT	#	34	100010			# останавливает алгоритм; отправить последовательность действий
		0	000000			и стоп-код

Некодированная длина = 25 символов × 5 бит/символ = 125 бит.

Длина кодирования = (6 кодов × 5 бит/код) + (11 кодов × 6 бит/код) = 96 бит.

Использование LZW позволило сэкономить 29 бит из 125, уменьшив размер сообщения более чем на 23%. Если бы сообщение было длиннее, то слова словаря начали бы представлять все более длинные фрагменты текста, очень компактно отправляя повторяющиеся слова.

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

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

Вход		Выходная последовательность	Новая запись в словаре				Комментарии
Биты	Код		Полный		Гипотеза
10100	20	Т			27:	Т?
01111	15	ТО	27:	К	28:	ТЕМ?
00010	2	Б	28:	OB	29:	Б?
00101	5	И	29:	БЫТЬ	30:	И?
01111	15	ТО	30:	ЭО	31:	ТЕМ?
10010	18	Р	31:	ИЛИ	32:	Р?	создал код 31 (последний умещается в 5 бит)
001110	14	Н	32:	РН	33:	Н?	поэтому начните читать входные данные с 6 бит
001111	15	ТО	33:	НЕТ	34:	ТЕМ?
010100	20	Т	34:	OT	35:	Т?
011011	27	К	35:	ТТ	36:	К?
011101	29	БЫТЬ	36:	ГЛУБОКИЙ	37:	БЫТЬ?	36 = ТО + 1-й символ (В)
011111	31	ИЛИ	37:	ЖИТЬ	38:	ИЛИ?	получена следующая кодированная последовательность (BE)
100100	36	ГЛУБОКИЙ	38:	РАСПОЛОЖЕНИЕ	39:	ГЛУБОКИЙ?
011110	30	ЭО	39:	БЫТЬ	40:	ТАМ?
100000	32	РН	40:	МУН	41:	РН?
100010	34	OT	41:	РНО	42:	OT?
000000	0	#

На каждом этапе декодер получает код X; он ищет X в таблице и выводит последовательность χ, которую он кодирует, и предполагает, что χ + ? в качестве записи, которую только что добавил кодер – потому что кодер выдал X для χ именно потому, что χ + ? не было в таблице, и кодировщик добавляет его. Но что это за пропущенная буква? Это первая буква в последовательности, кодируемой следующим кодом Z, которую получает декодер. Итак, декодер ищет Z, декодирует его в последовательность ω, берет первую букву z и прикрепляет ее к концу χ в качестве следующей словарной статьи.

Это работает до тех пор, пока полученные коды находятся в словаре декодера, чтобы их можно было декодировать в последовательности. Что произойдет, если декодер получит код Z, которого еще нет в его словаре? Поскольку декодер всегда отстает от кодера всего на один код, Z может находиться в словаре кодера только в том случае, если кодер только что сгенерировал его при отправке предыдущего кода X для χ. Таким образом, Z кодирует некоторый ω, равный χ + ?, и декодер может определить неизвестный символ следующим образом:

1. Декодер видит X, а затем Z, где X кодирует последовательность χ, а Z кодирует некоторую неизвестную последовательность ω.
2. Декодер знает, что кодер только что добавил Z как код для χ + некоторый неизвестный символ c , поэтому ω = χ + c .
3. Поскольку c — первый символ во входном потоке после χ и поскольку ω — строка, появляющаяся сразу после χ, c должен быть первым символом последовательности ω.
4. Поскольку χ является начальной подстрокой ω, c также должен быть первым символом χ.
5. Таким образом, даже если код Z отсутствует в таблице, декодер может вывести неизвестную последовательность и добавляет χ + (первый символ χ) в таблицу как значение Z.

Эта ситуация возникает всякий раз, когда кодер встречает ввод в форме cScSc , где c — один символ, S — строка, а cS уже есть в словаре, а cSc — нет. Кодер генерирует код для cS новый код для cSc , помещая в словарь . Затем он видит cSc на входе (начиная со второго c в cScSc ) и выдает новый только что вставленный код. Приведенный выше аргумент показывает, что всякий раз, когда декодер получает код, которого нет в его словаре, ситуация должна выглядеть следующим образом.

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

Дальнейшее кодирование

Простая схема, описанная выше, фокусируется на самом алгоритме LZW. Многие приложения применяют дальнейшее кодирование последовательности выходных символов. Некоторые упаковывают закодированный поток в виде печатных символов, используя некоторую форму кодирования двоичного кода в текст ; это увеличивает длину кодирования и снижает степень сжатия. И наоборот, повышенного сжатия часто можно достичь с помощью адаптивного энтропийного кодера . Такой кодер оценивает распределение вероятностей значения следующего символа на основе наблюдаемых на данный момент частот значений. Стандартное энтропийное кодирование, такое как кодирование Хаффмана или арифметическое кодирование, затем использует более короткие коды для значений с более высокими вероятностями.

Использование

LZW-сжатие стало первым широко используемым универсальным методом сжатия данных на компьютерах. Большой текстовый файл на английском языке обычно можно сжать с помощью LZW примерно до половины его исходного размера.

LZW использовался в общедоступной программе compress , которая стала более или менее стандартной утилитой в системах Unix примерно в 1986 году. С тех пор она исчезла из многих дистрибутивов, как потому, что нарушала патент LZW, так и потому, что gzip обеспечивал лучшие степени сжатия с использованием LZ77. -основанный на алгоритме DEFLATE , но по крайней мере с 2008 года FreeBSD включает как сжатие , так и распаковку как часть дистрибутива. Несколько других популярных утилит сжатия также использовали LZW или близкие ему методы.

LZW стал очень широко использоваться, когда в 1987 году он стал частью формата изображений GIF. Его также можно (необязательно) использовать в TIFF и PDF файлах . (Хотя LZW доступен в программном обеспечении Adobe Acrobat , Acrobat по умолчанию использует DEFLATE для большинства текстовых данных и данных изображений на основе таблиц цветов в файлах PDF.)

Патенты

Основная статья: Формат обмена графикой § Защита патентов Unisys и LZW

различные патенты и других странах на LZW и подобные алгоритмы выданы В США . LZ78 был защищен патентом США № 4 464 650, выданным Лемпелем, Зивом, Коном и Истманом, переданным Sperry Corporation , позже Unisys Corporation, поданным 10 августа 1981 года. На алгоритм LZW были выданы два патента США: патент США 4 814 746 Виктора С. Миллером и Марком Н. Вегманом и передан IBM , первоначально поданный 1 июня 1983 года, и патент США 4,558,302 Уэлча, переданный Sperry Corporation, позже Unisys Corporation, поданный 20 июня 1983 года.

В дополнение к вышеупомянутым патентам, патент Уэлча 1983 года также включает ссылки на несколько других патентов, оказавших на него влияние, в том числе два японских патента 1980 года ( JP9343880A и JP17790880A ) от Джуна Канацу из NEC , патент США 4021782 (1974) от Джона С. Хернинга, Патент США 4366551 (1977 г.) от Клауса Э. Хольца и патент Германии 1981 г. ( DE19813118676 ) от Карла Экхарта Хайнца.

В 1993–1994 годах и снова в 1999 году корпорация Unisys получила широкое осуждение, когда попыталась ввести лицензионные сборы за LZW в изображениях GIF. Споры между Unisys и CompuServe в 1993–1994 годах ( CompuServe был создателем формата GIF) вызвали в Usenet обсуждение comp.graphics « Мысли о формате файла, заменяющего GIF» , что, в свою очередь, способствовало обмену электронной почтой, который в конечном итоге завершился созданием патента. -неограниченный формат файла Portable Network Graphics (PNG) в 1995 году.

Срок действия патента Unisys в США на алгоритм LZW истек 20 июня 2003 г. Спустя 20 лет после подачи заявления. Срок действия патентов, поданных в Великобритании, Франции, Германии, Италии, Японии и Канаде, истек в 2004 году. аналогично и через 20 лет после их подачи.

Варианты

• LZMW (1985, В. Миллер, М. Вегман) – Ищет во входных данных самую длинную строку, уже находящуюся в словаре («текущее» совпадение); добавляет в словарь объединение предыдущего совпадения с текущим совпадением. (Таким образом, словарные статьи растут быстрее; но эту схему гораздо сложнее реализовать.) Миллер и Вегман также предлагают удалять из словаря низкочастотные статьи, когда словарь заполняется.
• LZAP (1988, Джеймс Сторер) – модификация LZMW: вместо добавления в словарь только объединения предыдущего совпадения с текущим совпадением, добавьте объединения предыдущего совпадения с каждой начальной подстрокой текущего совпадения («AP» означает «все префиксы»). Например, если предыдущее совпадение — «вики», а текущее — «педия», то кодер LZAP добавляет в словарь 5 новых последовательностей: «викип», «википе», «википед», «википеди» и «википедия». ", где кодер LZMW добавляет только одну последовательность "википедия". Это устраняет некоторую сложность LZMW за счет добавления большего количества словарных статей.
• LZWL — это слоговый вариант LZW.

См. также

• LZ77 и LZ78
• ЛЗМА
• Лемпель–Зив–Сторер–Шимански
• ЛЗЖБ
• Вес контекстного дерева
• Дискретное косинусное преобразование (DCT), алгоритм сжатия с потерями, используемый в JPEG и MPEG. стандартах кодирования

Внешние ссылки

• Вики Rosettacode, алгоритм на разных языках
• Патент США 4558302 , Терри А. Уэлч, Устройство и способ высокоскоростного сжатия и декомпрессии данных.
• SharpLZW — реализация C# с открытым исходным кодом
• MIT OpenCourseWare: лекция, включая алгоритм LZW
• Марк Нельсон, Сжатие данных LZW в журнале доктора Доббса (1 октября 1989 г.)
• Сжать, уменьшить и взорвать: устаревшие методы сжатия Zip объясняют LZW и то, как он использовался в PKZIP.