Канонический кодировщик Хаффмана: содержание закодированного битового потока

Допустим, у нас есть следующая каноническая кодовая таблица Хаффмана.

Symbol    Code-length   Codeword
 A            2          00
 B            2          01
 C            2          10
 D            2          11

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

Если текстовый файл содержит ACCDB, должен ли я передавать 00 01 10 11 или 10 10 10 10 (двоичный эквивалент соответствующей длины кода) как закодированный битовый поток? Пожалуйста, исправьте меня, если я ошибаюсь, и я ценю любое объяснение.

Более того, если это так для канонического Хаффмана, как мы можем декодировать этот битовый поток, чтобы вернуть исходные символы ACCDB (без использования дерева Хаффмана в декодере)?


encoding compression algorithm huffman-code text-compression
person beginner    schedule 19.01.2017    source источник
comment
После того, как вы отредактировали вопрос, это все еще не префиксный код. A является префиксом как C, так и D. В коде префикса никакой код не может иметь в качестве префикса какой-либо другой код.   -  person Mark Adler    schedule 20.01.2017
comment
Теперь это неполный код. 100 и 111 не используются. Вы можете отрезать последний бит C и D, чтобы сделать эти 10 и 11 полным кодом с длинами 2 2 2 2. Единственными допустимыми длинами четырехсимвольного кода являются 2 2 2 2 и 1 2 3 3.   -  person Mark Adler    schedule 20.01.2017

Ответы (1)


arrow_upward
0
arrow_downward

Это не каноническая таблица кодов Хаффмана, не код Хаффмана и не код префикса. Длины кода 1, 2, 2, 3 превышают доступные биты. 1, 2, 2 - это полный код, не позволяющий кодировать больше символов.

1, 2, 3, 3 - это полный код без превышения лимита подписки, и в этом случае примером кода может быть 0, 10, 110, 111. Вы можете видеть, что эти коды могут быть однозначно декодированы, читая их слева направо. .

person Mark Adler    schedule 19.01.2017
comment
Спасибо, Марк. Хорошо, я получил информацию о кодах и доступных битах. Однако из одного из ваших более ранних объяснений в другом потоке, мы не должны отправлять кодовые слова в декодер, верно? Итак, не могли бы вы рассказать мне, как будет выглядеть закодированный битовый поток для приведенного выше примера? В случае обычного Хаффмана это были бы просто соответствующие кодовые слова. Другой мой вопрос заключался в том, что если мы не должны использовать дерево Хаффмана в декодере, как декодер будет выводить кодовое слово (или из длины кода) ~ символьную информацию? Спасибо. - person beginner; 19.01.2017
comment
Это еще два вопроса, поэтому вам следует задать два новых вопроса. - person Mark Adler; 19.01.2017
comment
Хорошо, конечно. - person beginner; 19.01.2017