知识卡片

普通读书笔记卡 · 1285.j.1.o · 生成模型:未记录

字节频数不保证十六码长

理解等级:中级

原文断言频数缩放到一个字节后没有码长超过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追加到编码末尾中。一旦到达一个叶子结