Алгоритм сжатия данных без потерь Lempel–Ziv–Welch (LZW)

Введение

Универсальный алгоритм сжатия данных без потерь

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

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

Если используются коды переменной ширины, кодировщик и декодировщик должны быть внимательны, чтобы изменять ширину в одних и тех же позициях в закодированных данных, чтобы избежать расхождения в границах между отдельными кодами в потоке. В стандартной версии кодировщик увеличивает ширину с p до p + 1, когда встречается последовательность ω + s, отсутствующая в таблице (что требует добавления для неё кода), но следующий доступный код в таблице равен 2p (первый код, требующий p + 1 бит). Кодировщик выдаёт код для ω с шириной p (поскольку этот код не требует p + 1 бит), а затем увеличивает ширину кода, чтобы следующий выдаваемый код имел ширину p + 1 бит. Декодировщик всегда на один код отстаёт от кодировщика в построении таблицы, поэтому, увидев код для ω, он генерирует запись для кода 2p - 1. Поскольку это точка, в которой кодировщик увеличивает ширину кода, декодировщик также должен увеличить ширину здесь – в точке генерации наибольшего кода, помещающегося в p бит. К сожалению, некоторые ранние реализации алгоритма кодирования сначала увеличивают ширину кода, а затем выдают ω с новой шириной вместо старой, из-за чего декодировщику кажется, что ширина изменилась на один код слишком рано. Это называется «ранним изменением»; оно вызвало столько путаницы, что Adobe теперь допускает обе версии в PDF-файлах, но включает явный флаг в заголовке каждого LZW-сжатого потока, указывающий, используется ли раннее изменение. Среди графических форматов файлов, поддерживающих сжатие LZW, TIFF использует раннее изменение, а GIF и большинство других – нет. Когда таблица очищается в ответ на код очистки, как кодировщик, так и декодировщик изменяют ширину кода после кода очистки обратно к исходной ширине кода, начиная с кода, непосредственно следующего за кодом очистки.

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

Поскольку генерируемые коды обычно не выравниваются по границам байтов, кодировщик и декодировщик должны согласовать способ упаковки кодов в байты. Существует два распространенных метода: LSB first ("начиная с младшего бита") и MSB first ("начиная со старшего бита"). При упаковке LSB first первый код выравнивается таким образом, чтобы младший бит кода соответствовал младшему биту первого байта потока, а если код содержит более 8 бит, то старшие биты выравниваются с младшими битами следующего байта; последующие коды упаковываются так, что младший бит помещается в наименее значимый бит, еще не использованный в текущем байте потока, и при необходимости переносятся в последующие байты. При упаковке MSB first первый код выравнивается таким образом, чтобы его старший бит соответствовал старшему биту первого байта потока, а переполнение выравнивается со старшим битом следующего байта; последующие коды записываются так, что старший бит помещается в наиболее значимый бит, еще не использованный в текущем байте потока. Файлы GIF используют порядок упаковки LSB first. Файлы TIFF и PDF используют порядок упаковки MSB first.

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

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

Применение

LZW-сжатие стало первым широко используемым универсальным методом сжатия данных на компьютерах. Большой английский текстовый файл обычно можно сжать с помощью LZW примерно до половины своего первоначального размера. LZW использовался в общедоступной программе compress, которая стала более или менее стандартной утилитой в системах Unix примерно в 1986 году. С тех пор она исчезла из многих дистрибутивов, как из-за нарушения патента LZW, так и потому, что gzip обеспечивал лучшие коэффициенты сжатия, используя алгоритм DEFLATE на основе LZ77. Однако по состоянию на 2008 год, по крайней мере, FreeBSD включает в себя как compress, так и uncompress в состав дистрибутива. Ряд других популярных утилит сжатия также использовали LZW или близкие к нему методы. LZW получил широкое распространение, когда в 1987 году стал частью формата изображений GIF. Он также может (опционально) использоваться в файлах TIFF и PDF. (Хотя LZW доступен в программном обеспечении Adobe Acrobat, Acrobat по умолчанию использует DEFLATE для большинства текстовых данных и изображений, основанных на цветовых таблицах, в PDF-файлах.)

Патенты

В США и других странах были выданы различные патенты на LZW и аналогичные алгоритмы. LZ78 был запатентован Lempel, Ziv, Cohn и Eastman, переданный компании Sperry Corporation, позже Unisys Corporation, заявка подана 10 августа 1981 года. Два патента США были выданы на алгоритм LZW: Виктору С. Миллеру и Марку Н. Вегману, переданные компании IBM, первоначально заявленные 1 июня 1983 года, и Уэлчу, переданные компании Sperry Corporation, позже Unisys Corporation, заявленные 20 июня 1983 года. Помимо вышеуказанных патентов, патент Уэлча 1983 года также содержит ссылки на несколько других патентов, которые на него повлияли, включая два японских патента 1980 года (JP9343880A и JP17790880A) от Джун Канацу из NEC, (1974) от Джона С. Хоернинга, (1977) от Клауса Э. Холца и немецкий патент 1981 года (DE19813118676) от Карла Экхарта Хайнца. В 1993–1994 и снова в 1999 году компания Unisys Corporation подверглась широкой критике, когда попыталась взимать лицензионные сборы за LZW в GIF-изображениях. Споры Unisys CompuServe 1993–1994 годов (CompuServe являлся создателем формата GIF) вызвали обсуждение в Usenet comp.graphics на тему "Размышления о замене формата файла GIF", что, в свою очередь, привело к переписке по электронной почте, которая в конечном итоге привела к созданию формата файла Portable Network Graphics (PNG), свободного от патентных ограничений, в 1995 году. Патент Unisys на алгоритм LZW истек 20 июня 2003 года, через 20 лет после подачи заявки. Патенты, поданные в Соединенном Королевстве, Франции, Германии, Италии, Японии и Канаде, истекли в 2004 году. – Поиск входных данных для самой длинной строки, уже содержащейся в словаре (текущее соответствие); добавление конкатенации предыдущего соответствия с текущим соответствием в словарь. (Таким образом, записи в словаре растут быстрее, но эта схема гораздо сложнее в реализации.) Миллер и Вегман также предлагают удалять из словаря записи с низкой частотой при его заполнении. LZAP (1988, Джеймс Сторер) – модификация LZMW: вместо добавления в словарь только конкатенации предыдущего соответствия с текущим соответствием, добавляются конкатенации предыдущего соответствия с каждой начальной подстрокой текущего соответствия ("AP" означает "все префиксы"). Например, если предыдущее соответствие – "wiki", а текущее соответствие – "pedia", то кодировщик LZAP добавляет 5 новых последовательностей в словарь: "wikip", "wikipe", "wikiped", "wikipedi" и "wikipedia", в то время как кодировщик LZMW добавляет только одну последовательность "wikipedia". Это устраняет некоторую сложность LZMW, но за счет увеличения количества словарных записей. LZWL – вариант LZW, основанный на слогах.

Various patents have been issued in the United States and other countries for LZW and similar algorithms. LZ78 was covered by by Lempel, Ziv, Cohn, and Eastman, assigned to Sperry Corporation, later Unisys Corporation, filed on August 10, 1981. Two US patents were issued for the LZW algorithm: by Victor S. Miller and Mark N. Wegman and assigned to IBM, originally filed on June 1, 1983, and by Welch, assigned to Sperry Corporation, later Unisys Corporation, filed on June 20, 1983. In addition to the above patents, Welch's 1983 patent also includes citations to several other patents that influenced it, including two 1980 Japanese patents (JP9343880A and JP17790880A) from NEC's Jun Kanatsu, (1974) from John S. Hoerning, (1977) from Klaus E. Holtz, and a 1981 German patent (DE19813118676) from Karl Eckhart Heinz. In 1993–94, and again in 1999, Unisys Corporation received widespread condemnation when it attempted to enforce licensing fees for LZW in GIF images. The 1993–1994 Unisys CompuServe controversy (CompuServe being the creator of the GIF format) prompted a Usenet comp. graphics discussion Thoughts on a GIF replacement file format, which in turn fostered an email exchange that eventually culminated in the creation of the patent unencumbered Portable Network Graphics (PNG) file format in 1995. Unisys's US patent on the LZW algorithm expired on June 20, 2003, 20 years after it had been filed. Patents that had been filed in the United Kingdom, France, Germany, Italy, Japan and Canada all expired in 2004, – Searches input for the longest string already in the dictionary (the "current" match); adds the concatenation of the previous match with the current match to the dictionary. (Dictionary entries thus grow more rapidly; but this scheme is much more complicated to implement.) Miller and Wegman also suggest deleting low frequency entries from the dictionary when the dictionary fills up. LZAP (1988, by James Storer) – modification of LZMW: instead of adding just the concatenation of the previous match with the current match to the dictionary, add the concatenations of the previous match with each initial substring of the current match ("AP" stands for "all prefixes"). For example, if the previous match is "wiki" and current match is "pedia", then the LZAP encoder adds 5 new sequences to the dictionary: "wikip", "wikipe", "wikiped", "wikipedi", and "wikipedia", where the LZMW encoder adds only the one sequence "wikipedia". This eliminates some of the complexity of LZMW, at the price of adding more dictionary entries. LZWL is a syllable based variant of LZW.