Что такое lzw компрессия

АЛГОРИТМЫ СЖАТИЯ

Алгоритм LZW

Как и LZ77, алгоритм LZ78 был опубликован в сугубо научном журнале и сначала воспринимался читателями скорее как абстракция, нежели то, что можно положить в основу программного продукта. Так было до 1984 года, когда Терри Уэлч (Terry Welch) опубликовал свою работу. Модификация алгоритма LZ78, предложенная Уэлчем, получила название LZW (Lempel-Ziv-Welch).

Алгоритм на удивление прост. Если в двух словах, то LZW-сжатие заменяет строки символов некоторыми кодами. Это делается без какого-либо анализа входного текста. Вместо этого при добавлении каждой новой строки символов просматривается таблица строк. Сжатие происходит, когда код заменяет строку символов. Коды, генерируемые LZW-алгоритмом, могут быть любой длины, но они должны содержать больше бит, чем единичный символ. Первые 256 кодов (когда используются 8-битные символы) по умолчанию соответствуют стандартному набору символов. Остальные коды соответствуют обрабатываемым алгоритмом строкам.

Сжатие
Алгоритм LZW-сжатия в простейшей форме приведен ниже. Каждый раз, когда генерируется новый код, новая строка добавляется в таблицу строк. LZW постоянно проверяет, является ли строка уже известной, и, если так, выводит существующий код без генерации нового.

Рассмотрим пример для демонстрации алгоритма. Входная строка:

Как вы можете заметить, эта таблица быстро заполняется, т.к. новая строка добавляется в таблицу каждый раз, когда генерируется код. В этом явно вырожденном примере было выведено пять закодированных подстрок и семь символов. Если использовать 9-битные коды для вывода, то 19-символьная входная строка будет преобразована в 13.5-символьная выходную строку. Конечно, этот пример был выбран только для демонстрации. В действительности сжатие обычно не начинается до тех пор, пока не будет построена достаточно большая таблица, обычно после прочтения порядка 100 входных байт.

Распаковка
Алгоритму сжатия соответствует свой алгоритм распаковки. Он получает выходной поток кодов от алгоритма сжатия и использует его для точного восстановления входного потока. Одной из причин эффективности LZW-алгоритма является то, что он не нуждается в хранении таблицы строк, полученной при сжатии. Таблица может быть точно восстановлена при распаковке на основе выходного потока алгоритма сжатия. Это возможно потому, что алгоритм сжатия выводит СТРОКОВУЮ и СИМВОЛЬНУЮ компоненты кода прежде чем он поместит этот код в выходной поток. Это означает, что сжатые данные не обременены необходимостью тянуть за собой большую таблицу перевода.

Рассмотрим схему работы алгоритма на основе сжатых данных, полученных в выше приведенном примере. Важно отметить, что построение таблицы строк алгоритмом распаковки заканчивается как раз тогда, когда построена таблица строк алгоритма сжатия.

Выходной поток идентичен входному потоку алгоритма сжатия. Отметим, что первые 256 кодов уже определены для перевода одиночных символов, также как и в алгоритме сжатия.

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

Простой пример иллюстрирует это. Предположим, строка «JOEYN» определена в таблице с кодом 300. Когда последовательность «JOEYNJOEYNJOEY» появляется в таблице, выходной поток алгоритма сжатия выглядит следующим образом:

Когда распаковщик просматривает входной поток, он сначала декодирует код 300, затем выводит строку «JOEYN» и добавляет определение для, скажем, кода 399 в таблицу, хотя он уже мог там быть. Затем читает следующий входной код, 400, и обнаруживает, что его нет в таблице. Это уже проблема. К счастью, это произойдет только в том случае, если распаковщик встретит неизвестный код. Так как это фактически единственная коллизия, то можно без труда усовершенствовать алгоритм.

Результаты
Степень сжатия определяется различными факторами. LZW-сжатие выделяется среди прочих, когда встречается с потоком данных, содержащим повторяющиеся строки любой структуры. По этой причине он работает весьма эффективно, когда встречает английский текст. Уровень сжатия может достигать 50% и выше. Соответственно, сжатие видеоформ и копий экранов показывает еще большие результаты.

Трудности при сжатии файлов данных несколько больше. В зависимости от данных, результат сжатия может быть как хорошим, так и не очень удовлетворительным. В некоторых случаях «сжатый» файл может превосходить по своим размерам исходный текст.

Источник

Алгоритм LZW

Непосредственным предшественником LZW является алгоритм LZ78, опубликованный Абрахамом Лемпелем (Abraham Lempel) и Якобом Зивом (Jacob Ziv) в 1978 г. Этот алгоритм воспринимался как математическая абстракция до 1984 г., когда Терри Уэлч (Terry A. Welch) опубликовал свою работу с модифицированным алгоритмом, получившим в дальнейшем название LZW (Lempel—Ziv—Welch).

Содержание

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

Опубликование алгоритма LZW произвело большое впечатление на всех специалистов по сжатию информации. За этим последовало большое количество программ и приложений с различными вариантами этого метода.

Этот метод позволяет достичь одну из наилучших степеней сжатия среди других существующих методов сжатия графических данных, при полном отсутствии потерь или искажений в исходных файлах. В настоящее время используется в файлах формата TIFF, PDF, GIF, PostScript и других, а также отчасти во многих популярных программах сжатия данных (ZIP, ARJ, LHA).

Описание [ править ]

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

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

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

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

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

Пример [ править ]

В нашем примере алгоритму заранее известно о том, что будет использоваться всего [math]5[/math] различных символов, следовательно, для их хранения будет использоваться минимальное количество бит, позволяющее нам их запомнить, то есть [math]3[/math] ( [math]8[/math] различных комбинаций).

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

Закодированное же сообщение так же сначала кодировалось трехбитными группами, а при появлении в словаре восьмого слова — четырехбитными, итого длина сообщения составила [math]4 \cdot 3 + 7 \cdot 4 = 40[/math] бит, что на [math]8[/math] бит короче исходного.

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

Особенность LZW заключается в том, что для декомпрессии нам не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.

Теперь представим, что мы получили закодированное сообщение, приведённое выше, и нам нужно его декодировать. Прежде всего нам нужно знать начальный словарь, а последующие записи словаря мы можем реконструировать уже на ходу, поскольку они являются просто конкатенацией предыдущих записей. Кроме того, в процессе кодировании и декодировании коды в словарь добавляются во время обработки одного и того же символа, т.е. это происходит “синхронно”.

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

Оказывается, это возможно, если оговорить некоторые действия:

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

Мало того, описанное выше правило кодирования мы можем применять в общем случае не только к подряд идущим одинаковым символам, но и к последовательностям, у которых очередной добавляемый символ равен первому символу цепочки.

Источник

Инструменты сайта

Основное

Навигация

Информация

Действия

Содержание

Вспомогательная страница к разделу ☞ КОДИРОВАНИЕ

Алгоритм LZW

Статистические методы кодирования, имеющие целью сжатие передаваемой информации — типа префиксных кодов Хаффмана или Шеннона-Фано — предполагают предварительный анализ всего кодируемого документа и составление кодовой таблицы. Последняя должна быть известной декодеру или же, в общем случае, быть приложенной к закодированному документу.

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

Именно это предлагается в алгоритме Лемпеля-Зива-Уэлча (Lempel—Ziv—Welch) или LZW[1,2]. Более того, алгоритм не предполагает необходимости передачи декодеру составленного кодером словаря: по получении закодированной последовательности и при дополнительном знании кодировки начальных слов словаря (обычно, некоторого базового «алфавита»), декодер может сам динамически, т.е. в параллель с декодированием, восстановить исходный кодовый словарь!

Идея алгоритма напомнила мне идею шифрования по методу Кардано.

Кодирование (первое приближение)

оитомии о ими оооитми о о о ооиимтомиимотоим оои тоо и и м оио и омтоо тоимо т и

Стартовое состояние словаря: известна кодировка букв алфавита, будем считать, что она совпадает с нумерацией этих букв согласно таблице:

оитомии_о_ими

Во второй строке — текст, который надо закодировать, в третьей — код.

Начинаем кодировать текст, одновременно пополняя словарь:

оитомии_о_ими

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

а в словарь — трехбуквенное слово _оо. Идем далее:

Вот уже в словаре появляется четырехбуквенное слово…

оитомии_о_ими_оооитми_

о_о_о_ооиимтомиимотоим_оои_тоо_и_и_м_о

Здесь уже появилось пятибуквенное…

ио_и_омтоо_тоимо_т_иимиотмии

3 1 4 3 2 1 1 0 3 0 1 9 12 3 5 4 16 13 22 17 10 2 7 9 15 3 7 15 24 11 7 13 11 11 2 12 1 36 12 26 18 0 31 2 13 4

Декодирование

На вход процедуры подается последовательность чисел

3 1 4 3 2 1 1 0 3 0 1 9 12 3 5 4 16 …

Стартовое состояние: известна кодировка базового словаря (алфавита). Это позволяет декодировать начальный отрезок закодированного текста

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

Дальнейшая процедура протекает аналогично вплоть до вот этого момента

Продолжаем процесс декодирования

3 1 4 3 2 1 1 0 3 0 1 9 12 3 5 4 16 …

3 1 4 3 2 1 1 0 3 0 1 9 12 3 5 4 16 …

Это правило позволяет согласовать генерацию словаря с той, что совершалась в ходе кодирования текста. ♦

В том же алфавите (и при той же кодировке его букв в словаре) декодировать

3 0 4 3 2 6 8 1 4 0 3 4 12 0 1 0 2 15 20 1 21 10 7

В разобранном алгоритме декодирования имеется слабое место, которое проиллюстируем примером.

Кодирование не вызывает проблем:

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

И для разрешения этой коллизии нам придется откорректировать алгоритм кодирования.

Кодирование (коррекция алгоритма)

Решение коллизии возможно, например, удовлетворением требования блочности кода: все кодовые блоки делаем одинаковой длины. В рассмотренном примере в кодовой последовательности

3 1 4 3 2 1 1 0 3 0 1 9 12 3 5 4 16 13 22 17 10 2 7 9 15 3 7 15 24 11 7 13 11 11 2 12 1 36 12 26 18 0 31 2 13 4

вставляем нули перед однозначными числами:

03 01 04 03 02 01 01 00 03 00 01 09 12 03 05 04 16 13 22 17 10 02 07 09 15 03 07 15 24 11 07 13 11 11 02 12 01 36 12 26 18 00 31 02 13 04

Что делать? — Отказываться от требований блочности и однозначности кодирования.

Возвращаемся к примеру из начала раздела, только теперь перепишем кодовые последовательности в более привычном бинарном виде.

Пример.

Первые шаги алгоритма кодирования абсолютно идентичны рассмотренным в его начальной версии:

оитомии_о_ими

Стоимость

Насколько экономичен алгоритм LZW? Тестирование производилось с помощью реализации, осуществленной Иваном Боровым.

Пример. Текст

oitomii o imi oooitmi o o o ooiimtomiimotoim oi too i i m oio i omtoo toimo t iimiotmii ttmiotoitoomt imo o t mii i i m o ooi o tom tototoi oto i moi t i o mimto toootoi otomtioio t m iim toi m i iooim ittoomooo i i tom t oto iimitimoi o tmi tmi otomi i too t tioot tim mii oiooi tooimioomiootoooioo i oomiotmiotomi i o m ooo i tootmtiti i o ototi o omi i m iti i otooi i toooioomo i tmooi i oti tot iimii mio i moo omt totoo o m mooii imt i totmi i oot i o otito tom tot otoiiii i ootottm o ottoioooimo too imtoimoom oom titoo i oiomotoii i i oto iiioi i tioio too o m too tiotomtii oii o iii tom mot imt tiooi

Пример. Текст «Идиота» 6) в русском алфавите, без буквы ё, пробел учитывается, знаки препинания — нет.

Источники

[1]. Ziv J., Lempel A. Compression of Individual Sequences via Variable-Rate Coding. IEEE Trans. Inform. Theory, 1978, V. 24 (5), pp. 530–536

[2]. Welch T. A Technique for High-Performance Data Compression. Computer, 1984, V. 17 (6), pp. 8–-19.

[3]. Сэломон Д. Сжатие данных, изображений и звука. М.Техносфера. 2006.

Источник