Войти
Лемпель – Зив – Велч (LZW ) - это универсальный алгоритм сжатия данных без потерь , созданный Абрахамом Лемпелем, Джейкобом Зивом и Терри Велчем. Он был опубликован Уэлчем в 1984 году как улучшенная реализация алгоритма LZ78, опубликованного Лемпелем и Зивом в 1978 году. Алгоритм прост в реализации и имеет потенциал для очень высокой пропускной способности в аппаратных реализациях. Это алгоритм широко используемой утилиты сжатия файлов Unix compress и используется в формате изображения GIF.
Сценарий, описанный В статье Уэлча 1984 года последовательности 8-битных данных кодируются как 12-битные коды фиксированной длины. Коды от 0 до 255 представляют собой 1-символьные последовательности, состоящие из соответствующего 8-битного символа, а коды с 256 по 4095 создаются в словаре для последовательностей, встречающихся в данных по мере их кодирования. На каждом этапе сжатия входные байты собираются в последовательность до тех пор, пока следующий символ не составит последовательность без кода в словаре. Код для последовательности (без этого символа) добавляется к выходным данным, а новый код (для последовательности с этим символом) добавляется в словарь.
Идея была быстро адаптирована к другим ситуациям. Например, в изображении, основанном на таблице цветов, естественный алфавит символов представляет собой набор индексов таблицы цветов, а в 1980-х годах многие изображения имели небольшие таблицы цветов (порядка 16 цветов). Для такого сокращенного алфавита полные 12-битные коды давали плохое сжатие, если изображение не было большим, поэтому была введена идея кода переменной ширины : коды обычно начинаются на один бит шире, чем кодируемые символы, и по мере использования каждого размера кода ширина кода увеличивается на 1 бит до некоторого предписанного максимума (обычно 12 бит). Когда достигается максимальное значение кода, кодирование продолжается с использованием существующей таблицы, но новые коды не генерируются для добавления в таблицу.
Дальнейшие уточнения включают в себя резервирование кода, чтобы указать, что кодовая таблица должна быть очищена и восстановлена до исходного состояния («чистый код», обычно первое значение сразу после значений для отдельных букв алфавита) и код для обозначения конца данных («код остановки», обычно на единицу больше, чем код очистки). Чистый код позволяет повторно инициализировать таблицу после ее заполнения, что позволяет кодировке адаптироваться к изменяющимся шаблонам во входных данных. Интеллектуальные кодировщики могут отслеживать эффективность сжатия и очищать таблицу всякий раз, когда существующая таблица больше не соответствует входным данным.
Поскольку коды добавляются способом, определяемым данными, декодер имитирует построение таблицы, поскольку он видит результирующие коды. Очень важно, чтобы кодировщик и декодер согласовали разнообразие используемых LZW: размер алфавита, максимальный размер таблицы (и ширину кода), использование кодирования с переменной шириной, начальный размер кода и необходимость использования открытого и коды останова (и какие значения они имеют). Большинство форматов, использующих LZW, встраивают эту информацию в спецификацию формата или предоставляют явные поля для них в заголовке сжатия для данных.
Здесь показано высокоуровневое представление алгоритма кодирования:
Словарь инициализируется для хранения односимвольных строк, соответствующих всем возможным входным символам (и ничего кроме кодов очистки и остановки, если они используются). Алгоритм работает, просматривая входную строку в поисках последовательно более длинных подстрок, пока не найдет ту, которой нет в словаре. Когда такая строка найдена, индекс для строки без последнего символа (т. Е. Самая длинная подстрока в словаре) извлекается из словаря и отправляется на вывод, а новая строка (включая последний символ) добавляется в словарь со следующим доступным кодом. Последний входной символ затем используется как следующая отправная точка для поиска подстрок.
Таким образом, последовательно более длинные строки регистрируются в словаре и доступны для последующего кодирования как отдельные выходные значения. Алгоритм лучше всего работает с данными с повторяющимися шаблонами, поэтому начальные части сообщения мало сжимаются. Однако по мере роста сообщения степень сжатия стремится асимптотически к максимуму (т. Е. Коэффициент или степень сжатия улучшаются по возрастающей кривой, а не линейно, приближаясь к теоретическому максимуму в течение ограниченного периода времени, а не за бесконечное время).
Алгоритм декодирования работает, считывая значение из закодированного ввода и выводя соответствующую строку из инициализированного словаря. Чтобы перестроить словарь таким же образом, как он был построен во время кодирования, он также получает следующее значение из ввода и добавляет в словарь конкатенацию текущей строки и первый символ строки, полученной с помощью декодирование следующего входного значения или первого символа строки, просто выводимой, если следующее значение не может быть декодировано (если следующее значение неизвестно декодеру, тогда это должно быть значение, добавленное в словарь этой итерации, и поэтому его первый символ должен быть таким же, как первый символ текущей строки, отправляемой на декодированный вывод). Затем декодер переходит к следующему входному значению (которое уже было считано как «следующее значение» на предыдущем проходе) и повторяет процесс до тех пор, пока не будет больше входных данных, после чего окончательное входное значение декодируется без каких-либо дополнительных добавлений. к словарю.
Таким образом, декодер создает словарь, идентичный тому, который используется кодировщиком, и использует его для декодирования последующих входных значений. Таким образом, полный словарь не нужно отправлять с закодированными данными. Достаточно только начального словаря, содержащего односимвольные строки (и обычно он определяется заранее в кодировщике и декодере, а не отправляется явно с закодированными данными.)
Если используются коды переменной ширины, кодировщик и декодер должны быть осторожны, чтобы изменить ширину в одних и тех же точках закодированных данных, чтобы они не расходились по границам между отдельными кодами в потоке. В стандартной версии кодировщик увеличивает ширину с p до p + 1, когда встречается последовательность ω + s, которой нет в таблице (так что для нее необходимо добавить код), но следующий доступный код в таблице - 2 (первый код, требующий p + 1 бит). Кодер выдает код для ω с шириной p (поскольку этот код не требует p + 1 бит), а затем увеличивает ширину кода, так что следующий испускаемый код имеет ширину p + 1 бит.
Декодер всегда находится на один код позади кодировщика при построении таблицы, поэтому, когда он видит код для ω, он генерирует запись для кода 2-1. Поскольку это точка, в которой кодировщик увеличивает код width, декодер должен увеличить ширину и здесь - в точке, где он генерирует наибольший код, который умещается в 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 в действии, показывая состояние вывода и словарь на каждом этапе, как при кодировании, так и при декодировании данных. Этот пример создан для разумного сжатия очень короткого сообщения. В реальных текстовых данных повторение обычно менее выражено, поэтому обычно требуются более длинные входные потоки, прежде чем сжатие повысит эффективность.
Открытый текст, который должен быть закодирован (из алфавита, использующего только заглавные буквы):
TOBEORNOTTOBEORTOBEORNOT #
# - это маркер, используемый для показать, что конец сообщения достигнут. Таким образом, в алфавите открытого текста 26 символов (26 заглавных букв от A до Z), а символ # представляет собой стоп-код. Мы произвольно присваиваем им значения от 1 до 26 для букв и 0 для '#'. (Большинство разновидностей LZW помещают код остановки после алфавита данных, но ничто в базовом алгоритме этого не требует. Кодировщик и декодер должны только согласовать, какое значение он имеет.)
Компьютер отображает их в виде строк из бит. Пятибитовые коды необходимы, чтобы дать достаточно комбинаций, чтобы охватить этот набор из 27 значений. Словарь инициализируется этими 27 значениями. По мере роста словаря коды должны увеличиваться в ширину, чтобы вместить дополнительные записи. 5-битный код дает 2 = 32 возможных комбинации битов, поэтому, когда создается 33-е словарное слово, алгоритм должен в этот момент переключиться с 5-битных строк на 6-битные строки (для всех значений кода, включая те, которые ранее были выведены всего с пятью битами). Обратите внимание, что, поскольку используется код 00000, состоящий только из нулей, и он помечен как «0», 33-я словарная запись помечена 32 . (На ранее сгенерированный вывод не влияет изменение ширины кода, но после того, как в словаре сгенерировано 6-битное значение, оно, вероятно, может быть следующим испускаемым кодом, поэтому ширина для последующего вывода сдвигается до 6 бит, чтобы учесть это.)
Таким образом, исходный словарь состоит из следующих записей:
| Символ | Двоичный | Десятичный |
|---|---|---|
| # | 00000 | 0 |
| A | 00001 | 1 |
| B | 00010 | 2 |
| C | 00011 | 3 |
| D | 00100 | 4 |
| E | 00101 | 5 |
| F | 00110 | 6 |
| G | 00111 | 7 |
| H | 01000 | 8 |
| I | 01001 | 9 |
| J | 01010 | 10 |
| K | 01011 | 11 |
| L | 01100 | 12 |
| M | 01101 | 13 |
| N | 01110 | 14 |
| O | 01111 | 15 |
| P | 10000 | 16 |
| Q | 10001 | 17 |
| R | 10010 | 18 |
| S | 10011 | 19 |
| T | 10100 | 20 |
| U | 10101 | 21 |
| V | 10110 | 22 |
| W | 10111 | 23 |
| X | 11000 | 24 |
| Y | 11001 | 25 |
| Z | 11010 | 26 |
Буферизировать входные символы в последовательности ω до тех пор, пока ω + следующий символ не окажется в словаре. Выведите код для ω и добавьте следующий символ ω + в словарь. Снова начните буферизацию со следующего символа. (Кодируемая строка - «TOBEORNOTTOBEORTOBEORNOT #».)
| Текущая последовательность | Следующий символ | Вывод | Расширенный словарь | Комментарии | ||
|---|---|---|---|---|---|---|
| Код | Биты | |||||
| NULL | T | |||||
| T | O | 20 | 10100 | 27: | TO | 27 = первый доступный код после 0 по 26 |
| O | B | 15 | 01111 | 28: | OB | |
| B | E | 2 | 00010 | 29: | BE | |
| E | O | 5 | 00101 | 30: | EO | |
| O | R | 15 | 01111 | 31: | OR | |
| R | N | 18 | 10010 | 32: | RN | 32 требует 6 бит, поэтому для следующего вывода используйте 6 бит |
| N | O | 14 | 001110 | 33: | NO | |
| O | T | 15 | 001111 | 34: | OT | |
| T | T | 20 | 010100 | 35: | TT | |
| TO | B | 27 | 011011 | 36: | TOB | |
| BE | O | 29 | 011101 | 37: | BEO | |
| OR | T | 31 | 011111 | 38: | ORT | |
| TOB | E | 36 | 100100 | 39: | TOBE | |
| EO | R | 30 | 011110 | 40: | EOR | |
| RN | O | 32 | 100000 | 41: | RNO | |
| OT | # | 34 | 100010 | # останавливает алгоритм; отправить текущий код | ||
| 0 | 000000 | и стоп-код | ||||
Использование LZW позволило сэкономить 29 бит из 125, уменьшив сообщение более чем на 23%. Если бы сообщение было длиннее, то словарные слова начали бы представлять все более и более длинные участки текста, очень компактно отправляя повторяющиеся слова.
Для декодирования LZW-сжатого архива необходимо заранее знать используемый исходный словарь, но можно восстановить дополнительные записи, поскольку они всегда представляют собой просто конкатенации предыдущих записей.
| Вход | Последовательность вывода | Новая словарная запись | Комментарии | ||||
|---|---|---|---|---|---|---|---|
| Биты | Код | Полный | Гипотеза | ||||
| 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: | ИЛИ | 32: | R? | созданный код 31 (последний умещается в 5 битах) |
| 001110 | 14 | N | 32: | RN | 33: | N? | , поэтому начните чтение ввода с 6 бит |
| 001111 | 15 | O | 33: | NO | 34: | O? | |
| 010100 | 20 | T | 34: | OT | 35: | T? | |
| 011011 | 27 | TO | 35 : | TT | 36: | TO? | |
| 011101 | 29 | BE | 36: | TOB | 37: | БЫТЬ? | 36 = TO + 1-й символ (B) из |
| 011111 | 31 | OR | 37: | BEO | 38: | ИЛИ? | получена следующая кодированная последовательность (BE) |
| 100100 | 36 | TOB | 38: | ORT | 39: | TOB? | |
| 011110 | 30 | EO | 39: | TOBE | 40: | EO? | |
| 100000 | 32 | RN | 40: | EOR | 41: | RN? | |
| 100010 | 34 | OT | 41: | RNO | 42 : | OT? | |
| 000000 | 0 | # | |||||
На каждом этапе декодер принимает код 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 и распаковать как часть распределения. Несколько других популярных утилит сжатия также использовали LZW или близкие к нему методы.
LZW стал очень широко использоваться, когда он стал частью формата изображения GIF в 1987 году. Он также (необязательно) может использоваться в TIFF и PDF. файлов. (Хотя LZW доступен в программном обеспечении Adobe Acrobat, Acrobat по умолчанию использует DEFLATE для большинства текстовых данных и изображений на основе таблиц цветов в файлах PDF.)
Различные патенты были выданы в США и других странах на LZW и подобные алгоритмы. LZ78 был покрыт США. Патент 4464650 Лемпеля, Зива, Кона и Истмана, переуступленный Sperry Corporation, позже Unisys Corporation, подан 10 августа 1981 г. Два патента США были выданы на Алгоритм LZW: США Патент 4814746, выданный Виктором С. Миллером и Марком Н. Вегманом, переуступленный IBM, первоначально подан 1 июня 1983 г. и НАС Патент 4558302 Уэлча, переуступленный Sperry Corporation, позже Unisys Corporation, подан 20 июня 1983 года.
В дополнение к вышеупомянутым патентам патент Уэлча 1983 года также включает ссылки на несколько других патентов, которые повлияли на него., включая два японских патента 1980 г. (JP9343880A и JP17790880A ) от Jun Kanatsu, NEC, США Патент 4021782 (1974) от Джона С. Хёрнинга, США. Патент 4366551 (1977) от Клауса Э. Хольца и немецкий патент 1981 года (DE19813118676 ) от Карла Экхарта Хайнца.
В 1993–94 и снова в 1999 году Unisys Корпорация получила широкое осуждение, когда она попыталась ввести лицензионные сборы для LZW в изображениях GIF. Противоречие между Unisys-Compuserve (Compuserve, создателем формата GIF) в 1993–1994 гг. Породило обсуждение Usenet comp.graphics Мысли о формате файлов, заменяющих GIF, которые, в свою очередь, способствовали обмену электронной почтой, который в конечном итоге привел к созданию патента. -без обременения формат файла Portable Network Graphics (PNG) в 1995 году.
Патент Unisys в США на алгоритм LZW истек 20 июня 2003 года, через 20 лет после его подачи. Срок действия патентов, поданных в Великобритании, Франции, Германии, Италии, Японии и Канаде, истек в 2004 г., то есть через 20 лет после их подачи.
