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

нужна помощь, чтобы понять, как работает DEFLATE Encoding. Я знаю, что это комбинация алгоритма LZSS и кодирования Хаффмана.

Так что пусть закодируют, например, "Deflate Later". Параметры: [Буфер поиска: 8 КБ и буфер просмотра вперед 4 КБ] Что ж, вывод алгоритма LZSS: «Deflate ‹5, 4>». На следующем этапе используется статическое кодирование Хаффмана для уменьшения избыточности. Вот моя проблема, я не знаю, как мне кодировать эту пару ‹5, 4> с помощью Хаффмана.

[Отредактировано]

D 000
f 001
l 010
a 011
t 100
_ 101
e 11

Итак, в соответствии с этой таблицей строка «Deflate» записывается как 000 11 001 010 011 100 11 101. В качестве следующего шага давайте закодируем пару (5, 4). Фиксированный префиксный код длиной 4 согласно книге "Сжатие данных - Полный справочник" равен 258, за которым следует фиксированный префиксный код длиной 5 (код 4 + 1 дополнительный бит).

Это можно резюмировать так:

длина 4 -> 258 -> 0000010
расстояние 5 -> 4 + 1 дополнительный бит -> 00100|0

Итак, закодированная строка записывается как [заголовок: 1 01] 000 11 001 010 011 100 11 101 0000010 001000 [конец блока: 0000000], НО если я создам дерево Хаффмана, это больше не будет статическим Хаффманом, правильно?

Добрый день


zip encoding huffman-code deflate
person FewG    schedule 01.07.2013    source источник
comment
Поскольку вы не спрашивали, как кодировать Deflate, вы должны уже знать, как генерировать коды Хаффмана для этих литералов. Вы делаете то же самое, выдавая длину 4 вместо литерала, за которой следует код расстояния 5.   -  person Mark Adler    schedule 01.07.2013
comment
Итак, в соответствии с этой таблицей строка Deflate записывается как 000 11 001 010 011 100 11 101. В качестве следующего шага давайте закодируем пару (5, 4). Фиксированный код префикса длины 4 в соответствии с книгой Data Compression - The Complete Reference равен 258, за которым следует код фиксированного префикса расстояния 5. [суммарно как]: длина 4 -> 258 -> 0000010 [7 бит] расстояние 5 -> 4 + 1 дополнительный бит -> 00100|0 Итак, закодированная строка записывается как [заголовок: 1 01] 000 11 001 010 011 100 11 101 0000010 001000 [конец блока: 0000000], НО если я создаю дерево хаффмана, это не статичный хаффман, верно?   -  person FewG    schedule 02.07.2013

Ответы (1)


arrow_upward
13
arrow_downward 

D 000
f 001
l 010
a 011
t 100
_ 101
e 11

не является статическим кодом Deflate. Все статические литеральные/длинные коды 7-, 8- или 9-битные, а дистанционные коды все 5-битные. Вы спрашивали о статических кодах.

«Deflate late», закодированный в статическом формате deflate, поскольку литералы «Deflate» и длина 4, расстояние 5 соответствуют в шестнадцатеричном виде:

73 49 4d cb 49 2c 49 55 00 11 00

Это разбито следующим образом (биты считываются из наименее значимой части каждого байта):

011 - 01 means fixed code, 1 means last block
00101110 - D
10101001 - e
01101001 - f
00111001 - l
10001001 - a
00100101 - t
10101001 - e
00001010 - space
0100000 - length 4
00100 - distance 5 or 6 depending on one extra bit
0 - extra bit -> distance 5
0000000 - end code
0 - fill bit to byte boundary
person Mark Adler    schedule 01.07.2013
comment
Не могли бы вы уточнить, почему 00101110 = D и 10101001 = e? - person TLJ; 09.07.2015
comment
Прочтите RFC 1951, раздел 3.2.6. Д = 0x44. Добавьте 0x30, чтобы получить 0x74. Поменяйте местами биты и получите 00101110. e = 0x65. Добавьте 0x30, чтобы получить 0x95. Поменяйте местами биты и получите 10101001. - person Mark Adler; 09.07.2015
comment
RFC чрезвычайно сбивает с толку и содержит недоработанные таблицы в десятичном формате вместо двоичного, и не объясняет ясно, как были получены таблицы. Откуда вы взяли 0x30? Это всегда + 0x30 или это зависит от значения, которое вы добавляете? Почему ты меняешь местами биты? Знаете ли вы какие-либо другие ресурсы (помимо RFC), которые предоставляют четкие примеры раздувания сжатых данных и объясняют, почему фиксированные таблицы такие, какие они есть? - person Dan Bechard; 21.12.2016
comment
Я посмотрел, но не смог найти полусырые таблицы в RFC. 0x30 — это количество 7-битных кодов в фиксированном коде Хаффмана (от 256 до 279). Они предшествуют 8-битным кодам в канонической конструкции кода Хаффмана, поэтому для кодирования литералов в диапазоне от 0 до 143 вы добавляете 0x30 для учета предшествующих им кодов. Биты меняются местами согласно соглашению, указанному в 3.1.1. - person Mark Adler; 21.12.2016
comment
Чтобы помочь вам понять RFC 1951, вы можете посмотреть puff.c, простой инфлятор, написанный для однозначного определения формата. - person Mark Adler; 21.12.2016
comment
Фиксированный код был определен Филом Кацем при создании формата. Поскольку его больше нет с нами, мы можем только догадываться, как он придумал этот конкретный код. - person Mark Adler; 21.12.2016