Каким будет содержимое канонического битового потока, закодированного по алгоритму Хаффмана?

Закодированный битовый поток

Код:

00 01 10 110 111

Обратите внимание, что если бы мы отправили код 2,2,2,3,3, то было бы невозможно решить, был ли ввод AAACC или BBBEE (или многие другие эквивалентные варианты).

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

Другими словами, получив результат 000110110111, мы можем однозначно декодировать его как ABDCE.

Передача кодовой таблицы

Я думаю, что путаница может быть связана с тем, что вам нужно иметь две вещи для декодирования битового потока:

1. Кодированный битовый поток
2. Таблица поиска

Эти две вещи часто кодируются совершенно по-разному.

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

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

Пример

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

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

// Next sixteen bytes are the counts for each code length
u8 counts[16];
for (i = 0; i < 16; i++) {
    counts[i] = fgetc(fp);
    ctr++;
}

// Remaining bytes are the data values to be mapped
// Build the Huffman map of (length, code) -> value
for (i = 0; i < 16; i++) {
    for (j = 0; j < counts[i]; j++) {
        huffData[table][huffKey(i + 1, code)] = fgetc(fp);
        code++;
        ctr++;
    }
    code <<= 1;
}

Вы спрашиваете, как отправить описание кода получателю, чтобы получатель знал, как декодировать следующие значения кода.

Есть много способов изменить уровень сложности, в зависимости от того, сколько усилий вы хотите приложить для сжатия описания кода. Питер де Риваз описывает простой подход, используемый JPEG, который заключается в отправке 16 отсчетов количества кодов каждой длины, за которыми следуют байтовые значения каждого из этих символов. Итак, для вашего кода это будет (в шестнадцатеричном формате):

00 03 02 00 00 00 00 00 00 00 00 00 00 00 00 00 41 42 43 44 45

Это не очень компактно и не может представлять один из возможных кодов, то есть 256 8-битных кодов, поскольку вы ограничены количеством 255 для каждой длины.

Первое, что вы можете сделать, это отрезать длину кода, когда у вас есть полный код. Легко подсчитать, сколько шаблонов кода осталось, и в этом случае вы можете просто завершить его, когда их не останется. Следуйте за этим с помощью символов. Тогда у вас есть:

00 03 02 41 42 43 44 45

Нам не нужно восемь битов для каждого счетчика, так как они ограничены ограничениями на эти счетчики. Например, у вас не может быть более двух однобитных кодов. Таким образом, мы могли бы кодировать их меньшим количеством битов, например. n+1 бит для n кодов. Итак, два бита, три, биты и так далее, пока код не будет завершен. Для вашего кода, теперь в двоичном формате:

00 011 0010

за которыми следуют байты 41 42 43 44 45, смещенные в битовом потоке соответствующим образом. Теперь список отсчетов занимает девять битов вместо 24. Поскольку мы знаем, что может быть только 256 символов, мы можем ограничить количество битов для каждого отсчета девятью, что позволяет считать 256, решая предыдущую проблему не быть может представлять плоский код. Затем, если длина кода ограничена 16 битами (как для JPEG), наибольшее количество байтов, необходимых для подсчета, составляет 14,5, что меньше исходных 16. Часто подсчеты заканчиваются до 14,5 байт.

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

00 011 10, то восьмибитные значения 41 42 43 44 45

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

Совершенно другая схема используется в формате deflate (используется в zip, gzip, zlib, png и т. д.). Там сначала отправляется количество длин кода, за которым следует длина кода каждого символа по порядку до последнего. Сами символы подразумеваются расположением длины кода. Это приводит к большому количеству нулей для представления отсутствующих символов. Таким образом, для вашего кода будет 70, чтобы подняться до символа 69 («E»), за которым следуют 65 нулей, затем 2 2 2 3 3. Это кажется ужасно длинным, и это так. deflate, затем run-length и Хаффман кодирует этот список длин, чтобы сжать его. Длинные строки нулей сжимаются до нескольких битов, а короткие строки также состоят всего из нескольких битов каждая. Итак, вам нужно сначала отправить описание кода длины кода длины кода (!), чтобы вы могли его расшифровать.

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