知识卡片

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

有效码长不等于压缩文件大小

理解等级:中级

编码载荷大小由Σ频数×实际码长得到:本例12×3+18×2+7×3+15×2+20×2=163 bit。和原576 bit相比,载荷节省约71.7%,略高于经验熵基准161.463 bit的理想长度。

实际文件还要让解码器知道符号频率/树、原长度或结束信息,并把有效位打包为整字节。没有计入这些开销的71.7%不能直接称为本章完整压缩缓冲的实际节省;对很短数据,头部可能比全部原文还大。

静态霍夫曼常先扫一次统计频率、再扫一次写码,解码按每符号路径消耗输入位。时间应按符号数、有效码长和字母表规模解释,不把“快速/最高效”当未给输入的普遍性能排名。

271第一/第二问说明近均匀频率和小样本的头部成本会削弱霍夫曼收益;LZ77字面标记过多也会膨胀。窗口太小是可能原因之一,缺少重复或重复很远同样可能使匹配少,不能承诺通常无需考虑这些输入。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      163位 假设不使用压缩算法的72个字符均用8位来表示,那么其总共所占的数据大小为576位,所以其压缩比计算如下: 1-(163/576)=71.7% 要再次强调的是,在实际中无法用小数位来表示霍夫曼编码,所以在很多情况下这个压缩比并没有数据的熵效果那么好。但它也非常接近于最佳压缩比。 在通常情况下

    • · 查看原书依据

      小量的数据时,其压缩效果也不好。在这种情况中,表中表头所占用的空间对数据的压缩率会产生负面影响。幸运的是,这些限制条件通常都不是问题,因为在大多数的数据中符号都不会是均匀分布的,而且我们通常对压缩小量的数据不感兴趣。 问:和霍夫曼编码一样,在某些情况下使用LZ77算法也可能产生不佳的压缩结果。请说明

    参考来源

    - 位置:《算法精解:C语言描述》第14章《霍夫曼编码的效率》(spine1383;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1349.html;u257-ch14-013)。 - 结论依据:257所有频数乘码长、比例和两次扫描段实读,260/261格式文字已读,避免把载荷模型伪称当前编码器全输出测量。 - 原始内容:163位 假设不使用压缩算法的72个字符均用8位来表示,那么其总共所占的数据大小为576位,所以其压缩比计算如下: 1-(163/576)=71.7% 要再次强调的是,在实际中无法用小数位来表示霍夫曼编码,所以在很多情况下这个压缩比并没有数据的熵效果那么好。但它也非常接近于最佳压缩比。 在通常情况下 - 位置:《算法精解:C语言描述》第14章《问与答》(spine1394;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1360.html;u271-ch14-013)。 - 结论依据:271第一/第二问说明近均匀频率和小样本的头部成本会削弱霍夫曼收益;LZ77字面标记过多也会膨胀。窗口太小是可能原因之一,缺少重复或重复很远同样可能使匹配少,不能承诺通常无需考虑这些输入。 - 原始内容:小量的数据时,其压缩效果也不好。在这种情况中,表中表头所占用的空间对数据的压缩率会产生负面影响。幸运的是,这些限制条件通常都不是问题,因为在大多数的数据中符号都不会是均匀分布的,而且我们通常对压缩小量的数据不感兴趣。 问:和霍夫曼编码一样,在某些情况下使用LZ77算法也可能产生不佳的压缩结果。请说明