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

Question

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

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

Answer 1

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

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