为何对字符串应用Huffman编码算法后得到的体积比原始数据更大？

解答 #

Huffman编码出现编码后体积大于原数据的情况是短样本场景下的正常现象，核心原因是忽略了编码表存储的固定开销，且测试样本的冗余度过低，具体如下：

• Huffman编码的总存储开销由两部分组成：编码后的二进制数据长度 + 解码必需的霍夫曼编码表（字符和对应编码的映射关系）存储长度，只有两者之和小于原数据长度时才能得到正向压缩收益。
• 你本次的测试场景刚好踩中了压缩收益为负的情况：
  1. 测试样本仅15个字符，一共包含10种不同字符，大部分字符仅出现1~2次，频率分布非常均匀，用短编码替换高频字符的收益极低，仅编码后的数据部分49比特远小于原数据的120比特，但加上10字节（80比特）的编码表存储开销、15比特的字节对齐填充开销后，总开销直接反超原数据。
  2. 当测试样本长度提升到数百、上千字节，且存在大量重复字符时，编码表的固定开销会被平摊到大量数据上，Huffman编码的压缩收益就会正常体现。
• 你当前的计算结果和实现逻辑没有问题，短文本场景下Huffman编码体积变大属于预期内的情况。

内容的提问来源于stack exchange，提问作者Arafat_19AK