Lempel–Ziv–Welch ( LZW ) — универсальный алгоритм сжатия данных без потерь, созданный Авраамом Лемпелем , Джейкобом Зивом и Терри Уэлчем . Он был опубликован Уэлчем в 1984 году как улучшенная реализация алгоритма LZ78 , опубликованного Лемпелем и Зивом в 1978 году. Алгоритм прост в реализации и имеет потенциал для очень высокой пропускной способности в аппаратных реализациях. [1] Это алгоритм утилиты сжатия файлов Unix compress , используемый в формате изображений GIF .
Сценарий, описанный в статье Уэлча 1984 года [1], кодирует последовательности 8-битных данных как 12-битные коды фиксированной длины. Коды от 0 до 255 представляют собой 1-символьные последовательности, состоящие из соответствующего 8-битного символа, а коды от 256 до 4095 создаются в словаре для последовательностей, встречающихся в данных по мере их кодирования. На каждом этапе сжатия входные байты собираются в последовательность до тех пор, пока следующий символ не создаст последовательность без кода в словаре. Код для последовательности (без этого символа) добавляется к выходу, а новый код (для последовательности с этим символом) добавляется в словарь.
Идея была быстро адаптирована к другим ситуациям. Например, в изображении, основанном на таблице цветов, естественный алфавит символов представляет собой набор индексов таблицы цветов, и в 1980-х годах многие изображения имели небольшие таблицы цветов (порядка 16 цветов). Для такого сокращенного алфавита полные 12-битные коды давали плохое сжатие, если изображение не было большим, поэтому была введена идея кода переменной ширины : коды обычно начинаются на один бит шире кодируемых символов, и по мере того, как каждый размер кода израсходован, ширина кода увеличивается на 1 бит, до некоторого предписанного максимума (обычно 12 бит). Когда достигается максимальное значение кода, кодирование продолжается с использованием существующей таблицы, но новые коды для добавления в таблицу не генерируются.
Дальнейшие усовершенствования включают резервирование кода для указания того, что кодовую таблицу следует очистить и восстановить в исходное состояние («код очистки», обычно первое значение сразу после значений для отдельных символов алфавита), и кода для указания конца данных («код остановки», обычно на единицу больше кода очистки). Код очистки позволяет повторно инициализировать таблицу после ее заполнения, что позволяет кодированию адаптироваться к изменяющимся шаблонам во входных данных. Интеллектуальные кодировщики могут отслеживать эффективность сжатия и очищать таблицу всякий раз, когда существующая таблица больше не соответствует входным данным.
Поскольку коды добавляются способом, определяемым данными, декодер имитирует построение таблицы, поскольку он видит полученные коды. Крайне важно, чтобы кодер и декодер согласовали разнообразие используемых LZW: размер алфавита, максимальный размер таблицы (и ширину кода), используется ли кодирование переменной ширины, начальный размер кода и следует ли использовать коды очистки и остановки (и какие значения они имеют). Большинство форматов, использующих LZW, встраивают эту информацию в спецификацию формата или предоставляют для них явные поля в заголовке сжатия данных.
Здесь показан высокоуровневый вид алгоритма кодирования:
Словарь инициализируется так, чтобы содержать односимвольные строки, соответствующие всем возможным входным символам (и ничего больше, кроме кодов очистки и остановки, если они используются). Алгоритм работает, сканируя входную строку на предмет последовательно более длинных подстрок, пока не найдет ту, которой нет в словаре. Когда такая строка найдена, индекс для строки без последнего символа (т. е. самая длинная подстрока, которая есть в словаре) извлекается из словаря и отправляется на вывод, а новая строка (включая последний символ) добавляется в словарь со следующим доступным кодом. Последний входной символ затем используется в качестве следующей начальной точки для сканирования подстрок.
Таким образом, последовательно более длинные строки регистрируются в словаре и доступны для последующего кодирования в качестве отдельных выходных значений. Алгоритм лучше всего работает с данными с повторяющимися шаблонами, поэтому начальные части сообщения сжимаются незначительно. Однако по мере роста сообщения коэффициент сжатия асимптотически стремится к максимуму (т. е. коэффициент сжатия или коэффициент улучшаются по возрастающей кривой, а не линейно, приближаясь к теоретическому максимуму в течение ограниченного периода времени, а не в течение бесконечного времени). [2]
Здесь показан высокоуровневый вид алгоритма декодирования:
Алгоритм декодирования работает путем считывания значения из закодированного ввода и вывода соответствующей строки из словаря. Однако полный словарь не нужен, нужен только начальный словарь, содержащий односимвольные строки (и который обычно жестко закодирован в программе, а не отправляется с закодированными данными). Вместо этого полный словарь перестраивается в процессе декодирования следующим образом: после декодирования значения и вывода строки декодер объединяет его с первым символом следующей декодированной строки (или первым символом текущей строки, если следующую невозможно декодировать; поскольку если следующее значение неизвестно, то это должно быть значение, добавленное в словарь в этой итерации, и поэтому его первый символ совпадает с первым символом текущей строки), и обновляет словарь новой строкой. Затем декодер переходит к следующему вводу (который уже был прочитан в предыдущей итерации) и обрабатывает его, как и раньше, и так далее, пока не исчерпает входной поток.
Если используются коды переменной ширины, кодер и декодер должны быть осторожны, чтобы изменить ширину в тех же точках в закодированных данных, чтобы они не расходились на границах между отдельными кодами в потоке. В стандартной версии кодер увеличивает ширину с p до p + 1, когда встречается последовательность ω + s , которой нет в таблице (так что для нее должен быть добавлен код), но следующий доступный код в таблице — 2 p (первый код, требующий p + 1 бит). Кодер выдает код для ω шириной p (так как этот код не требует p + 1 бит), а затем увеличивает ширину кода так, чтобы следующий выданный код имел ширину p + 1 бит.
Декодер всегда отстает на один код от кодера при построении таблицы, поэтому, когда он видит код для ω, он генерирует запись для кода 2 p − 1. Поскольку это точка, в которой кодер увеличивает ширину кода, декодер должен увеличить ширину и здесь — в точке, в которой он генерирует наибольший код, умещающийся в p бит.
К сожалению, некоторые ранние реализации алгоритма кодирования увеличивают ширину кода, а затем выдают ω с новой шириной вместо старой, так что для декодера это выглядит так, как будто ширина изменяет один код раньше. Это называется «ранним изменением»; это вызвало столько путаницы, что Adobe теперь допускает обе версии в файлах PDF, но включает явный флаг в заголовок каждого потока, сжатого LZW, чтобы указать, используется ли раннее изменение. Из графических форматов файлов, которые поддерживают сжатие LZW, TIFF использует раннее изменение, в то время как GIF и большинство других — нет.
Когда таблица очищается в ответ на код очистки, и кодер, и декодер изменяют ширину кода после кода очистки обратно на исходную ширину кода, начиная с кода, следующего сразу за кодом очистки.
Поскольку выдаваемые коды обычно не попадают на границы байтов, кодер и декодер должны договориться о том, как коды упаковываются в байты. Два распространенных метода — LSB-first (« сначала младший бит ») и MSB-first (« сначала старший бит »). При упаковке LSB-first первый код выравнивается так, что младший бит кода попадает в младший бит первого байта потока, и если код имеет более 8 бит, оставшиеся старшие биты выравниваются с младшими битами следующего байта; дальнейшие коды упаковываются так, что LSB переходит в младший бит, еще не использованный в текущем байте потока, переходя в дальнейшие байты по мере необходимости. Упаковка MSB-first выравнивает первый код так, что его старший бит попадает в MSB первого байта потока, с переполнением, выравниваемым с MSB следующего байта; дальнейшие коды записываются так, что MSB переходит в старший бит, еще не использованный в текущем байте потока.
В файлах GIF используется порядок упаковки LSB-first. В файлах TIFF и PDF используется порядок упаковки MSB-first.
Следующий пример иллюстрирует алгоритм LZW в действии, показывая статус вывода и словаря на каждом этапе, как при кодировании, так и при декодировании данных. Этот пример был построен для обеспечения разумного сжатия очень короткого сообщения. В реальных текстовых данных повторение, как правило, менее выражено, поэтому обычно необходимы более длинные входные потоки, прежде чем сжатие наберет эффективность.
Открытый текст, который необходимо закодировать (из алфавита, использующего только заглавные буквы), выглядит следующим образом:
БЫТЬИЛИНЕБЫТЬБЫТЬНЕ#
В алфавите открытого текста 26 символов (заглавные буквы от A до Z ). # используется для представления стоп-кода: кода вне алфавита открытого текста, который запускает специальную обработку. Мы произвольно назначаем им значения от 1 до 26 для букв и 0 для стоп-кода '#'. (Большинство разновидностей LZW помещают стоп-код после алфавита данных, но ничто в базовом алгоритме не требует этого. Кодер и декодер должны только согласовать, какое значение он имеет.)
Компьютер отображает их как строки битов . Для получения достаточных комбинаций, охватывающих этот набор из 27 значений, необходимы пятибитные коды. Словарь инициализируется этими 27 значениями. По мере роста словаря коды должны увеличиваться в ширине, чтобы вместить дополнительные записи. 5-битный код дает 2 5 = 32 возможных комбинаций битов, поэтому при создании 33-го слова словаря алгоритм должен в этой точке переключиться с 5-битных строк на 6-битные (для всех кодовых значений, включая те, которые ранее выводились только с пятью битами). Обратите внимание, что поскольку используется нулевой код 00000, помеченный как «0», 33-я запись словаря помечена как 32. (Ранее сгенерированный вывод не затрагивается изменением ширины кода, но как только в словаре генерируется 6-битное значение, оно, вероятно, может быть следующим выданным кодом, поэтому ширина для последующего вывода смещается до 6 бит, чтобы это учесть.)
Итак, первоначальный словарь состоит из следующих записей:
Буферизация входных символов в последовательности ω до тех пор, пока ω + следующий символ не будет в словаре. Выдать код для ω и добавить ω + следующий символ в словарь. Начать буферизацию снова со следующего символа. (Строка для кодирования — "TOBEORNOTTOBEORTOBEORNOT#".)
Использование LZW сэкономило 29 бит из 125, сократив сообщение более чем на 23%. Если бы сообщение было длиннее, то слова словаря начали бы представлять все более длинные разделы текста, отправляя повторяющиеся слова очень компактно.
Чтобы расшифровать архив, сжатый с помощью LZW, необходимо заранее знать исходный используемый словарь, но дополнительные записи можно реконструировать, поскольку они всегда являются просто конкатенацией предыдущих записей.
На каждом этапе декодер получает код X; он ищет X в таблице и выводит последовательность χ, которую он кодирует, и предполагает, что χ + ? является записью, которую только что добавил кодер, — потому что кодер выдал X для χ именно потому, что χ + ? не было в таблице, и кодер идет дальше и добавляет ее. Но какая буква отсутствует? Это первая буква в последовательности, закодированной следующим кодом Z, которую получает декодер. Поэтому декодер ищет Z, декодирует ее в последовательность ω и берет первую букву z и добавляет ее в конец χ в качестве следующей записи словаря.
Это работает до тех пор, пока полученные коды находятся в словаре декодера, так что их можно декодировать в последовательности. Что произойдет, если декодер получит код Z, которого еще нет в его словаре? Поскольку декодер всегда находится всего на один код позади кодера, Z может быть в словаре кодера, только если кодер только что сгенерировал его, когда выдавал предыдущий код X для χ. Таким образом, Z кодирует некоторое ω, которое равно χ + ?, и декодер может определить неизвестный символ следующим образом:
Такая ситуация возникает всякий раз, когда кодер сталкивается с вводом формы cScSc , где c — один символ, S — строка, а cS уже есть в словаре, а cSc — нет. Кодер выдает код для cS , помещая новый код для cSc в словарь. Затем он видит cSc во вводе (начиная со второго c из cScSc ) и выдает новый код, который он только что вставил. Приведенный выше аргумент показывает, что всякий раз, когда декодер получает код, которого нет в его словаре, ситуация должна выглядеть следующим образом.
Хотя ввод формы cScSc может показаться маловероятным, этот шаблон довольно распространен, когда входной поток характеризуется значительным повторением. В частности, длинные строки из одного символа (которые обычны в типах изображений, для кодирования которых часто используется LZW) многократно генерируют шаблоны такого рода.
Простая схема, описанная выше, фокусируется на самом алгоритме LZW. Многие приложения применяют дальнейшее кодирование к последовательности выходных символов. Некоторые упаковывают кодированный поток как печатные символы, используя некоторую форму двоично-текстового кодирования ; это увеличивает кодированную длину и уменьшает степень сжатия. И наоборот, повышенное сжатие часто может быть достигнуто с помощью адаптивного энтропийного кодера . Такой кодер оценивает распределение вероятностей для значения следующего символа на основе наблюдаемых частот значений до сих пор. Стандартное энтропийное кодирование, такое как кодирование Хаффмана или арифметическое кодирование, затем использует более короткие коды для значений с более высокими вероятностями.
Сжатие LZW стало первым широко используемым универсальным методом сжатия данных на компьютерах. Большой английский текстовый файл обычно можно сжать с помощью LZW примерно до половины его исходного размера.
LZW использовался в общедоступной программе compress , которая стала более или менее стандартной утилитой в системах Unix около 1986 года. С тех пор она исчезла из многих дистрибутивов, как потому, что нарушала патент LZW, так и потому, что gzip обеспечивал лучшие коэффициенты сжатия с использованием алгоритма DEFLATE на основе LZ77 , но по крайней мере с 2008 года FreeBSD включает в себя как compress , так и uncompress как часть дистрибутива. Несколько других популярных утилит сжатия также использовали LZW или тесно связанные методы.
LZW стал очень широко использоваться, когда он стал частью формата изображений GIF в 1987 году. Он также может (опционально) использоваться в файлах TIFF и PDF . (Хотя LZW доступен в программном обеспечении Adobe Acrobat , Acrobat по умолчанию использует DEFLATE для большинства текстовых и основанных на таблицах цветов данных изображений в файлах PDF.)
В Соединенных Штатах и других странах были выданы различные патенты на LZW и аналогичные алгоритмы. LZ78 был защищен патентом США 4,464,650 , выданным Lempel, Ziv, Cohn и Eastman, переданным Sperry Corporation , позже Unisys Corporation, поданным 10 августа 1981 года. Для алгоритма LZW были выданы два патента США: патент США 4,814,746, выданный Victor S. Miller и Mark N. Wegman и переданный IBM , первоначально поданным 1 июня 1983 года, и патент США 4,558,302 , выданный Welch, переданный Sperry Corporation, позже Unisys Corporation, поданным 20 июня 1983 года.
В дополнение к вышеуказанным патентам патент Уэлча 1983 года также включает ссылки на несколько других патентов, которые повлияли на него, включая два японских патента 1980 года (JP9343880A и JP17790880A) от Джуна Канацу из NEC , патент США 4,021,782 (1974) от Джона С. Хорнинга, патент США 4,366,551 (1977) от Клауса Э. Хольца и немецкий патент 1981 года (DE19813118676) от Карла Экхарта Хайнца. [3]
В 1993–94 и снова в 1999 году корпорация Unisys подверглась всеобщему осуждению, когда попыталась ввести лицензионные сборы за LZW в изображениях GIF. Спор между Unisys и CompuServe в 1993–1994 годах ( CompuServe был создателем формата GIF) спровоцировал обсуждение в Usenet comp.graphics Thoughts on a GIF-replacement file format , что, в свою очередь, способствовало обмену электронными письмами, который в конечном итоге привел к созданию в 1995 году формата файла Portable Network Graphics (PNG), не обремененного патентами.
Патент США Unisys на алгоритм LZW истек 20 июня 2003 года [4] , спустя 20 лет после подачи заявки. Патенты, поданные в Великобритании, Франции, Германии, Италии, Японии и Канаде, истекли в 2004 году [4] , также спустя 20 лет после подачи заявки.