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

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

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 (без использования дерева Хаффмана в декодере)?

источник

2017-01-19 beginner

После внесения изменений в вопрос, это еще не префиксный код. A является префиксом как C, так и D. В префиксном коде код не может содержать какой-либо другой код в качестве его префикса. –

Теперь это неполный код. 100 и 111 не используются. Вы можете вырезать последний бит C и D, чтобы сделать эти 10 и 11, чтобы сделать его полным кодом, с длиной 2 2 2 2. Единственные допустимые длины кода с четырьмя символами - 2 2 2 2 и 1 2 3 3. –

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

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

источник

2017-01-19 15:47:51

Спасибо, Марк. Хорошо, я получил коды и доступные биты. Однако из одного из ваших более ранних объяснений в другом потоке мы не должны отправлять кодовые слова в декодер, верно? Итак, можете ли вы рассказать мне, как будет выглядеть кодированный поток бит для приведенного выше примера? В случае обычного Хаффмана это были бы только соответствующие кодовые слова. Мой другой вопрос состоял в том, что мы не должны использовать дерево Хаффмана в декодере, как декодер будет выводить кодовое слово (или из длины кода) ~ символьную информацию? Благодарю. – beginner

Это еще два вопроса, поэтому вы должны опубликовать два новых вопроса. –

Хорошо, конечно. – beginner

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

ответ

Смежные вопросы