Лемпель – Зив – Велч - Lempel–Ziv–Welch

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.

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

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

Расшифровка

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

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

Если используются коды переменной ширины, кодировщик и декодер должны быть осторожны, чтобы изменить ширину в одних и тех же точках закодированных данных, чтобы они не расходились по границам между отдельными кодами в потоке. В стандартной версии кодировщик увеличивает ширину с 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 в действии, показывая состояние вывода и словаря на каждом этапе, как при кодировании, так и при декодировании данных. Этот пример создан для разумного сжатия очень короткого сообщения. В реальных текстовых данных повторение обычно менее выражено, поэтому обычно необходимы более длинные входные потоки, прежде чем сжатие повысит эффективность.

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

TOBEORNOTTOBEORTOBEORNOT#

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

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

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

Символ Двоичный Десятичный
# 00000 0
А 00001 1
B 00010 2
C 00011 3
D 00100 4
E 00101 5
F 00110 6
грамм 00111 7
ЧАС 01000 8
я 01001 9
J 01010 10
K 01011 11
L 01100 12
M 01101 13
N 01110 14
О 01111 15
п 10000 16
Q 10001 17
р 10010 18
S 10011 19
Т 10100 20
U 10101 21 год
V 10110 22
W 10111 23
Икс 11000 24
Y 11001 25
Z 11010 26

Кодирование

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

Текущая последовательность Следующий символ Выход Расширенный словарь Комментарии
Код Биты
НОЛЬ Т
Т О 20 10100 27: К 27 = первый доступный код после 0 до 26
О B 15 01111 28: OB
B E 2 00010 29: БЫТЬ
E О 5 00101 30: EO
О р 15 01111 31: ИЛИ ЖЕ
р N 18 10010 32: RN 32 требует 6 бит, поэтому для следующего вывода используйте 6 бит
N О 14 001110 33: НЕТ
О Т 15 001111 34: ОТ
Т Т 20 010100 35: TT
К B 27 011011 36: TOB
БЫТЬ О 29 011101 37: BEO
ИЛИ ЖЕ Т 31 год 011111 38: ОРТ
TOB E 36 100100 39: БЫТЬ
EO р 30 011110 40: EOR
RN О 32 100000 41: РНО
ОТ # 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 B 28: OB 29: Б?
00101 5 E 29: БЫТЬ 30: E?
01111 15 О 30: EO 31: О?
10010 18 р 31: ИЛИ ЖЕ 32: Р? созданный код 31 (последний помещается в 5 бит)
001110 14 N 32: RN 33: N? так что начните читать ввод с 6 бит
001111 15 О 33: НЕТ 34: О?
010100 20 Т 34: ОТ 35: Т?
011011 27 К 35: TT 36: К?
011101 29 БЫТЬ 36: TOB 37: БЫТЬ? 36 = ТО + 1-й символ (B) из
011111 31 год ИЛИ ЖЕ 37: BEO 38: ИЛИ ЖЕ? получена следующая кодированная последовательность (BE)
100100 36 TOB 38: ОРТ 39: TOB?
011110 30 EO 39: БЫТЬ 40: ЭО?
100000 32 RN 40: EOR 41: РН?
100010 34 ОТ 41: РНО 42: ОТ?
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 , где с представляет собой один символ, 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 ) от Карла Экхарта Хайнца.

В 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 г., через 20 лет после его подачи. Срок действия патентов, поданных в Великобритании, Франции, Германии, Италии, Японии и Канаде, истек в 2004 г., то есть через 20 лет после их подачи.

Варианты

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

Смотрите также

Рекомендации

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