Лемпель – Зив – Велч

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

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

Алгоритм [ править ]

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

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

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

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

Кодировка [ править ]

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

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

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

Таким образом, последовательно более длинные строки регистрируются в словаре и доступны для последующего кодирования как отдельные выходные значения. Алгоритм лучше всего работает с данными с повторяющимися шаблонами, поэтому начальные части сообщения мало сжимаются. Однако по мере роста сообщения степень сжатия асимптотически стремится к максимуму (т. Е. Коэффициент или степень сжатия улучшаются по возрастающей кривой, а не линейно, приближаясь к теоретическому максимуму в течение ограниченного периода времени, а не в течение бесконечного времени). ^[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 (« самый старший бит»first "). При упаковке LSB-first первый код выравнивается так, чтобы младший бит кода приходился на младший значащий бит первого байта потока, а если код имеет более 8 битов, старший оставшиеся биты выравниваются с младшими значащими битами следующего байта; дальнейшие коды упаковываются с LSB, идущим в младший значащий бит, еще не использованный в текущем байте потока, переходя в следующие байты по мере необходимости. код, так что его самый старший бит попадает в 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 бит, чтобы учесть это. )

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

Кодировка [ править ]

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

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

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

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

Расшифровка [ править ]

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

На каждом этапе декодер получает код 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 , где с представляет собой один символ, S представляет собой строку и сСт уже в словаре, но CSC не является. Кодировщик испускает код для cS , помещая новый код для cSc в словарь. Далее он видит CSC на входе (начиная со второй с из cScSc ) и испускает новый код он просто вставлен. Приведенный выше аргумент показывает, что всякий раз, когда декодер получает код, которого нет в его словаре, ситуация должна выглядеть так.

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

Дальнейшее кодирование [ править ]

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

Использует [ редактировать ]

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

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

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

Патенты [ править ]

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

В дополнение к указанным выше патентам, 1983 патента Уэлча также включает в себя цитаты на несколько других патентов , которые повлияли на него, в том числе два 1980 японских патентов ( JP9343880A и JP17790880A ) от NEC «ы июня Kanatsu, патент США 4021782 (1974) от John S. Hoerning, Патент США 4366551 (1977) от Клауса Э. Хольца и патент Германии 1981 года ( DE 19813118676 ) от Карла Экхарта Хайнца. ^[3]

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

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

Варианты [ править ]

• LZMW (1985, В. Миллер, М. Вегман) ^[5] - Ищет на входе самую длинную строку, которая уже есть в словаре («текущее» совпадение); добавляет в словарь конкатенацию предыдущего совпадения с текущим совпадением. (Словарные статьи, таким образом, растут быстрее, но эту схему гораздо сложнее реализовать.) Миллер и Вегман также предлагают удалять низкочастотные статьи из словаря, когда словарь заполняется.
• LZAP (1988, Джеймс Сторер) ^[6] - модификация LZMW: вместо добавления в словарь просто конкатенации предыдущего совпадения с текущим совпадением, добавьте конкатенации предыдущего совпадения с каждой начальной подстрокой текущего совпадения ( «AP» означает «все префиксы»). Например, если предыдущее совпадение - «wiki», а текущее совпадение - «pedia», то кодировщик LZAP добавляет в словарь 5 новых последовательностей: «wikip», «wikipe», «wikiped», «wikipedi» и «wikipedia». ", где кодировщик LZMW добавляет только одну последовательность" wikipedia ". Это устраняет часть сложности LZMW за счет добавления большего количества словарных статей.
• LZWL - это слоговый вариант LZW.

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

• Rosettacode wiki, алгоритм на разных языках
• Патент США 4558302 , Терри А. Велч, Устройство и способ высокоскоростного сжатия и декомпрессии данных.
• SharpLZW - реализация на C # с открытым исходным кодом
• MIT OpenCourseWare: Лекция, включающая алгоритм LZW
• Марк Нельсон, LZW Data Compression on Dr. Dobbs Journal (1 октября 1989 г.)