知识卡片
字节频数不保证十六码长
原文断言频数缩放到一个字节后没有码长超过16位,不能作为定长unsigned short码字的正确性前提。独立数学核算给出反例:13个权重1,1,2,3,5,8,13,21,34,55,89,144,233,再加242个权重255,共255个符号;标准霍夫曼合并产生最长18位码。全部权重已在1到255,无需再缩放。
完整权重、合并轨迹和叶深保存在本批174-07-huffman-code-length-calculation.json。它是读者用Python优先队列进行的独立数学计算,未运行书中C实现。即使先修好原源码的遍历与合并错误,16位code字段仍不能覆盖此例;截断会丢失路径,按size计算bit_get位置也可能越界。
可选择显式限制码长的编码算法或能保存实际路径的表示,同时让文件格式和解码器共享约束;不能仅靠把权重缩小来推定路径一定够短。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
没有编码会大于16位。 使用一个有序的遍历方法(见第9章)来遍历霍夫曼树,从而构建这个表。在每次执行build_table的过程中,code记录当前生成的霍夫曼编码,size保存编码的位数。在遍历树时,每当选择左分支时,将0追加到编码末尾中;每当选择右分支时,将1追加到编码末尾中。一旦到达一个叶子结
参考来源
- 位置:《算法精解:C语言描述》第14章《huffman_compress》(spine1385;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1351.html;u260-ch14-016)。
- 结论依据:260的16位断言、03025/03027 short字段及取位表达式实读;反例通过本地独立数学核算记录,明确非原C程序运行。
- 原始内容:没有编码会大于16位。 使用一个有序的遍历方法(见第9章)来遍历霍夫曼树,从而构建这个表。在每次执行build_table的过程中,code记录当前生成的霍夫曼编码,size保存编码的位数。在遍历树时,每当选择左分支时,将0追加到编码末尾中;每当选择右分支时,将1追加到编码末尾中。一旦到达一个叶子结