Формат Deflate

Формат словарного сжатия Deflate, предложенный Кацем (Katz), исполь­зуется популярным архиватором PKZIP [3]. Сжатие осуществляется с по­мощью алгоритма типа LZH, иначе говоря, указатели и литералы кодируют­ся по методу Хаффмана. Формат специфицирует только работу декодера, т. е. определяет алгоритм декодирования, и не налагает серьезных ограни чений на реализацию кодера. В принципе в качестве алгоритма сжатия мо­жет применяться любой работающий со скользящим окном, лишь бы он ис­ходил из стандартной процедуры обновления словаря для алгоритмов се­мейства LZ77 и использовал задаваемые форматом типы кодов Хаффмана.

Особенности формата:

■ является универсальным, т. е. не ориентирован на конкретный тип данных;

■ прост в реализации;

■ де-факто является одним из промышленных стандартов на сжатие данных.

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

)1 Поучительная ремарка. В 1994 г. корпорация Unisys "вспомнила" о своем патенте в США на алгоритм LZW, зарегистрированном в 1985 г., и объявила о незаконности использования LZW без соответствующей лицензии. В частно­сти, Unisys заявила о нарушении своих прав как патентовладельца в случае не-лицензированного использования алгоритма LZWe формате GIF. Было объявле­но, что производители, программы или аппаратное обеспечение которых чи­тают или записывают файлы в формате GIF, должны покупать лицензию на использование, а также выплачивать определенный процент с прибыли при коммерческом применении. Далее Unisys в лучших традициях тоталитарной пропаганды последовательно продолжала переписывать историю, неоднократ­но меняя задним числом свои требования к лицензируемым продуктам и условия оплаты. В частности, было оговорено, что плата взимается только в случае коммерческих продуктов, но в любом случае требуется получить официальное разрешение от Unisys. Но, с другой стороны, Unisys требует у всех владельцев Интернет (интранет)-сайтов, использующих рисунки в формате GIF, приобре­сти лицензию стоимостью порядка $5000 в том случае, если ПО, с помощью которого были созданы эти файлы GIF, не имеет соответствующей лицензии Unisys. С точки зрения некоторых независимых экспертов по патентному пра­ву, чтение (декодирование) GIF-файлов не нарушает права Unisys, но, судя по всему, сама корпорация придерживается другой точки зрения. Также доста­точно странно поведение корпорации CompuServ, разработавшей формат GIF и опубликовавшей его в 1987 г., т. е. уже после регистрации патента на LZW, как открытый и свободный от оплаты. По состоянию на 2001 г., LZWзапа­тентован Unisys no меньшей мере в следующих странах: США, Канаде, Велико­британии, Германии, Франции, Японии. Текущее состояние дел можно выяс­нить на сайте компании www.unisys.com. Срок действия основного патента в США истекает не ранее 19 июня 2003 г.

Общее описание

Закодированные в соответствии с форматом Deflate данные представля­ют собой набор блоков, порядок которых совпадает с последовательностью соответствующих блоков исходных данных. Используется 3 типа блоков за­кодированных данных:

1) состоящие из несжатых данных;

2) использующие фиксированные коды Хаффмана;

3) использующие динамические коды Хаффмана.

Длина блоков первого типа не может превышать 64 Кб, относительно других ограничений по размеру нет. Каждый блок типа 2 и 3 состоит из двух частей:

■ описания двух таблиц кодов Хаффмана, использованных для кодирова­ния данных блока;

■ собственно закодированных данных.

Коды Хаффмана каждого блока не зависят от использованных в преды­дущих блоках.

Само описание динамически создаваемых кодов Хаффмана является, в свою очередь, также сжатым с помощью фиксированных кодов Хаффма­на, таблица которых задается форматом.

Алгоритм словарного сжатия может использовать в качестве словаря часть предыдущего блока (блоков), но величина смещения не может быть больше 32 Кб. Данные в компактном представлении состоят из кодов эле­ментов двух типов:

■ литералов (одиночных символов);

■ указателей имеющихся в словаре фраз; указатели состоят из пары <дли-на совпадения, смещением

Длина совпавшей строки не может превышать 258 байт, а смещение фразы - 32 Кб. Литералы и длины совпадения кодируются с помощью од­ной таблицы кодов Хаффмана, а для смещений используется другая табли­ца; иначе говоря, литералы и длины совпадения образуют один алфавит. Именно эти таблицы кодов и передаются в начале блока третьего типа.

Алгоритм декодирования

Сжатые данные декодируются по следующему алгоритму.

do{

Block.ReadHeader (); // читаем заголовок блока /*определяем необходимые действия по разжатию в

соответствии с типом блока */

switch (Block.Type) {

case NO_COMP:// данные не сжаты, просто копируем их /*заголовок блока не выровнен на границу байта, сделаем это ⁴ */ Block.SeekNextByte ();

Block.ReadLen (); // читаем длину блока /♦копируем данные блока из входного файла сжатых данных в результирующий DataFile */

PutRawData (Window, Block, DataFile); break; case DYN_HUF:

/*блок данных сжат с помощью динамически построенных кодов Хаффмана, прочитаем их ■ */ Block.ReadHuffmanCodes (); case FIXED_HUF: for (;;) {

/♦прочтем один символ алфавита литералов и

длин совпадения */

value = Block.DecodeSymbol (); if ( value < 256)

// это литерал, запишем его в выходной файл DataFile.WriteSymbol (value); else if ( value == 256) // знак конца блока break; else {

// это закодированный указатель match_len = Block.DecodeLen (); match_pos = Block.DecodePos (); /♦скопируем соответствующую фразу из словаря

в выходной файл */

CopyPhrase (Window, match_len, match_pos, DataFile);

} };

break; default:

// Ошибка в блоке данных throw BadData (Block) ; )while ( IIsLastBlock );

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

Кодирование длин и смещений

Как уже указывалось, литералы и длины совпадения объединены в единый алфавит символов со значениями {0, 1, ..., 285}, так что 0-255 отведены под литералы, 256 указывает на конец текущего блока, а 257-285 определяют дли­ны совпадения. Код длины совпадения состоит из кода числа, лежащего в диа­пазоне 257-285 (базы длины совпадения), и, возможно, дополнительно читае­мых битов, непосредственно следующих за кодом этого числа. База определяет квантованную длину совпадения, поэтому одному значению базы может соот­ветствовать несколько длин. Значение поля дополнительно читаемых битов ис­пользуется для доопределения длины совпадения. Таблица отображения значе­ний кодов в длины фраз приведена ниже (табл. 3.6).

Таблица 3.6

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

Таким образом, функция Block.DecodeSymbol, упомянутая в преды­дущем подразд., читает символ, который может быть либо литералом, либо знаком конца блока, либо базой совпадения. В последнем случае, т. е. когда значение символа > 256, дополнительные биты читаются с помощью функ­ции Block. DecodeLen.

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

Таблица 3.7

Функция Block. DecodePos должна выполнить два действия: прочитать базу смещения и, на основании значения базы, прочитать необходимое ко­личество дополнительных битов. Как и в случае литералов/длин совпаде­ния, дополнительные биты соответствуют целым числам заданной длины, в которых первым записан самый старший бит.

Кодирование блоков фиксированными кодами Хаффмана

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

Таблица 3.8

Символы со значениями 286 и 287 не должны появляться в сжатых дан­ных, хотя для них и отведено кодовое пространство.

Базы смещений кодируются S-битовыми числами так, что 00000 соот­ветствует 0, 11111 -31. При этом запрещается использовать базы со значе­ниями 30 и 31, так как их смысл не определен.

Пример

Покажем, как выглядит в закодированном виде такая последователь­ность замещенных строк и литерала:

Длина совпадения раскладывается на два поля, поэтому для у = 5 получа­ем (см. табл. 3.6):

Длина совпадения кодируется как 0000011 (см. табл. 3.8). В общем случае смещение состоит также из двух полей, и для / = 260 получаем:

Смещение 260 записывается как последовательность битов 1000000000П (подчеркиванием показана граница чисел), где первое чис­ло - база, второе - поле дополнительных битов, равное 260 - 257 = 3.

Действуя аналогичным образом, на основании табл. 3.6, 3.7, 3.8 находим отображение всей последовательности:

Кодирование блоков динамически создаваемыми кодами

Хаффмана

В этом случае перед собственно сжатыми данными передается описание кодов литералов/длин и описание кодов смещений. В методе Deflate исполь­зуется канонический алгоритм Хаффмана, поэтому для указания кода сим­вола достаточно задать только длину этого кода. Неявным параметром яв­ляется положение символа в упорядоченном списке символов. Таким обра­зом, динамические коды Хаффмана описываются цепочкой длин кодов, упорядоченных по значению соответствующего кодам числа (литера­ла/длины совпадения в одном случае и смещения в другом). При этом алфа­вит CWL (codeword lengths) длин кодов имеет вид, описанный в табл. 3.9.

Таблица 3.9

Например, если в результате декодирования описания кодов была полу­чена цепочка длин 2, 3, 16 (х = 4), 17 (х=3), 4,..., то длина кодов символов будет равна:

Обратите внимание, что символы упорядочены по возрастанию их зна­чений.

С целью увеличения сжатия сами эти цепочки длин кодируются с помо­щью кодов Хаффмана. Если длина кода символа (т. е. длина кода длин ко­дов) равна нулю, то это значит, что соответствующий символ в данных не встречается и код ему не отводится.

Формат блока с динамическими кодами Хаффмана описан в табл. 3.10.

Таблица 3.10

На основании вышесказанного можно дать такое описание алгоритма кодирования литералов/длин:

■ литералы/длины совпадения кодируются с помощью кодов Хаффмана для литералов/длин, назовем их кодами 1;

■ описание кодов 1 передается в виде цепочки длин этих кодов;

■ при указании длин кодов могут использоваться специальные символы (см. алфавит CWL);

■ длины кодов, т. е. символы алфавита CWL, кодируются с помощью ко­дов Хаффмана для длин кодов, назовем их кодами 2;

■ коды 2 также описываются через последовательность их длин;

■ длины кодов 2 задаются с помощью 3-битовых чисел.

Для кодирования смещений используется такой же подход, при этом длины кодов смещений также сжимаются с помощью кодов 2.

Упражнение. Объясните, почему размеры полей, хранящих величины HLIT, HDIST и HCLEN, именно таковы, как это указано в табл. 3.10.

Алгоритм словарного сжатия для Deflate

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

Рассмотрим свободный от патентов алгоритм сжатия для Deflate, ис­пользуемый в разрабатываемой Info-ZIP group утилите Zip.

Для поиска фраз используется метод хеш-цепочек. Хеш-функция вычисля­ется на основании 3 байт данных (напомним, что формат Deflate не позволяет кодировать строки длиной менее 3 байт). Функция может принимать значения от 0 до заданного числа HASHMASK - 1 и имеет вид выражения, последова­тельно вычисляемого для каждого очередного символа:

int UPDATE_HASH (int h, char с) {

return ( (h«H_SHIFT) ^л с ) & HASH_MASK;

}

где h - текущее значение хеш-функции; с - очередной символ; HSHIFT -параметр сдвига значения функции.

HSHIFT назначается таким образом, чтобы после очередного сдвига значение самого старого байта не влияло на значение хеш-функции.

На каждом шаге компрессор читает очередную 3-байтовую строку, рас­полагающуюся в начале буфера. После соответствующего обновления хеш-функции производится обращение к первому элементу хеш-цепочки, адрес которого определяется значением функции. Если цепочка пуста, то кодиру­ется литерал, производится сдвиг окна на 1 символ и осуществляется пере­ход к следующему шагу. Иначе хеш-цепочка анализируется с целью найти самое длинное совпадение между буфером и фразами, на которые ссылают­ся элементы (узлы) хеш-цепочки. Обновление хеш-цепочек организовано так, что поиск начинается с самых "новых" узлов, что позволяет сместить распределение частот смещений кодируемых фраз в пользу коротких сме­щений и, следовательно, улучшить сжатие, так как небольшие смещения имеют коды малой длины.

Для ускорения кодирования в случае обработки избыточных данных очень длинные хеш-цепочки обрубаются до определенной длины, задавае­мой параметрами алгоритма. Усечение производится в зависимости от дли­ны уже найденного совпадения: чем оно длиннее, тем больше отрезаем.

Сжатие может быть улучшено за счет механизма "ленивого" сравнения (lazy matching, или lazy evaluation). Этот подход позволяет отойти от прямо­линейного, "жадного" разбора входной последовательности и повысить эф­фективность сжатия путем более аккуратного выбора фраз словаря. После того как определяется совпадающая фраза match (t+l) длины match Jen (t+\) = L для строки s_nl, Sm, S/+3> ■ • •. находящейся в начале буфера, выполня­ется поиск совпадения match (t+2) для строки s_n2, s_n3, s_M... Если match Jen (t+2) > match Jen (t+l) = L, то отказываемся от замещения строки •sv+i, St+2, St+i--- Решение о том, следует кодировать match (t+2) или нет, при­нимается на шаге t+Ъ по результатам аналогичной проверки. Иначе кодиро­вание протекает обычным образом, но с "запаздыванием" на один шаг. Под­робнее:

// минимальная длина совпадения

const int THRESHOLD = 3;

// смещение и длина совпадения для match(t+l)

int prev_pos,

prev_len; // смещение и длина совпадения для match (t+2) int match_pos,

match__len = THRESHOLD - 1; // признак отложенного кодирования фразы match(t+l)

int match_available = 0;

prev_pos = match_pos; prev_len = match_len;

/♦найдем максимальное (или достаточно длинное) совпадение

для позиции t+2 */

find_phrase (smatch_pos, Smatch_len); if ( prev_len >= THRESHOLD && match_len <= prev_len ) {

/* считаем, что выгоднее закодировать фразу match(t+1)

Ч

encode_phrase (prev_pos, prev_len);

match_available = 0;

match_len = THRESHOLD - 1;

// сдвинем окно на match_len{t+1)-1 символов

move_window (prev_len-l);

t += prev_len-l; } else {

// отложим решение о кодировании на один шаг

if (match_available) {

/♦кодирование литерала s_t+i или фразы match(t+1)

было отложено; кодируем литерал s_t+i */ encode_literal (window[t+1]);

}else{

match_available = 1.;

}

move_window (1);

t++; )

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

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

Упражнение. Объясните, почему использование ленивого сравнения при сжа­тии не требует внесения изменений в алгоритм декодера.

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