返回主题:文本压缩与熵编码

知识卡片

普通读书笔记卡 · 3626.a.2

霍夫曼反复合并最低频

理解等级:中级
  1. 霍夫曼算法从每个字符各成一叶开始,
  2. 每轮取频率最低的两棵树作新节点的左右子树,
  3. 新节点频率为两者之和,再放回最小优先队列。

重复n−1轮后得到编码树;正确性仍须证明。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第15章 贪心算法 · 查看原书依据

      The algorithm uses a min-priority queue Q, keyed on the freq attribute, to identify the two least-frequent objects to merge together. The result of merging two objects is a new object whose frequency is the sum of the frequencies of the two objects that were merged.

    参考来源

    - 位置:《算法导论(第4版)》第15章《贪心算法》(OEBPS/chapter015.xhtml,文本字符[35000,40000))。 - 结论依据:HUFFMAN 伪代码以频率为键的最小优先队列,每轮两次 EXTRACT-MIN、建频率和节点并回插,重复 |C|−1 轮;正确性由后续引理证明。 - 原始内容:The algorithm uses a min-priority queue Q , keyed on the freq attribute, to identify the two least-frequent objects to merge together. The result of merging two objects is a new object whose frequency is the sum of the frequencies of the two objects that were merged.