作业11-Greedy解决Optimal Prefix-Code Problem
发布时间
阅读量：
阅读量
1.问题
设字符集为 C=\{x_1,x_2,x_3,...,x_n\}，并已知每个字符对应的出现频率{f(x_i)}，现需确定一个关于C的最优前缀码。
所谓前缀码，是指在字符编码过程中所采用的一种通用编码方式，其核心特征在于：任意一个字符的编码均不能作为其他字符编码的前缀部分。具备这一特性的编码形式即被称为前缀码（该名称可能存在一定的表述歧义）。
而最优前缀码，则是在满足前缀码特性的前提下，能够使整个字符集C的平均码长达到最小值的编码策略。
（上述关于前缀码与最优前缀码的定义源自百度百科）
2.解析框架构建
思路：采用贪心算法构建最优前缀编码
具体实现：首先建立一个最小堆结构，依次从堆顶取出两个节点，生成一个新的节点，该节点的数值为前两个节点数值的总和，并将第一个节点作为新节点的左子节点，第二个节点作为右子节点。随后将原先堆顶的两个节点移除，并将新生成的节点重新插入堆中。重复上述过程，直至最小堆中仅剩一个节点，此时哈夫曼森林便转化为哈夫曼树，最终即可生成对应的编码方案。
例子：
设有字符集合C={A,B,C,D,E,F,G}，其对应的出现频率为f(x)={3,6,7,4,2,20,1}
还没有任何评论哟~