知识卡片

普通读书笔记卡 · 3613.d.1 · 生成模型:未记录

霍夫曼构树反复合并最小项

理解等级:中级

本章介绍霍夫曼树构造时,先把较小树作为候选,每轮从优先队列取出两棵权重最小的树并合并,再以合并结果继续后续选择。优先队列提供的是重复取最小权重的能力,目标不在于把所有候选完全排序。

符号频率用于权重,构成的编码会让高频符号通常使用较短码。这里尚未解释完整编码生成、前缀性质或最优性证明,不能仅靠这段应用预告就声称全部压缩算法已读或实现。

255/03018最初W7、U12、X15、V18、Y20,合7+12=19,再15+18=33,再19+20=39,最后33+39=72。叶保存符号及频数,内部根保存合计频数,最后根为原72个符号。图不表示普通按键搜索树,而是频率合并生成的码树。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      每次都必须合并键值最小的二叉树,因此每次合并的两棵树都是从一个优先队列中取出的。 负载均衡 它用来维护管理一系列处理类似任务的服务。当连接请求到达时,优先队列可以确定哪个服务器能够最好地处理到达的任务。

    • · 查看原书依据

      两个频率最小的根结点的树合并,并将其频率之和存放到树的新根结点中(见图14-1,步骤2)。这个过程反复持续下去,直到最后只剩下一棵树(这棵树就是霍夫曼树,见图14-1,步骤5)。霍夫曼树的根结点包含数据中符号的总个数,它的叶子结点包含原始的符号和符号的频率。由于霍夫曼编码就是在不断寻找两棵最适合合并

    参考来源

    - 位置:《算法精解:C语言描述》第10章《第10章 堆和优先队列》(spine1308;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1275.html;u170-ch10-002)。 - 结论依据:170霍夫曼应用段与144频率/码长说明已读,保留两两合并时取最小的机制;完整第14章仍待阅读。 - 原始内容:每次都必须合并键值最小的二叉树,因此每次合并的两棵树都是从一个优先队列中取出的。 负载均衡 它用来维护管理一系列处理类似任务的服务。当连接请求到达时,优先队列可以确定哪个服务器能够最好地处理到达的任务。 - 位置:《算法精解:C语言描述》第14章《构造霍夫曼树》(spine1381;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1347.html;u255-ch10-002)。 - 结论依据:255/03018最初W7、U12、X15、V18、Y20,合7+12=19,再15+18=33,再19+20=39,最后33+39=72。叶保存符号及频数,内部根保存合计频数,最后根为原72个符号。图不表示普通按键搜索树,而是频率合并生成的码树。 - 原始内容:两个频率最小的根结点的树合并,并将其频率之和存放到树的新根结点中(见图14-1,步骤2)。这个过程反复持续下去,直到最后只剩下一棵树(这棵树就是霍夫曼树,见图14-1,步骤5)。霍夫曼树的根结点包含数据中符号的总个数,它的叶子结点包含原始的符号和符号的频率。由于霍夫曼编码就是在不断寻找两棵最适合合并