Dynami c Huffman: четкость упаковки битов - PullRequest
Новая
       147

Dynami c Huffman: четкость упаковки битов

0 голосов
/ 25 февраля 2020

Мне просто интересно, есть ли хорошие примеры Dynami c Упаковка битов Хаффмана. Я не очень хорошо понимаю материал RF C, касающийся упаковки битов. Я нашел много отличных примеров для Stati c Huffman здесь, в Stack Overflow, однако примеров для Dynami c, похоже, не хватает.

В РФ C 1951, раздел 3.1.1 

             * Data elements are packed into bytes in order of
               increasing bit number within the byte, i.e., starting
               with the least-significant bit of the byte.
             * Data elements other than Huffman codes are packed
               starting with the least-significant bit of the data
               element.
             * Huffman codes are packed starting with the most-
               significant bit of the code.

Я сбит с толку из-за изменения в упаковке данных между Huffman Codes и Data Elements other than Huffman Codes. Что составляет Huffman Codes и Data Elements other than Huffman Codes. В какую группу попадают codelengths, hlit, hclen, hdist, actual compressed data? Спасибо.

Ответы [ 2 ]

0 голосов
/ 16 марта 2020

Буквенные коды / коды длины и расстояния в сжатых данных и код длины кодов в динамических заголовках - это все коды Хаффмана, и они обращены (самый старший бит кода входит в наименее значимый неиспользуемый бит текущего байта, который собирается, и так далее). Эти три являются кодами Хаффмана в формате deflate. Все остальное в формате, включая дополнительные биты, следующие за некоторыми из этих кодов, упакованы в их естественном порядке (младший значащий бит входит в следующий младший значащий неиспользованный бит).

0 голосов
/ 25 февраля 2020

Это только моя интерпретация https://tools.ietf.org/html/rfc1951. Насколько я понимаю, первый пункт описывает выходной битовый буфер; способ, которым битовый буфер очищается в битовом потоке. Второй и третий биты с входом буфера.

Пример: 5-битный элемент данных 11110 , за которым следует 4-битный код Хаффмана 0001

Хранится в буфере битов: 01111 0001

Хранится в буфере обращенных битов (что более логично): 1000 11110

Упаковано в байты: 00011110 xxxxxxx 1

Редактировать: В случае, если это была неясная часть, «Коды Хаффмана» имеют особое значение в CS, ссылаясь на действительные коды которые могут быть прочитаны с дерева. Все, что называется Хаффманом, например «Длина кода Хаффмана», является метаданными, а не кодами.

Очевидно, этот порядок упакованных битов предназначен для максимально простого декодирования с использованием логических операций и операций сдвига. Метаданные имеют правильный битовый порядок для потребления. Коды Хаффмана поменялись местами. Таким образом, декодирование может начаться до того, как все биты, которые образуют код, находятся в буфере битов.

...