知识卡片
哈夫曼编码的整数位长天花板
内容
哈夫曼编码给每个符号分配整数长度码字，这是它压缩效果不如算术编码的根本原因。当某符号概率极高（如99%）时，理论上只需0.015比特，但哈夫曼编码器受限于整数位长最少也要1比特——多花的部分纯是浪费，概率越极端越严重。理论上可打包多个符号成”块”编码缓解，但块内组合数随块长指数增长，实际不可行。哈夫曼用”接近最优、实现简单”换掉了”绝对最优、实现复杂”的算术编码。
参考来源
- 位置：第2章《文本压缩》2.4节「算术编码」（源文件：_chapter-text/ch02.txt）
- 结论依据：原文用0.99/0.01概率的具体例子说明哈夫曼编码因整数位长限制至少要为高概率符号分配1比特，而算术编码只需0.015比特，并指出分块编码可缓解但块数随长度指数增长不可行，直接支持卡片论点。
- 原始内容："将哈夫曼编码与算术编码进行比较，假定编码一个来自两个符号的字母表中的符号，这两个符号的出现概率分别为0.99和0.01……具有99％出现概率的这个符号用算术编码只需要0.015比特；相反，哈夫曼编码器至少需要为每个符号分配1比特……分块难以实现……随着其长度的增加，块数呈指数性增长。"