Алгоритм сжатия данных Deflate
Алгоритм Deflate используется в самых популярных
архиваторах: ZIP, GZIP, в формате изображений
*.png (Portable Network Graphics -- сжатие изображений
БЕЗ ПОТЕРИ ИНФРМАЦИИ), в сжатии HTML (Web) и т.д.
Алгоритм Deflate базируется на LZ77, причем в его
начальном варианте, как он был опубликован в 1977 г.
в статье Lempel, Ziv (для того, чтобы обойти патенты
на более поздние его вариации типа LZ77SS ???).
Он совершенно свободный. Описание алгоритма содержится в
документе Deflate RFC1951 (Request For Comments).
Главная идея: сначала применяем алгоритм кодирования
LZ77, и потом к полученному потоку данных применяются
коды Хаффмана (статические или динамические).
Вспомним алгоритм кодирования LZ77. Основная идея
LZ77 -- не передавать полностью фрагменты текста,
которые уже встречались раньше, а просто передавать
ссылки на них. Ссылка -- это смещение назад
(или distance, back distance) и длина фрагмента,
это пара целых чисел; и дополнительно передается
следующий за фрагментом байт (литерал, literal).
Таким образом, исходный поток байтов преобразуется
в поток троек:
(обратная дистанция к фрагменту,
длина фрагмента, следующий байт)
Давайте закодируем строку "BARBARA".
Кодировщик в процессе работы хранит часть уже
обработанных символов из входного потока, точнее
его хвост (конец) длиной Window символов (не
обязательно хранить все прочитанные символы,
в Deflate размер скользящего равен 32768 = 2^15.
Кроме того, есть еще Look-ahead buffer (буфер
предварительного просмотра, в Deflate его
минимальная длина 258 + 1, в алгоритме Deflate ищутся
фразы длиной не более 258).
Еще раз повторим LZ77 для строки "BARBARA". Будем
отмечать текущую позицию (первый необработанный символ
входного потока) квадратными скобками:
1) [B]ARBARA
(0, 0, B)
2) B[A]RABARA
(0, 0, B) (0, 0, A)
3) BA[R]BARA
(0, 0, B) (0, 0, A) (0, 0, R)
4) BAR[B]ARA
(0, 0, B) (0, 0, A) (0, 0, R) (3, 3, A)
5) BARBARA[]
(0, 0, B) (0, 0, A) (0, 0, R) (3, 3, A)
завершение.
Результат: строка "BARBARA" кодируется
последовательностью троек чисел
(0, 0, B) (0, 0, A) (0, 0, R) (3, 3, A)
(в реальности передаются не буквы, а их
байтовые коды:
(0, 0, 66), (0, 0, 65), (0, 0, 82), (3, 3, 65)
)
Еще примеры:
>>> s = "don't trouble trouble until trouble troubles you"
>>> x = bytes(s, "ascii")
>>> x
b"don't trouble trouble until trouble troubles you"
>>> y = encodeLZ77(x)
>>> y
[(0, 0, 100), (0, 0, 111), (0, 0, 110), (0, 0, 39),
(0, 0, 116), (0, 0, 32), (0, 0, 116), (0, 0, 114),
(0, 0, 111), (0, 0, 117), (0, 0, 98), (0, 0, 108),
(0, 0, 101), (8, 9, 117), (0, 0, 110), (0, 0, 116),
(0, 0, 105), (0, 0, 108), (22, 16, 115), (0, 0, 32),
(0, 0, 121), (0, 0, 111), (0, 0, 117)]
>>> len(y)
23
>>> len(x)
48
Мы видим, что исходная последовательность байтов длины 48
кодируется последовательностью троек длины 23, более чем
в 2 раза короткой.
Проверим работу декодировщика:
>>> xx = decodeLZ77(y)
>>> xx
bytearray(b"don\'t trouble trouble until trouble troubles you")
>>> x == xx
True
Получили исходную последовательность байтов.
Проблема: мы получаем последовательность троек
чисел:
(distance, length, byte)
-- обратное расстояние, длина фразы, следующий символ.
Эти числа имеют следующие диапазоны в алгоритме Deflate:
1 <= distance <= 32768
3 <= length <= 258
0 <= byte <= 255
Если попросту передавать числа как 2-байтовые
последовательности, мы вряд ли получим хорошее сжатие.
Идея: к выходной последовательности алгоритма LZ77
применяется кодирование Хаффмана. Кодирование Хаффмана
применяется к символам фиксированного алфавита.
Вторая идея: например, distance имеет 32768 значений.
Это слишком большой алфавит, и мы его сокращаем до
30 элементов. Каждый элемент будет соответствовать
некоторому диапазону величин distance. Вслед за
номером диапазона (т.е. кодом символа нашего
алфавита) мы будем передавать дополнительные биты,
указывающие величину числа. Конкретно, для расстояний
используется следующий алфавит и дополнительно
число битов для каждого элемента алфавита
(см. документ RFC1951):
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
Например, для передачи дистанции 52 надо передать
код Хаффмана для символа 11, который соответствует
дистанциям от 49 до 64, и затем передать 4 бита,
в которых записано число 3 (поскольку 52-49=3),
его двоичная запись 0011. Например, пусть код
Хаффмана символа 11 равен XXXXX, тогда передается
последовательность битов
XXXXX 0011
Отметим, что выходной поток -- это не
поток байтов, а поток битов.
Два алфавита
В алгоритме Deflate используются два алфавита
для построения и использования кодов Хаффмана:
1) алфавит для величин байтов (литералов),
чисел от 0 до 255, стоп-символа -- число 256,
и дальше символы для величин длины фразы
(длины фраз меняются от 3 до 258);
2) второй алфавит -- для дистанций (величины
смещений от 1 до 32768).
Почему 2 разных алфавита? Слишком различаются диапазоны
дистанций с кодами байтов и длин фраз. С другой стороны,
коды байтов (литералы) и длины фраз имеют примерно
одинаковые диапазоны, и разумно объединть их в один
алфавит. Для кодировки длин фраз также используются
дополнительные биты:
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
Таблица указывает, что символы от 257 до 285
первого алфавита кодируют длины фраз: символы от 257
до 264 кодирую длины от 3 до 10, символ 265 кодирует
длины 11 и 12, при этом передается 1 дополнительный бит,
равный 0 для длины 11 и 1 для длины 12, и так далее
в соответствии с таблицей. Например, для длины 110
передается код Хаффмана символа 279 и дополнительные
4 бита, кодирующие число 11 (двоичная запись 1011),
поскольку 110 - 99 = 11:
XXX 1011
где XXX -- код Хаффмана символа 279.
Символы от 0 до 255 в первом алфавите (алфавите литералов
и длин) соответствуют литералам (величинам байтов,
т.е. числам от 0 до 255). Символ 256 -- "стоп символ",
который означает конец блока, на нем блок заканчивается.
И дальше идут перечисленные выше коды для длин фраз.
Блоки в алгоритме Deflate и
общее описание алгоритма кодирования
Выходной поток (битов, не байтов!) оформляется
как последовательность блоков. Блоки не зависят
друг от друга. Блок начинается с трех битов
в LSB порядке (младший бит Least Significat Bit
передается первым -- от младших битов к старшим):
1) первый бит 1 означает, что это последний (final)
блок, 0 -- что будет блок продолжения;
2) второй и третий биты означают тип блока:
-- 00 означает, что блок не сжимается, т.е.
байты передаются так, как они идут в
исходном потоке байтов без иизменений.
Размер такого блока не превышает
2^16 = 65536 байтов (последовательность
байтов выравнивается по границе байта).
Формат такого блока:
---------------------========================
0/1 00 xxxxx LEN NLEN массив байтов длины len
---------------------========================
-- 01 означает, что применяется кодирование Хаффмана
к двум указанным выше алфавитам с применением
статических кодов Хаффмана, определенных
в стандарте алгоритма Deflate. Информация
о кодовых деревьях и кодах символов вообще
не передается внутри такого блока, поскольку
она стандартная (и это уменьшает длину
выходного потока).
-- 10 означает, что применяются динамические коды
коды и деревья Хаффмана для обоих алфавитов
(алфавита литералов+длин и алфавита дистанций).
В начале блока указывается информация о
деревьях Хаффмана для обоих
алфавитов -- сначала для алфавита
литералов+длин и затем для алфавита дистанций.
И затем блок содержит коды Хаффмана для
закодированной последовательности, полученной
алгоритмом LZ77 в следующем порядке:
литерал либо
пара длина фразы, дистанция к этой фразе
(литералов может быть много или их вообще
может не быть!). Например,
литерал, литерал, длина, дистанция,
литерал, длина, дистанция, длина, дистанция,
литерал, ..., стоп-символ.
Ключевой и самый сложный момент в понимании алгоритма
Deflate -- это способ передачи деревьев и кодов
Хаффмана. Отметим, что по заданным вероятностям
или частотам можно построить много деревьев Хаффмана,
эквивалентных в смысле минимальной средней длины
кодов сообщений. Например, пусть мы имеем алфавит из
4-х символов A, B, C, D с частотами 3, 4, 1, 1.
Дерево Хаффмана может быть таким:
/\
/\ B
A /\
C D
Коды символов в этом случае будут следующими:
A 00
B 1
C 010
D 011
Но можно построить и другое минимальное дерево:
/\
B /\
A /\
C D
Коды:
A 10
B 0
C 110
D 111
Коды и деревья Хаффмана в алгоритме Deflate
обладают двумя дополнительными свойствами:
1) более короткие коды лексикографически
предшествуют более длинным кодам;
2) коды равной длины идут подряд последовательно
и соответствуют порядку символов в алфавите
(символ, соответствующий следующему коду,
лексикографически больше, чем текущий символ).
В приведенных двух примеах второе дерево удовлетворяет
этим свойствам, а первое нет.
Самое интересное утверждение:
Теорема.
Если дерево и коды Хаффмана удовлетворяют
указанным двум дополнительным свойствам,
то они однозначно определяются массивом
длин кодов, соответствующих символам алфавита.
В рассмотренном втором примере длины кодов равны
2, 1, 3, 3:
символ код длина кода
A 10 2
B 0 1
C 110 3
D 111 3
Теорема утверждает, что дерево однозначно определяется
длинами кодов 2, 1, 3, 3. Поэтому в алгоритме Deflate
для задания деревьев передаются массивы длин кодов
символов (индекс в массиве соответствует
номеру символа в алфавите, начиная с нуля).
Почему это так? Попробуем объяснить на картинке.
Рассмотрим алфавит {A,B,C,D,E,F,G,H}. Пусть
длины кодов Хаффмана для букв алфавита равны
3,3,3,3,3,2,4,4 соответственно. Построим дерево
кодов Хаффмана, пользуясь исключительно этой
информацией:
;