哈夫曼编码算法与分析(java实现)
5星 · 超过95%的资源 需积分: 50 120 浏览量
2012-11-26
15:23:38
上传
评论 4
收藏 98KB DOC 举报 
算 法 与 分 析
1. 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。给出文件中各个字符
出现的频率，求各个字符的哈夫曼编码方案。
2. 给定带权有向图 G =(V,E)，其中每条边的权是非负实数。另外，还给定 V 中的一个
顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指
路上各边权之和。
3. 设 G =(V,E)是无向连通带权图，即一个网络。E 中每条边(v,w)的权为 c[v][w]。如
果 G 的子图 G’是一棵包含 G 的所有顶点的树，则称 G’为 G 的生成树。生成树上各边
权的总和称为该生成树的耗费。在 G 的所有生成树中，耗费最小的生成树称为 G 的最
小生成树。求 G 的最小生成树。
求解问题的算法原理：
1.最优装载哈夫曼编码
1.1 前缀码
对每一个字符规定一个 0,1 串作为其代码，并要求任一字符的代码都不是其它字符代码
的前缀，这种编码称为前缀码。
编码的前缀性质可以使译码方法非常简单。
表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有 2 个儿子结点。
平均码长定义为：
B(T)=
f(c):c 的码长，dt(c):c 的深度
使平均码长达到最小的前缀码编码方案称为给定编码字符集 C 的最优前缀码。
1.2 构造哈夫曼编码
哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。
哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树 T。
算法以|C|个叶结点开始，执行|C|-1 次的“合并”运算后产生最终所要求的树 T。
编码字符集中每一字符 c 的频率是 f(c)。以 f 为键值的优先队列 Q 用在贪心选择时有效
地确定算法当前要合并的 2 棵具有最小频率的树。一旦 2 棵具有最小频率的树合并后，产
生一棵新的树，其频率为合并的 2 棵树的频率之和，并将新树插入优先队列 Q。经过 n-1
次的合并后，优先队列中只剩下一棵树，即所要求的树 T。
可用最小堆实现优先队列 Q。
2.单源最短路径
Dijkstra 算法是解单源最短路径问题的贪心算法。
其基本思想是，设置顶点集合 S 并不断地作贪心选择来扩充这个集合。一个顶点属于集
合 S 当且仅当从源到该顶点的最短路径长度已知。
剩余11页未读，继续阅读
资源评论
u0102728742015-05-22很好的资源，值得下载！！
小小葡萄干2016-03-05代码可以 值得参考，在写Android版的哈夫曼中加以修改应用- qq_257149292015-11-21可以参考算法。
- jintianmingtianyiran2013-07-12程序有点BUG，运行不起，不过可以参考算法
