Как восстановить динамическое дерево Хаффмана из DEFLATE - PullRequest
Новая
       50

Как восстановить динамическое дерево Хаффмана из DEFLATE

0 голосов
/ 04 ноября 2018

Этот вопрос относится к разделу 3.2.7 RFC-1951 о восстановлении динамического дерева Хаффмана.

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

Например, вот rgb (255,0,0) 50x50 png, где IDAT - это динамическое дерево Хаффмана из DEFLATE. 

0000024: xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx  CIDATx
000002a: xxxxxxxx 11101101 11001111 00110001 00010001 00000000  ...1..
0000030: 00000000 00001000 00000000 10100001 11101111 01011111  ....._
0000036: 01011010 00110011 10111000 01111010 00001100 00000100  Z3.z..
000003c: 10100000 10101001 11111001 00100000 00010001 00010001  ... ..
0000042: 00010001 00010001 00010001 00010001 00010001 00010001  ......
0000048: 00010001 00010001 00010001 00010001 00010001 00010001  ......
000004e: 00010001 00010001 00010001 00010001 00010001 00010001  ......
0000054: 00010001 00010001 00010001 00010001 00010001 00010001  ......
000005a: 00010001 00010001 00010001 00010001 00010001 00010001  ......
0000060: 00010001 00010001 00010001 00010001 00010001 10010001  ......
0000066: 10001011 00000101 10110000 00110011 01110101 10010110  ...3u.
000006c: 01111001 11000101 00011100 10110001 00000000 00000000  y.....
0000072: 00000000 00000000 01001001 01000101 01001110 01000100  ..

infgen создает этот заголовок: 

last
dynamic
litlen 0 2
litlen 255 4
litlen 256 4
litlen 274 4
litlen 283 4
litlen 285 1
dist 3 1
dist 15 1

... цель состоит в том, чтобы понять биты и процессы для восстановления динамического дерева ...

Первые три бита описывают заголовок DEFLATE. 

101 <- last block bit, tree type is dynamic.

Следующие четырнадцать битов описывают HLIT, HDIST и HCLEN. 

11101 <- HLIT,  29 + 257 = 286 
01111 <- HDIST, 15 + 1 = 16
1110 <- HCLEAN, 14 + 4 = 18

Что эти значения описывают в динамическом дереве Хаффмана?

Затем, читая три бита за раз и следуя таблице перестановок ... длина оказывается равной ...

Lengths: [4, 2, 4, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 2] (строка 697 puff.c )

Используются ли эти длины для определения литералов?

Ответы [ 3 ]

0 голосов
/ 05 ноября 2018

Заголовок содержит длины битов литерала Deflate (0-255), длины (256-285) и кодов расстояния (0-29). Если вам известны их битовые длины, вы можете перестроить дерево, следуя алгоритму в Разделе 3.2.2 RFC1951. Найдите шаги, которые начинаются с «Подсчитать количество кодов для каждой длины кода ...»

Однако значения длины в битах также кодируются с помощью Хаффмана с использованием от 0 до 7 бит. Сначала нужно открыть таблицу HCLEN, используя тот же алгоритм, что и выше. Раздел 3.2.7 объясняет это.

Зачем кодировать заголовок дважды как таковой? Сделать динамический заголовок Хаффмана маленьким.

0 голосов
/ 06 ноября 2018

Больше информации ... следующие 14 битов ... 

5 Bits of HLIT, the Literal/Length codes - 257 (257 - 286)
5 Bits of HDIST, the Distance codes - 1        (1 - 32)
4 Bits of HCLEN, the Code Length codes - 4     (4 - 19)

From the example:
  HLIT => 29 + 257 = 286, HDIST => 15 + 1 = 16, HCLEN => 14 + 4 = 18

Теперь соберите 3-битные значения HCLEN раз. Следуя порядку таблицы перестановок (стр. 13 из RFC-1951.) 

permuted ordering: [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15]

From the example: 
   HCLEN is 18 => 18*3 = 54-bits.
   lengths: [ 4 2 4 0 2 0 0 0 0 0 0 0 0 0 0 0 0 3 2 ]

Затем распакуйте эти трехбитовые значения. Эта распаковка содержит инструкции по как для построения динамического дерева Хаффмана ... «Для еще большей компактности сами последовательности длины кода сжимаются с использованием кода Хаффмана». 

To unpack the triple-bit values: (examples below)
  1. Count the number occurrences of the values.
  2. Determine the offset, the count plus the previous offset.
  3. Determine the symbols. 
     A symbol is placed at the offset value, which is found at a length value. 
     After placing a symbol, increment the offset.


From the example: 
    LENGTHS: [ 4 2 4 0 2 0 0 0 0 0 0 0 0 0 0 0 0 3 2 ] //the three-bits from HCLEN
    COUNT: [ 13 0 3 1 2 0 0 0 0 0 0 0 0 0 0 0 ] //the occurrences of lengths.
      i.e, 0 occurs 13 times, 1 occurs 0 times, 2 occurs 3 times...
    OFFSET: [ x 0 0 3 4 6 6 6 6 6 6 6 6 6 6 6 ] //the count plus the previous offset.
      i.e, o[2] = 0 + 3, o[3] = 3 + 1, o[4] = 4 + 0...
    SYMBOL: [ 1 4 18 17 0 2 ] //use length to index offset to place symbol
      i.e, if i=1, s[off[len[i]]] = s[off[len[2]]] => s[off[0]] => s[0] = 1, increment off[0]...

... Символы теперь определены. Далее декодируем биты для построения динамического дерева Хаффмана…

0 голосов
/ 04 ноября 2018

Что эти значения описывают в динамическом дереве Хаффмана?

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

Далее следуют восемнадцать кодовых длин кодов (по три бита каждый), за которыми следуют 286 буквенных / длинных кодов и затем шестнадцать кодов расстояний, все они кодируются с использованием кода кодовой длины .

Используются ли эти длины для определения литералов?

Нет. Трехбитовые длины предназначены для кодов длины кода. Вам нужно создать этот код только для того, чтобы прочитать следующие длины буквенных / длинных и дистанционных кодов, которые сами сжимаются с использованием этого кода.

Это описано в разделе 3.2.7 RFC 1951:

«Для еще большей компактности сами последовательности кодов сжимаются с использованием кода Хаффмана».

...