精选优质文档-倾情为你奉上哈夫曼编码I.问题描述 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。II.问题分析 对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。 设C为编码字符集，则表示其最优前缀码的二叉树中恰有|C|个叶子，|C|-1个内部结点。其中，每个叶子对应于字符集中一个字符。二叉树T的代价：编码文件需要二进制位数使 达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。 哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始，执行|C|1次的“合并”运算后产生最终所要求的树T。 编码字符集中每一字符c的频率是freq。以freq为键值的最小堆优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。
