Канонический код Хаффмана

• Основы канонического кода Хаффмана

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

• Мотивация и реализация

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

• Алгоритм канонизации

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

• Представление кодовой книги

  • Кодовая книга может быть закодирована с использованием количества битов для каждого символа или с указанием количества символов для каждой разрядности. 
  • Псевдокод для реконструкции кодовой книги представлен в статье. 

• Рекомендации

  • Алгоритм описан в статье «Способ построения кодов с минимальной избыточностью» Дэвида А. Хаффмана.