知识卡片
范式哈夫曼编码：为随机访问而生的编码变体
内容
标准哈夫曼解码要从树根沿指针走到叶子，每解码一位就访问一次几乎不会被重复引用的内存节点，大字母表下会造成大量缓存不命中，且存整棵树本身要耗费巨大内存。范式哈夫曼只要保证同一码长的码字数值连续且按字典序排列，就不需遍历树，只需知道每种码长的第一个码字即可定位，额外内存从”一整棵树”降到”码长种类数”，特别适合全文检索这种高频随机解码场景，MG系统就用它压缩正文。
参考来源
- 位置：第2章《文本压缩》2.3节「哈夫曼编码」（源文件：_chapter-text/ch02.txt）
- 结论依据：原文说明标准哈夫曼解码树存储开销大、遍历指针导致缓存不命中，而范式哈夫曼只需知道每种码长的第一个码字即可解码，且MG系统采用基于单字的范式哈夫曼编码压缩正文，直接支持卡片论点。
- 原始内容："第2个问题是从根到叶子遍历一棵树涉及通过内存查找大量的指针……这会产生页错误或者大量的缓存不命中……范式码的使用意味着解码只需比n个字稍多的空间……MG系统采用基于单字的哈夫曼编码方法来压缩主要文本。"