Канонический код Хаффмана
-
Основы канонического кода Хаффмана
- Канонические коды Хаффмана — это особый тип кодов Хаффмана с уникальными свойствами.
- Вместо сохранения структуры кодового дерева, они упорядочены по длине кодовых слов, что снижает нагрузку на кодовую книгу.
-
Мотивация и реализация
- Компрессоры данных обычно используют каноническую кодовую книгу для эффективной работы.
- Канонизация кодовой книги Хаффмана начинается с создания обычной кодовой книги и затем преобразуется в каноническую.
- Для распаковки данных декодеру требуется та же модель, что и для сжатия.
-
Алгоритм канонизации
- Обычный алгоритм Хаффмана присваивает символам коды переменной длины, но канонизация сортирует коды по длине и алфавиту.
- Кодирование канонической кодовой книги может быть выполнено меньшим количеством битов по сравнению с произвольным деревом Хаффмана.
-
Представление кодовой книги
- Кодовая книга может быть закодирована с использованием количества битов для каждого символа или с указанием количества символов для каждой разрядности.
- Псевдокод для реконструкции кодовой книги представлен в статье.
-
Рекомендации
- Алгоритм описан в статье «Способ построения кодов с минимальной избыточностью» Дэвида А. Хаффмана.
Полный текст статьи: