哈夫曼压缩算法.pdf
《哈夫曼压缩算法.pdf》由会员分享,可在线阅读,更多相关《哈夫曼压缩算法.pdf(7页珍藏版)》请在三一文库上搜索。
1、文件压缩总结(哈夫曼压缩)在学习哈弗曼压缩之前,还是首先来了解什么是哈夫曼树,哈夫曼编码。 1.哈夫曼树是一种最优二叉树,它的带权路径长度达到最小。树的带权路径长度为所有叶子结点带权路径长度之和。而结点的带权路径长度是结点的路径长度乘以结点的权值。 2.哈夫曼编码是依据字符出现概率来构造异字头的平均长度最短的码字。从哈弗曼树的根结点开始,按照左子树代码为“0”,右子树代码为“1”的规则,直到树的叶子结点,每个叶子结点的哈弗曼编码就是从根结点开始,将途中经过的枝结点和叶子结点的代码按顺序串起来。哈夫曼压缩是字节符号用一个特定长度的 01 序列替代, 在文件中出现频率高的符号, 使用短的 01 序
2、列, 而出现频率少的字节符号, 则用较长的 01 序列表示。这里的文件压缩, 我还只能做简单的 文件 A-压缩为文件 B-解压为文件C,看文件 A 和文件 C 是不是相同。那么就要分两个大步骤,小步骤:不过,根据哈弗曼树的特点,我们首先还是要定义结点类型结点类型代码1. public class TreeNode 2. public TreeNode parent; /双亲结点3. public TreeNode left; /左孩子结点4. public TreeNode right; /右孩子结点5.6. public byte con;/ 结点的数据7. public int rate;
3、8. public String bian=;9. public int count=0;10. public TreeNode(byte con, int rate) 11. super();12. this.con= con;13. this.rate = rate;14. 15. 然后分两大步骤一. 首先压缩文件1. 将源文件 A 中数据按字节读取,然后用 MAP 统计每个字节出现的次数 (Key-不同的字节,value-次数)。统计频率代码1. while (t != -1) / 如果未到达结尾2. byte b = (byte) t;3.4. if (map.containsKey(
4、b) / 如果 map 里面包含 number 键5. int value = map.get(b);/ 就可以通过get函数得到number对应的 value 的值6. value+;/ 使次数加 17.8. map.put(b, value);9. else / 如果 map 里面不包含 number 键10. map.put(b, 1);/ number 的次数只有一次11. 12. / 继续读取下一个13. t = bis.read();14.15. 2. 将 Map 中的 value 值作为权值,建哈夫曼树,并得到每个字节的哈弗曼编码。创建哈树代码1. /*2. * 创建哈树3. *
5、 param nodeQueue已经得到的优先队列4. * return创建哈树后,返回树的根结点5. */6. public static TreeNode creatTree(PriorityQueue nodeQueue)7. byte a=0; /定义一个 byte,用来表示枝节点的 字节8. TreeNode root=null; /用来表示树的根结点9. while(nodeQueue.size()=2) /当优先队列中 的元素大于 2 时,还可以使它们组成新的跟结点10. TreeNode left=nodeQueue.poll(); /获取当前队列中的最小元素,并将队列中的该元
6、素删除。是该节点作为左孩子11. TreeNode right=nodeQueue.poll(); /获取当前队列中的最小元素,作为右孩子12. root=new TreeNode(a,left.rate+right.rate); /左右孩子的频率之和作为 根结点的 频率13. root.left=left; /连接孩子结点和根结点的关系14. root.right=right;15. if(nodeQueue.size()=0)16. return root;17. 18. nodeQueue.add(root);19. 20. return root;21. 得到哈夫曼编码代码1. /*2
7、. * 得到哈树 叶子结点的哈弗曼编码3. * param node哈树的根结点4. * return将叶子结点的字节,编码存放入 map 中返回5. */6. public static HashMap getCode(TreeNode node)7. if(node.con!=(byte)0)8. System.out.println(char)node.con+-zuo-+node.bian);9. codemap.put(node.con, node.bian);10. 11. TreeNode left=node.left; / 获得左孩子结点12. if(left!=null) /
8、若为非空则获得它的 哈弗曼编码13. left.bian=node.bian+0;14. left.count+;15. getCode(left);16. 17. TreeNode right=node.right; / 获得右孩子结点18. if(right!=null) /若为非空则获得它的 哈弗曼编码19. right.bian=node.bian+1;20. right.count+;21. getCode(right);22. 23. return codemap;24.3. 压缩关键(压缩文件的格式:码表+文件信息)再构造 Map(Key-每个不同的字节,value-哈弗曼编码)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈夫曼 压缩 算法
链接地址:https://www.31doc.com/p-13475555.html