В этой части мы, как и в первой, распакуем файл gzip вручную, но теперь ещё и декодируем коды Хаффмана.

Для начала запишем данные на диск:

$ echo "hector the frantic father on an anchor or a rare fat cat sat on the ranch" > test-huff.txt
$ xxd test-huff.txt
00000000: 6865 6374 6f72 2074 6865 2066 7261 6e74  hector the frant
00000010: 6963 2066 6174 6865 7220 6f6e 2061 6e20  ic father on an
00000020: 616e 6368 6f72 206f 7220 6120 7261 7265  anchor or a rare
00000030: 2066 6174 2063 6174 2073 6174 206f 6e20   fat cat sat on
00000040: 7468 6520 7261 6e63 680a                 the ranch.

На этот раз файл получился размером 74 байта и содержит 13 символов:

a, c, e, f, h, i, n, o, r, s, t; пробел (0x20) и перевод каретки (0x0a).

В этой строке есть много повторений. Надеюсь, gzip это учтёт. Поскольку я работаю под Windows, то для распаковки использовал 7zip-zstd.

$ 7z a -mx9 test-huff.txt.gz .\test-huff.txt
$ xxd test-huff.txt.gz
00000000: 1f8b 0808 d76f 6565 0200 7465 7374 2d68  .....oee..test-h
00000010: 7566 662e 7478 7400 158b 410a 0031 0c02  uff.txt...A..1..
00000020: effb 0abf 2621 257b 69c1 e6ff d480 1e64  ....&!%{i......d
00000030: c6ca e823 7425 96b8 fb0f 2c7a 0967 8393  ...#t%....,z.g..
00000040: 2873 8710 9543 11ee 75ad cc51 237d 0fc7  (s...C..u..Q#}..
00000050: 9797 d64a 0000 00                        ...J...

Чтобы вы лучше поняли, как будет выглядеть декодирование, покажу первую строку декодированного потока gzip:

0101 1001 0001 1101 00111 010 000 1101 0101 1001 000
h    e    c    t    o     r   ' '   t    h  e    ' ' 

Ну а подробности читайте далее.

Информация gzip

Первые байты вполне понятны:

• 1f8b — «магический», жёстко закодированный заголовок gzip.
• 08 — означает метод сжатия DEFLATE.
• 08(00001000) — бит 3 установлен, значит, будет присутствовать имя файла.
• d76f 6565 — временна́я метка 1701146583, UTC Tue Nov 28 04:43:03 2023
• 02 — использование самого медленного метода сжатия.
• 00 — операционная система Windows (пригождается для LF/CLRF). Да, я пишу файлы в Windows, так как недавно перестал использовать WSL, потому что в моём ноутбуке всего 8 ГБ RAM, чего сегодня для Windows явно недостаточно. Планирую приобрести Mac в рамках предстоящей «Чёрной пятницы».

Следующие несколько байтов содержат имя файла:

74 65 73 74 2d 68 75 66 66 2e 74 78 74 00
t  e  s  t  -  h  u  f  f  .  t  x  t  NUL

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

На этот раз мы пойдём другим путём. Наш текущий файл намного больше предыдущего, который составлял 9 байт, к тому же мы будем декодировать коды Хаффмана, что может оказаться довольно запутанным процессом. В связи с этим я решил использовать программу infgen, написанную соавтором самого gzip, Марком Адлером. Infgen способна декодировать файл gzip и сообщать информацию о каждом его байте. Благодарю Rendello с Hackenews за то, что посоветовал её.

Примечание: infgen требует наличия в системе zlib, что в случае с Windows может оказаться проблематичным. Мне пришлось установить MSYS и использовать команду gcc ./infgen.c -lz -o ./infgen

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

$.\infgen.exe -dd .\test-huff.txt.gz
! infgen 3.2 output
!
gzip
!
last                    ! 1
dynamic                 ! 10
count 259 12 16         ! 1100 01011 00010
[... additional output trimmed. See appendix for the full output]

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

Мы не будем разбирать этот поток битов подробно, я лишь вкратце уточню, что он представляет данные после обработки алгоритмом DEFLATE, без байтов заголовков, CRC и Length (длины). Напомню, что биты здесь упакованы в порядке от младшего (LSB, Least Significant Bit) к старшему (MSB, Most Significant Bit), а все целые числа интерпретируются с прямым порядком байтов (за исключением кодов Хаффмана, которые упаковываются в порядке от старшего бита к младшему). xxd выводит биты от старшего к младшему, поэтому читать их поток нужно в обратном направлении. Подробнее об этом сказано также в первой части проекта.

$ xxd -s 24 -l 55 -b .\test-huff.txt.gz
00000018: 00010101 10001011 01000001 00001010 00000000 00110001  ..A..1
0000001e: 00001100 00000010 11101111 11111011 00001010 10111111  ......
00000024: 00100110 00100001 00100101 01111011 01101001 11000001  &!%{i.
0000002a: 11100110 11111111 11010100 10000000 00011110 01100100  .....d
00000030: 11000110 11001010 11101000 00100011 01110100 00100101  ...#t%
00000036: 10010110 10111000 11111011 00001111 00101100 01111010  ....,z
0000003c: 00001001 01100111 10000011 10010011 00101000 01110011  .g..(s
00000042: 10000111 00010000 10010101 01000011 00010001 11101110  ...C..
00000048: 01110101 10101101 11001100 01010001 00100011 01111101  u..Q#}
0000004e: 00001111 

.

Начнём с кодов Хаффмана

Думаю, что вместо декодирования таблицы Хаффмана информативнее будет двигаться от конца к началу. Поэтому начнём с заключительной таблицы, и потом разберём, как она кодируется с использованием только длины кодов. Затем мы посмотрим, как кодируются эти длины, используя схему кодировки Run-length (RLE, протяжённость серии), которая сама кодируется с помощью кодов Хаффмана.

▍ Таблица Хаффмана

Я намеренно ограничил содержимое файла 13 символами. Теперь посмотрим, как они были закодированы.

Ещё раз обращу ваше внимание. Поскольку коды Хаффмана упаковываются в порядке от старшего бита к младшему, infgen даёт развёрнутый вывод.

Эти коды, выстраиваясь по частоте вхождения символа в исходном материале, почти формируют красивый префиксный код Хаффмана. Но здесь есть разрывы, потому что gzip использует особый приём для повышения степени сжатия — совмещает литералы и длины в один алфавит Хаффмана. Это позволяет дополнительно сэкономить пространство вместо того, чтобы кодировать эти элементы с помощью двух отдельных кодов Хаффмана.

Под длинами подразумеваются длины последовательностей (match), то есть прохождение N шагов в обратном направлении. Ниже мы разберём этот процесс подробнее.

Тем не менее по неясной для меня причине расстояние кодируется с помощью отдельного алфавита. К чему это недоумение? ¯\(ツ)/¯ …

Полное дерево Хаффмана len/lit получается таким:

Канонизация кода Хаффмана

Заметьте, поскольку мы написали коды Хаффмана в порядке возрастания, нам не обязательно конкретно указывать биты. Если мы просто будем знать длину кода каждого символа, то сможем в точности воссоздать этот код.

Рассмотрим символы с длиной 3: пробел, a, r, 3. Они выстроены в алфавитном порядке (по ASCII), охватывая коды от 000 до 011. Символы с длиной 4, а именно c, e, h, t, также перечислены в алфавитном порядке и представлены кодами от 1000 до 1011.

Эта техника называется каноническим кодированием Хаффмана и представляет очень крутой приём для выражения кодов. По сути, любое кодирование по методу Хаффмана, даже в других форматах сжатия, работает таким образом. Если вам этот момент не до конца ясен, не поленитесь почитать статью в Википедии по прикреплённой ссылке.

Получается, мы можем представить наши коды Хаффмана так:

И при их декодировании нам нужно лишь передать длины кодов — так мы поймём, как воссоздать изначальный код Хаффмана. Алфавит len/lit простирается от 0 до 285, значит, можно представить наш код в виде массива длиной 286 элементов:

0,0,0,0,0,0,0,0,0,0,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,3,0,4,0,4,5,0,4,6,0,0,0,0,5,5,0,0,3,5,4,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
5,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

Но это крайне накладный вариант. Только посмотрите на все эти нули в середине, которые так и просят, чтобы их закодировали с помощью RLE. Это мы и сделаем. Нам нужна такая кодировка RLE, которая будет просто отражать количество нулей, сопровождаемое длиной кода. При этом 1-2 нуля будут кодироваться стандартно. Что-то вроде этого:

zeros 10, codelengths 6,
zeros 21, codelengths 3,
zeros 64, codelengths 3 0 4 0 4 5 0 4 6,
zeros 4, codelengths 5 5 0 0 3 5 4,
zeros 138, codelengths 0 5 3 4
rest zeroes

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

• Код от 0 до 15 представляет длину. Имейте в виду, это означает, что максимальная длина кода len/lit будет 15.
• 17 и 18 используются для представления коротких и длинных последовательностей нулей соответственно, сопровождаясь фиксированным числом битов, указывающих количество этих нулей.
• 16 используется для обозначения повторений предыдущего элемента. В нашем случае отсутствует.

Разберём пример. Для этого мы представим код выше так:

17 [10] 6
18 [21] 3
18 [64] 3 0 4 0 4 5 0 4 6
17 [4] 5 5 0 0 3 5 4
18 [138] 0 5 3 4

Числа в скобках отражают фиксированное количество нулей и к длинам кодов не относятся.

В завершение нужно указать, как представлять коды от 0 до 18. Простейшей реализацией будет выразить их как фиксированные целые числа размером 5 бит. Но имейте в виду, что в нашем примере выше некоторые коды встречаются чаще других. Не будет ли грамотным решением сжать эти более частотные коды в меньшее число битов? Подождите-ка! Именно это и представляют из себя коды Хаффмана, и мы уже прописали весь механизм их обработки.

Итак, gzip представляет коды от 0 до 18, используя второй порядок кодов Хаффмана. Вот таблица длин кодов для нашего примера:

Эти длины кодов второго порядка (длины кодов длин кодов) далее кодируются в виде статических целых чисел размером 3 бита и выстраиваются в фиксированный 18-элементный массив.

2,0,4,2,3,3,4,0
0,0,0,0,0,0,0,0
0,4,4

Или должны были выстраиваться, если бы автор gzip не реализовал ещё один приём. Как мы видим, более значительные длины кодов, вроде 10-15, чаще представлены нулями. То же касается и наименьших длин вроде 1 и 2. Поэтому gzip «угадывает» ожидаемую частоту длин кодов и выстраивает их в порядке 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15. После этого он кодирует длину ненулевой части массива и отбрасывает все оставшиеся нули.

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

Получается, наши длины должны кодироваться в следующем порядке:

0,4,4,2,0,0,0,4
0,3,0,3,0,2,0,4
0,0,0

«Ненулевая» длина массива равна 16 (последние три элемента нули), и она кодируется отдельно в заголовке блока. Значит, мы можем просто отбросить три хвостовых элемента и получить битовую кодировку:

000 100 100 010 000 000 000 100
000 011 000 011 000 010 000 100

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

Этот момент не совсем ясен, но вроде работает всё именно так. Перед этим идут 17 бит, указывающие длины. Значит, наши 48 бит будут сжаты именно в таком виде, где x представляет неизвестные биты других частей кода gzip:

0100000x 00001010 00000000 00110001 00001100 00000010 xxxxxxx1

А вот и оно!

00000018: 00010101 10001011 01000001 00001010 00000000 00110001  ..A..1
                            ^^^^^^^  ^^^^^^^^ ^^^^^^^^ ^^^^^^^^ 
0000001e: 00001100 00000010 11101111 11111011 00001010 10111111  ......
          ^^^^^^^^ ^^^^^^^^        ^
00000024: 00100110 00100001 00100101 01111011 01101001 11000001  &!%{i.
0000002a: 11100110 11111111 11010100 10000000 00011110 01100100  .....d
00000030: 11000110 11001010 11101000 00100011 01110100 00100101  ...#t%
00000036: 10010110 10111000 11111011 00001111 00101100 01111010  ....,z
0000003c: 00001001 01100111 10000011 10010011 00101000 01110011  .g..(s
00000042: 10000111 00010000 10010101 01000011 00010001 11101110  ...C..
00000048: 01110101 10101101 11001100 01010001 00100011 01111101  u..Q#}
0000004e: 00001111                                               .

Можно выдохнуть!

Распаковка файла gzip

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

А мы перейдём к фактической распаковке кодов Хаффмана, так как это будет более информативно. Напомню, вот поток битов, где выделена первая строка раздела сжатых данных, продолжающаяся до самого конца.

00000018: 00010101 10001011 01000001 00001010 00000000 00110001  ..A..1
0000001e: 00001100 00000010 11101111 11111011 00001010 10111111  ......
00000024: 00100110 00100001 00100101 01111011 01101001 11000001  &!%{i.
0000002a: 11100110 11111111 11010100 10000000 00011110 01100100  .....d
00000030: 11000110 11001010 11101000 00100011 01110100 00100101  ...#t%
          ^        ^^^^^^^^ ^^^^^^^^ ^^^^^^^^ ^^^^^^^^ ^^^^^^^^ 
00000036: 10010110 10111000 11111011 00001111 00101100 01111010  ....,z
0000003c: 00001001 01100111 10000011 10010011 00101000 01110011  .g..(s
00000042: 10000111 00010000 10010101 01000011 00010001 11101110  ...C..
00000048: 01110101 10101101 11001100 01010001 00100011 01111101  u..Q#}
0000004e: 00001111                                               .

Вот первый раздел в декодированном виде:

0101 1001 0001 1101 00111 010 000 1101 0101 1001 000
h    e    c    t    o     r   ' '   t    h  e    ' ' 

01011 010 100 11011 1101 111111 0001 000 01011 100
f     r   a   n     t    i      c    ' ' f     a   

01 011 110
MATCH 3 14 (the)

Мы используем вывод infgen, где коды Хаффмана представлены в обратном порядке, чтобы облегчить их обнаружение в потоке битов. Если вы хотите сопоставить этот вывод с кодами, которые мы видели ранее, то просто разверните порядок его битов.

Сконцентрируемся на первой инструкции MATCH. Значение 110 представляет код Length/Lit для 257. Поскольку литералы занимают диапазон только от 0 до 255, это код длины, и он представляет последовательность длиной 3. Как далеко в обратном направлении нам нужно смотреть? Рядом с ним указан код расстояния, который также представлен в кодировке Хаффмана. Мы его не декодировали, но вот таблица этих кодов:

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

В примере выше с MATCH 3 14 мы видим, что код расстояния (infgen) равен 011. Это значение соответствует коду 7, из чего следует, что расстояние находится в диапазоне между 13 и 16 включительно. Следующие 2 бита дадут нам уже точное понимание. Поскольку это 01, значит нам нужно отсчитать назад 14 позиций.

Для нахождения последовательности мы отсчитываем 14 букв назад и видим 1101, или t. Значит, последовательность длиной 3 символа означает the. Всё верно — это часть слова father.

Продолжим:

010 000 00111 11011 000 100
r   ' ' o     n     ' ' a

001 0011
MATCH 4 3 (n an)

Здесь мы встречаем первую интересную последовательность. Заметьте, что она находится на расстоянии 3 букв от конца, но имеет длину 4. Таким образом gzip представляет повторяющийся элемент (в данном случае n) в самой последовательности.

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

Например, строку bananananana можно представить как b, a, n, match 9 2.

Завершим рассмотрение оставшегося кода, объединив всё:

0101 1001 0001 1101 00111 010 000 1101 0101 1001 000
h    e    c    t    o     r   ' '   t    h  e    ' ' 

01011 010 100 11011 1101 111111 0001 000 01011 100
f     r   a   n     t    i      c    ' ' f     a   

01 011 110
MATCH 3 14 (the)

010 000 00111 11011 000 100
r   ' ' o     n     ' ' a

001 0011
MATCH 4 3 (n an)

0001 0101 111 00 110       001 110
c    h    MATCH 3 32 (or ) MATCH 3 3 (or )

100 000 010 100 010 1001
a   ' ' r   a   r   e

101 00 0011        000 0001 101 110
MATCH 4 30 ( fat)  ' ' c    MATCH 3 4 (at )

10111 101 110 0010    10 110
s     MATCH 3 4 (at ) MATCH 3 35 (on )

1000 111 0011     010 0100 10 0011
MATCH 4 57 (the ) r   MATCH 4 37 (anch)

011111 01111
LF     END

Заключение

Крутой ликбез, не так ли? В процессе я сделал несколько интересных наблюдений:

• Обратите внимание, что к концу gzip полностью исключил все символы пробела.
• Сжатие начинается откровенно слабо, но постепенно его степень возрастает. Это касается всех кодировок на основе LZ77.
  
  • Несмотря на сей факт, по мере устремления строки к бесконечности LZ77 становится оптимальной кодировкой.
• Мы добились степени сжатия 74%, игнорируя заголовки и контрольные суммы. Вот вся структура файла в байтах:
  
  • Несжатых: 74
  • Данные DEFLATE: 55 (сжатие 74%)
    
    • Заголовок блока: 2.125 [17 бит]
    • Таблица RLE: 6 [48 бит]
    • Таблица LenLit: 13.125 [105 бит]
    • Расстояние: 3.625 [29 бит]
    • Сжатые данные: 30.125 [241 бит]
• И хотя об этом не говорилось, генерация таблицы Хаффмана из исходного текста выполняется с помощью алгоритма, ориентирующегося на плотность распределения символов.
• Заметьте, что мы совсем не рассмотрели сам процесс сжатия. Дело в том, что gzip и DEFLATE по факту представляют форматы, безразличные к методу сжатия. То есть вы при желании можете попробовать создать более эффективный gzip-компрессор.

Обобщение

Было весело! В этой статье мы рассмотрели, как коды Хаффмана упаковываются и свёртываются в небольшое количество бит с помощью двухэтапной кодировки. Теперь вы полностью готовы к тому, чтобы самостоятельно выполнить декодирование, поскольку это тот же процесс, только в обратном порядке. Если у вас возникнут сложности, все ответы можно найти в выводе infgen.
После этого мы использовали «декодированные» коды Хаффмана, чтобы полностью декодировать сжатый вывод, и попутно разобрали принцип работы MATCH.

Перспективы

1. Я по-прежнему не понимаю формат таблицы статистик infgen.
2. Может, как-нибудь напишу статью о том, как gzip определяет последовательности. Однако этот материал уже выйдет из области грамотно прописанных спецификаций, перейдя в область заметок по реализации, комментариев и самого исходного кода программы.
3. Также хочу дополнить серию статьёй, посвящённой использованию библиотеки сжатия LZ4, которая, как мне кажется, сильно недооценена.
4. Я, пожалуй, пока не буду заниматься анализом zstd, так как ещё нужно разобраться в кодировке tANS и понять, в чём смысл её использования. В простом примере, который мы только что рассмотрели, таблица последовательностей была не сильно большой, а zstd отличается лишь тем, что использует для кодов последовательностей tANS, для литералов он также использует коды Хаффмана. Так что мне пока не ясно, как это может улучшить сжатие.

Если найдёте какие-то ошибки, можете сообщить о них на GitHub или отписать мне на почту thomastayac@gmail.com

Приложение — весь вывод infgen

Скидки, итоги розыгрышей и новости о спутнике RUVDS — в нашем Telegram-канале ????