Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Формат 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:// данные не сжаты, просто копируем их /*заголовок блока не выровнен на границу байта, сделаем это 4 */ 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

Значе­ние базы

Число доп. битов

Длина сов­падения

Значение базы

Число доп. битов

Длина совпа­дения

257

0

3

272

2

31...34

258

0

4

273

3

35...42

259

0

5

274

3

43...50

260

0

6

275

3

51...58

261

0

7

276

3

59...66

262

0

8

277

4

67...82

263

0

9

278

4

83...98

264

0

10

279

4

99...114

265

1

11,12

280

4

115...130

266

1

13,14

281

5

131...162

267

1

15,16

282

5

163...194

268

1

17,18

283

5

195...226

269

2

19...22

284

5

227...257

270

2

23...26

285

0

258

271

2

27...30

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

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

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

Таблица 3.7

Зна­чение базы

Число доп. битов

Значение смещения

Значение базы

Число

ДОП.

битов

Значение смещения

0

0

1

15

6

193...256

I

0

2

16

7

257...384

2

0

3

17

7

385...512

3

0

4

18

8

513...768

4

1

5,6

19

8

769... 1024

5

1

7,8

20

9

1025...1536

6

2

9...12

21

9

1537...2048

7

2

13...16

22

10

2049...3072

8

3

17...24

23

10

3073...4096

9

3

25...32

24

11

4097...6144

10

4

33...48

25

11

6145...8192

11

4

49...64

26

12

8193...12288

12

5

65...96

27

12

12289... 16384

13

5

97...128

28

13

16385...24576

14

6

129...192

29

13

24577...32768

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

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

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

Таблица 3.8

Значение символа

Длина кода, бит

Значение кода (в двоичной системе счисления)

0-143

8

00110000 10111111

144-255

9

110010000 111111111

256-279

7

0000000 0010111

280-287

8

11000000

11000111

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

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

Пример

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

Элемент

Смещение /

Длина совпадения;

Литерал

1

260

5

-

2

45

20

-

3

-

-

3

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

Длина совпадения

Соответствующий символ в алфавите литералов/длин

База

Число дополнительных битов

5

259

259

0

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

Смещение

База

Число дополнительных битов

Значение дополнительных битов

260

16

7

3

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

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

Элемент

Последовательность битов

Комментарии

I

00000И Ю000_00000И

База длины совпадения = 259. Поле дополнительных битов совпадения от­сутствует.

База смещения =16.

Поле дополнительных битов смещения = 3. Длина поля = 7

2

000П01 01 OIOIOJIOO

База длины совпадения = 269.

Поле дополнительных битов совпадения = 1.

Длина поля = 2.

База смещения = 10.

Поле дополнительных битов смещения = 12.

Длина поля = 4

3

00110011

Литерал = 3

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

Хаффмана

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

Таблица 3.9

Значение

символа

алфавита

CWL

Что определяет

0...15

Соответствует длинам кодов от 0 до 15

16

Копировать предыдущую длину кода х раз, где х определяется зна­чением 2 битов, читаемых после кода символа 16; можно указать необходимость повторить предыдущую длину 3-6 раз

17

Позволяет задать для х кодов, начиная с текущего, длину 0; х мо­жет принимать значения от 3 до 10 и определяется таким же обра­зом, как и для 16

18

Аналогично 17, но х может быть от 11 до 138

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

Значение символа

0

1

2

3

4

5

6

7

8

9

Длина кода символа

2

3

3

3

3

3

0

0

0

4

?

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

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

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

Таблица 3.10

Поле

Описание

Размер

HLIT

Хранит количество кодов литералов/длин минус 257

5 бит

HDIST

Хранит количество кодов смещений минус 1

5 бит

HCLEN

Хранит количество кодов длин кодов минус 4

4 бита

Таблица описания кодов длин ко­дов (коды 2)

Содержит описание (последовательность длин ко­дов) длин кодов в следующем порядке: 16,17,18,0, 8,7,9,6,10,5,11,4, 12,3, 13,2,14,1,15. Иначе го­воря, это порядок символов в алфавите CWL. Длина кода любого символа CWL задается с помо­щью 3 бит; таким образом, длина кода длины кода может быть от 0 (соответствующий символ из CWL не используется) до 23 - 1 = 7 бит. Длины однозначно задают совокупность кодов

(HCLEN+4)-Збита

Таблица описания кодов ли­тералов/ длин (коды 1)

Содержит описание HLIT+257 кодов литералов/длин совпадения, закодировано кодами длин кодов

Перемен­ный

Таблица описания кодов сме­щений

Содержит описание HDIST+l кодов смещений, за­кодировано кодами длин кодов

Перемен­ный

Сжатые данные

Содержит данные, сжатые с помощью двух задан­ных выше совокупностей кодов

м

Знак кон­ца блока

Число 256, сжатое с помощью кодов литералов/длин

и

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

■ литералы/длины совпадения кодируются с помощью кодов Хаффмана для литералов/длин, назовем их кодами 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 для строки snl, Sm, S/+3> ■ • •. находящейся в начале буфера, выполня­ется поиск совпадения match (t+2) для строки sn2, sn3, sM... Если 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) {

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

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

}else{

match_available = 1.;

}

move_window (1);

t++; )

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

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

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

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