知识卡片
哈夫曼码字溢出：病态情况远比直觉估计的更容易触发
内容
哈夫曼编码码长理论上没有硬性上限，用32位整数存储看起来绰绰有余——直觉上要处理2的33次方个符号才可能逼近溢出。但这直觉错了：迫使哈夫曼算法生成超长码字所需的最小符号数由斐波那契数列增长速度决定，其增长率远小于2。构造刻意的病态频率分布，只需一千三百万个符号就能把某码字撑到32位溢出，比朴素估计的90亿低近千倍。真正解法是理论上限长编码或把整数精度提高到64位，提醒要先推导最坏情况的真实增长率。
参考来源
- 位置：第9章《系统实现》「码字溢出」小节（源文件：_chapter-text/ch09.txt，对应_epub-src/OEBPS/text00015.html）
- 结论依据：原文明确说明迫使哈夫曼算法生成最大码长的符号数由斐波那契数列决定，只需不到1300万符号即可导致33比特码字溢出，远小于按2的指数估算的90亿，直接支持卡片论点。
- 原始内容："迫使哈夫曼算法生成出最大码长的频表实际上是与大名鼎鼎的斐波那契数列有关……只需不到1300万的符号。在病态（pathological）情况下，即可迫使哈夫曼编码生成33比特长的码字，大大小于此前讨论的90亿的估计值。"