Механизм сжатия

Question

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

Answer 1

То, как именно передается дерево Хаффмана, зависит от формата сжатия.

• Статический Хаффман кодирует дерево. Алгоритм Deflate кодирует только количество бит на символ .

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

Answer 2

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

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