知识卡片
构树须覆盖全字母表并收敛
256种字节值应覆盖0到255,但源码多个循环用c_MAX,在8位字节环境只处理0到254。255号频数、码表项和头部频数字节未按意图初始化或填写,遇到原始字节255还可能对未初始化频数递增。
有S棵初始树时,每次两树合一使数量减1,应合并S−1次。源码for(c=1;c;c++)只有S−2次;S≥2时最后仍有两棵树,却只提取一棵并销毁队列剩余树,导致部分符号丢失。这些是按源码推导的错误,未执行原C程序。
修复时要同时维护“所有实际符号均有叶子”和“最终只有一棵覆盖它们的树”两项不变量,不能只改一个边界就宣布编码器可用。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
示例14-3)解压缩由huffman_compress压缩的数据。首先,此操作读取追加到压缩数据的头。回想一下,头的前4个字节包含编码符号的数量。这个值存放在size中。接下来的256个字节包含所有符号的缩放频率。 利用存放在头中的信息,调用build_tree重建压缩过程中用到的霍夫曼树。一旦重建
参考来源
- 位置:《算法精解:C语言描述》第14章《huffman_uncompress》(spine1386;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1352.html;u261-ch14-018)。
- 结论依据:03021–03029完整实读:build_tree初始循环、合并循环和最终extract/destroy,以及compress/uncompress对应循环。
- 原始内容:示例14-3)解压缩由huffman_compress压缩的数据。首先,此操作读取追加到压缩数据的头。回想一下,头的前4个字节包含编码符号的数量。这个值存放在size中。接下来的256个字节包含所有符号的缩放频率。 利用存放在头中的信息,调用build_tree重建压缩过程中用到的霍夫曼树。一旦重建