知识卡片

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

高频短码优化的是加权长度

理解等级:中级

变长符号码按频率分配码长:常见符号尽量用较短码,罕见符号可用较长码,目标是让Σ频数×码长较小。每个符号仍需可区分且能无歧义组合,不是随意给所有高频符号相同短码。

符号不必是文字字符,可以由应用定义;本章实际实现取一个字节为符号。不同频率也可能得到相同整数码长,因此“频率更高用短码”是设计方向,不表示每对不等频率都必须严格不同长。

霍夫曼在给定权重、逐符号二元前缀码的范围中优化平均长度,不表示在任意字典/块编码/所有压缩格式中全局最短。权重模型若改变,最优所针对的目标也随之改变。

255给定频数下二元逐符号前缀码需整数码长,可能不能逐符号等于小数自信息,故平均长度可高于熵基准;这不削弱在该前缀码范围的最优性,也不证明它接近所有数据的整体压缩极限。同频平局可得到不同码树,不应强求唯一比特编码。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      出现频率高的符号编码,用较多的位对出现频率低的符号编码。我们要意识到,一个符号不一定必须是文本字符,它可以是任何大小的数据,但往往它只占一个字节。

    • · 查看原书依据

      小数位的(如表14-1所示)。而在实际中,因为霍夫曼编码所用的位数不可能有小数位,所以有些代码会超过实际最优的代码位数。 图14-1展示了用表14-1中的数据来构建一棵霍夫曼树的过程。构建的过程往往从叶子结点向上进行。首先,将每个符号和频率放到它自身的树中(见图14-1,步骤1)。然后,将两个频率最

    参考来源

    - 位置:《算法精解:C语言描述》第14章《霍夫曼编码的描述》(spine1380;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1346.html;u253-ch14-010)。 - 结论依据:253全文最小冗余说明实读,255树构建与257频数乘码长机制已读;最优范围由已读Stanford作者Huffman最优前缀码段补核,不扩大到所有编码。 - 原始内容:出现频率高的符号编码,用较多的位对出现频率低的符号编码。我们要意识到,一个符号不一定必须是文本字符,它可以是任何大小的数据,但往往它只占一个字节。 - 位置:《算法精解:C语言描述》第14章《构造霍夫曼树》(spine1381;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1347.html;u255-ch14-010)。 - 结论依据:255给定频数下二元逐符号前缀码需整数码长,可能不能逐符号等于小数自信息,故平均长度可高于熵基准;这不削弱在该前缀码范围的最优性,也不证明它接近所有数据的整体压缩极限。同频平局可得到不同码树,不应强求唯一比特编码。 - 原始内容:小数位的(如表14-1所示)。而在实际中,因为霍夫曼编码所用的位数不可能有小数位,所以有些代码会超过实际最优的代码位数。 图14-1展示了用表14-1中的数据来构建一棵霍夫曼树的过程。构建的过程往往从叶子结点向上进行。首先,将每个符号和频率放到它自身的树中(见图14-1,步骤1)。然后,将两个频率最