Алгортм сжатия Deflate,
детальное описание
Повторим. Главная идея алгоритма Deflate --
совместить алгоритмы сжатия LZ77 и коды Хаффмана.
В алгоритме Deflate сначала применяется алгоритм LZ77,
который по входному потоку байтов выдает поток троек
(дистанция назад, длина фразы, следующий байт)
где
1 <= дистанция <= 32768
3 <= длина фразы <= 258
0 <= байт <= 255
(в том случае, если фраза уже встречалась
раньше; если нет, то тройка выглядит так:
(0, 0, байт)
). Код байта иногда называют литералом, т.е.
это численная константа в диапазоне от 0..255.
Также добавляется специальный стоп-символ
с кодом 256, который в алгоритме Deflate обозначает
конец блока.
Априори такие тройки могут занимать больше
места, чем исходный поток байтов (на дистанцию
надо надо отводить 15 битов, на длину 9 битов, на
литерал 8 битов -- итого 32 бита на тройку).
Поэтому к потоку троек, который выдается алгоритмом
LZ77, потом применяется еще и кодирование Хаффмана.
Впрочем, эта схема отнюдь не прямая, и даже
понять ее описание непросто.
Закодированный поток битов (не байтов!) состоит из
блоков. Каждый блок задается 3-мя битами в его начале:
-- первый бит равен 0, если блок не последний,
и 1, если последний;
-- следующие 2 бита означают тип блока (блоки
бывают 3-х типов):
1) биты "00" означают, что блок не сжимается,
а просто передаются байты, соответствующие
байтам входного потока. Дальше
пропускаются 5 битов 0 и задается сначала
длина последовательности байтов (в двух
байтах, 1 <= длина <= 65535)
-----+------+==========================
LEN | NLEN | последовательность байтов
-----+------+==========================
Длина равна LEN + NLEN*256;
2) биты "01" означают, что используется
фиксированные деревья кодов Хаффмана для двух
алфавитов:
(1) алфавита литералов и длин, и (2) алфавита
дистанций. Описания этих двух кодовых деревьев
не передаются в выходном потоке (они
фиксированы и заданы в стандарте алгоритма);
3) биты "10" означают, что используются динамические
деревья Хаффмана для двух алфавитов, эти деревья
вычисляются в соответствии с вероятностями
символов этих двух алфавитов, которые определяет
кодировщик в процессе работы. Передаются
сначала описание кодов и дерева Хаффмана для
алфавита литералов и длин, затем описание
кодов Хаффмана для алфавита дистанций.
Причем и описания этих двух деревьев
Хаффмана передаются с помощью третьего
дерева кодов -- дерева для алфавита
длин кодов (подробности будут
приведены ниже). То есть в начале блока,
помимо нескольких констант, передается
сначала описание дерева Хаффмана для алфавита
длин кодов, затем описание дерева Хаффмана
для алфавита литералов и длин, в конце
дерево Хаффмана для алфавита дистанций.
И лишь затем идет последовательность кодов,
описывающее содержание фрагмента входных
данных, соответствующих этому блоку.
Блок заканчивается кодом стоп-символа.
Эта последовательность кодов состоит из
кодов литералов, перемежающаяся с парами
кодов длин и дистанций (именно в таком порядке --
сначала длина фразы, потом обратная дистанция
к фразе, которая уже встречалась раньше).
Например,
литерал, литерал, литерал, длина, дистанция,
литерал, длина, дистанция, длина, дистанция,
литерал, литерал, длина, дистанция, ...,
код стоп-символа.
Различия между блоками "01" и "10" только в том,
что в случае блока типа "01" не передается
информация о деревьях Хаффмана.
Очень важно!
И в случае длин, и особенно в случае дистанций
слишком много вариантов. Например, число дистанций
равно 32767, это очень большой алфавит, и кодировать
такой огромный алфавит неэффективно. Поэтому дистанции
делятся на 30 классов, в стандарте содержится описание
этого разбиения:
1; 2; 3; 4; 5-6; 7-8; 9-12; 13-16; 17-24; 25-32;
33-48; 49-64; 65-96; 97-128; 129-192; ...
24577-32768.
Для передачи длины сначала передается код символа,
соответствующего классу этих длин, и затем
в нескольких битах смещение относительно начальной длины
этого класса. Например, для длины 112 ее класс номер 13
содержит длины в диапазоне 97-128, смещение для
длины 112 равно 112-97 = 15, число 15 записывается
в 5-ти битах как "01111". Еще раз, для дистанции
сначала передается код символа, соответствующего
этому классу (класс 13 в данном примере), и затем
смещение относительно начальной длины в этом классе,
в нашем примере 5-битовая запись числа 15, равная
"01111". Длины дополнительных битовых
последовательностей для классов дистанций приведены
в таблице, содержащейся в описании стандарта:
Extra Extra Extra
Code Bits Dist Code Bits Dist Code Bits Distance
---- ---- ---- ---- ---- ------ ---- ---- --------
0 0 1 10 4 33-48 20 9 1025-1536
1 0 2 11 4 49-64 21 9 1537-2048
2 0 3 12 5 65-96 22 10 2049-3072
3 0 4 13 5 97-128 23 10 3073-4096
4 1 5,6 14 6 129-192 24 11 4097-6144
5 1 7,8 15 6 193-256 25 11 6145-8192
6 2 9-12 16 7 257-384 26 12 8193-12288
7 2 13-16 17 7 385-512 27 12 12289-16384
8 3 17-24 18 8 513-768 28 13 16385-24576
9 3 25-32 19 8 769-1024 29 13 24577-32768
Аналогичная идея используется и для алфавита литералов
и длин. В этом алфавите символы 0..255 соответствуют
литералам (кодам байтов), символ 256 -- это стоп-символ,
и дальше символы 257..285 соответствуют длинам фраз
от 3 до 258. Используется та же техника разделения длин
на классы и добавления после символа класса длины еще
нескольких дополнительных битов, задающих смещение
внутри класса относительно его первого элемента.
Длины этих дополнительных последовательностей битов
содержатся в следующей таблице, заданной в стандарте
RFC 1951:
Extra Extra Extra
Code Bits Length(s) Code Bits Lengths Code Bits Length(s)
---- ---- ------ ---- ---- ------- ---- ---- -------
257 0 3 267 1 15,16 277 4 67-82
258 0 4 268 1 17,18 278 4 83-98
259 0 5 269 2 19-22 279 4 99-114
260 0 6 270 2 23-26 280 4 115-130
261 0 7 271 2 27-30 281 5 131-162
262 0 8 272 2 31-34 282 5 163-194
263 0 9 273 3 35-42 283 5 195-226
264 0 10 274 3 43-50 284 5 227-257
265 1 11,12 275 3 51-58 285 0 258
266 1 13,14 276 3 59-66
Например, для кодирования длины 56 используется
символ 275, соответствующий классу длин 51-58,
и смещение 56-51 = 5, записываемое в двоичном виде
тремя битами как "110". То есть в выходной кодовой
последовательности будут следующие биты:
-------------------------+------
код Хаффмана символа 275 | "110"
-------------------------+------
Блок типа "01", использующий статические коды Хаффмана
для двух алфавитов, не содержит записи кодов/деревьев
Хаффмана, они постоянные и определены в стандарте
RFC1951 следующими таблицами. Для алфавита
литералов и длин используется таблица:
Lit Value Bits Codes
--------- ---- -----
0 - 143 8 00110000 through
10111111
144 - 255 9 110010000 through
111111111
256 - 279 7 0000000 through
0010111
280 - 287 8 11000000 through
11000111
Для алфавита дистанций символы от 0 до 31 кодируются
5-ю битами (символы с равными вероятностями, коды
одинаковой длины) с дополнительными последовательностями
битов, как и в таблице для динамических кодов, которая
была приведена выше.
Сложнее всего разобраться, как передается информация
о дереве и кодах Хаффмана в случая динамических
кодов Хаффмана для блока типа "10".
Два замечания. Если мы знаем дерево Хаффмана (дерево
префиксных кодов), то мы знаем и коды всех символов
алфавита. Пример: алфавит из символов A,B,C,D и дерево
/\
B /\
A /\
C D
дает коды символов как пути от корня к листьям дерева,
в котором ребра к левому узлу-сыну помеченны битом 0,
к правому сыну -- битом 1. В данном случае коды
следующие:
A 10
B 0
C 110
D 111
Но верно и обратное утверждение!
Если мы знаем префиксные коды для всех символов алфавита,
то мы можем построить по ним и дерево Хаффмана.
Например, в случае кодов
A 10
B 0
C 110
D 111
мы сначала строим путь к листу A:
\ 1
/ 0
A
затем в том же (полностью сбалансированном) дереве
отмечаем путь к листу B
0 /
B
затем к C
\ 1
\ 1
/ 0
C
и к D:
\ 1
\ 1
\ 1
D
Объединяя все эти пути, получаем
кодовое дерево:
/\
B /\
A /\
C D
Мораль: для задания кодового дерева достаточно
задать префиксные коды всех символов алфавита.
Второе замечание
Минимальных деревьев и кодов Хаффмана для данного
распределения вероятностей символов может быть
несколько, достаточно, например, заменить
нули на единицы и единицы на нули, в нашем примере
получим:
/\
/\ B
/\ A
D c
В алгоритме Deflate накладываются два дополнительных
условия на деревья:
1) коды меньшей длины лексикографически предшествуют
кодам большей длины. Например, в последнем дереве
код символа B равен "1", а код символа A равен
"01", и "1" > "01", т.е. это условие НЕ ВЫПЛНЯЕТСЯ;
2) коды одинаковый длины идут в последовательном
порядке (соответствующем двоичной записи чисел,
отличающихся на единицу), причем порядок
соответствует порядку символов в алфавите (мы
считаем, что символы алфавита упорядочены,
и для двух символов с кодами одинаковой длины
меньший код соответствует меньшему символу).
В нашем случае это условие также НЕ ВЫПОЛНЯЕТСЯ:
код D = "000"
код С = "001"
Символ С в нашем алфавите предшествует
символу D, но код C больше кода D.
Напротив, дерево
/\
B /\
A /\
C D
удовлетворяет обоим условиям.
Оказывается, если дерево кодов Хаффмана удовлетворяет
обоим дополнительным условиям, то выполняется
следующее утверждение.
Теорема. Дерево Хаффмана, удовлетворяющее
приведенным выше двум дополнительным условиям,
однозначно определяется длинами кодов для всех
символов алфавита.
То есть достаточно задать длины кодов, и только по этой
информации дерево кодов Хаффмана и сами коды
однозначно восстанавливаются.
Пример (приведенный в документе RFC 1951).
Рассмотрим алфавит A,B,C,D,E,F,G,H, и пусть известно,
что длины кодов символов этого алфавита равны
A B C D E F G H
3 3 3 3 3 2 4 4
Восстановим дерево, проиллюстрировав процесс на
картинке:
Напишем на Python3 программу, которая восстанавливает
минимальное дерево кодов Хаффмана (точнее, сами
эти коды -- согласно первому замечанию, по кодам
легко построить и кодовое дерево). Реализуем функцию,
которая по алфавиту (списку символов) и списку длин кодов
символов алфавита восстанавливает коды этих символов.
class HuffmanCode:
def __init__(
self, symbol = "", length = 0, code = 0
):
self.symbol = symbol;
self.length = length;
self.code = code;
def __repr__(self):
c = "";
if self.length > 0:
mask = 1 << (self.length - 1)
while mask != 0:
bit = (mask & self.code)
if bit != 0:
c += '1'
else:
c += '0'
mask >>= 1
return self.symbol + ": " + c
def __str__(self):
return repr(self)
def huffmanCodes(alphabet, codeLengths):
'''Compute the Huffman codes for given alphabet
by the list of code lengths of alphabet symbols'''
# Define the numbers of codes of given length.
# bl_count[l] = number of codes of length l
numSymbols = len(alphabet)
maxCodeLen = max(codeLengths)
hCodes = []
for i in range(numSymbols):
hCodes.append(
HuffmanCode(
alphabet[i],
codeLengths[i],
0
)
)
# print("hCode =", hCodes)
# Stage 1. Count number of codes of length l.
bl_count = [0]*(maxCodeLen + 1)
for l in codeLengths:
bl_count[l] += 1
# print("bl_count =", bl_count)
# Stage 2. Compute the first code of lenght l:
# next_code[bit_length]
next_code = [0]*(maxCodeLen + 1)
for l in range(1, maxCodeLen + 1):
next_code[l] = (
next_code[l - 1] +
bl_count[l - 1]
)*2
# print("next_code =", next_code)
# Stage 3. Compute the huffman codes for all symbols
for i in range(numSymbols):
l = codeLengths[i]
if l > 0:
hCodes[i].code = next_code[l]
next_code[l] += 1
# print("hCodes =", hCodes)
return hCodes
Вот пример использования этой функции, вычисляющей
коды Хаффмана для алфавита A,B,C,D,E,F,G,H и длин
кодов символов этого алфавита 3,3,3,3,3,2,4,4
(этот пример мы рассмотрели ранее на картинке):
>>> alpha = "ABCDEFGH"
>>> alphabet = [alpha[i] for i in range(len(alpha))]
>>> codeLengths = [3, 3, 3, 3, 3, 2, 4, 4]
>>> hc = huffmanCodes(alphabet, codeLengths)
>>> hc
[A: 010, B: 011, C: 100, D: 101, E: 110,
F: 00, G: 1110, H: 1111]
Результат совпадает с тем, который мы получили
на картинке, а также с результатом, приведенном
в документации RFC 1951.
Итак, понятно, что для записи деревьев Хаффмана
для обоих алфавитов (алфавита литералов/длин и
алфавита дистанций) мы должны записать длины
префиксных кодов сначала для всех символов
первого алфавита, затем второго. Опять же,
эта запись получилась бы достаточно длинной,
поэтому и для нее снова применяются коды Хаффмана
(только для записи самих деревьев, не для контента!).
Эта запись в некотором смысле эмулирует кодировку RLE
(Run Lengths Encoding -- кодирование участков,
содержащих одинаковые повторяющиеся символы).
Используем коды Хаффмана для записи длин других
кодов Хаффмана (для алфавита литералов/длин фраз
и для алфавита дистанций). Алфавит для записи
длин кодов следующий:
0 - 15: Represent code lengths of 0 - 15
16: Copy the previous code length 3 - 6 times.
The next 2 bits indicate repeat length
(0 = 3, ... , 3 = 6)
Example: Codes 8, 16 (+2 bits 11),
16 (+2 bits 10) will expand to
12 code lengths of 8 (1 + 6 + 5)
17: Repeat a code length of 0 for 3 - 10 times.
(3 bits of length)
18: Repeat a code length of 0 for 11 - 138 times
(7 bits of length)
Как видим, всего в этом алфавите 18 символов, и он
ориентирован на записи последовательностей повторяющихся
длин. В алгоритме Deflate максимальная длина
кодов Хаффмана для алфавитов литералов/длин и дистанций
не превышает 15. Символы 0..15 в алфавите длин
соответствуют длинам 0-15. Символ 16 означает повторение
предыдущего символа (для длины кодовой последовательности)
от 3 до 6 раз, при этом количество повторений
задается с помощью дополнительной битовой
последовательности, в случае символа 16 эта
последовательность состоит из 2-х битов (числа 0..3),
таким образом число повторений равно 3 + дополнительное
число. Например, число повторений 5 кодируется как
---------------+-----
код символа 16 | "10"
---------------+-----
(дополнительные биты "10" представляют число 2
в двоичной записи, число повторений 5 = 3 + 2).
Другой пример: число повторений 50 кодируется
символом 18 (соответствующим повторениям от 11 до
138 раз) и дополнительными 7 битами, которые представляют
двоичную запись числа 50 - 11 = 39 --
это биты "0100111":
---------------+----------
код символа 18 | "0100111"
---------------+----------
Интересно, что длины кодов Хаффмана для дерева
длин кодов, алфавит которого содержит 19 символов
от 0 до 18, записываются не подряд, а в порядке
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3,
13, 2, 14, 1, 15.
Сам блок с динамическими кодами Хаффмана
(блок типа "10") имеет следующий формат:
5 Bits: HLIT, # of Literal/Length codes - 257 (257 - 286)
5 Bits: HDIST, # of Distance codes - 1 (1 - 32)
4 Bits: HCLEN, # of Code Length codes - 4 (4 - 19)
(HCLEN + 4) x 3 bits: code lengths for the code length
alphabet given just above, in the order: 16, 17, 18,
0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
These code lengths are interpreted as 3-bit integers
(0-7); as above, a code length of 0 means the
corresponding symbol (literal/length or distance code
length) is not used.
HLIT + 257 code lengths for the literal/length alphabet,
encoded using the code length Huffman code
HDIST + 1 code lengths for the distance alphabet,
encoded using the code length Huffman code
The actual compressed data of the block,
encoded using the literal/length and distance Huffman
codes
The literal/length symbol 256 (end of data),
encoded using the literal/length Huffman code
Коротко говоря, сначала идет запись деревьев,
причем первым записывается дерево для представления
деревьев, с его помощью записывается сначала дерево
для алфавита литералов/длин фраз, затем дерево
дистанций, и только потом записываются коды содержимого
входной последовательности байтов в форме
литерал, литерал, длина, дистанция,
литерал, длина, дистанция, длина, дистанция,
длина, дистанция, литерал, литерал,
длина, дистанция, литерал, ...,
стоп-символ.
Стоп-символом (символ 256) кончается любой
блок типа 01 или 10.
Последовательность блоков кончается финальным блоком
с первым битом 1 (блоки, предшествующие последнему,
начинаются с бита 0).
На этом мы закончим описание формата Deflate.