1、先读取文件,统计每个字符在文件中出现的次数。读取文件应用到文件输出流(FileInputStream),在读的过程中,每次读取只读一个字节(byte(8个bit)),根据每次读取的字节可以统计文件中每个字符出现的次数。
2、根据统计出来的字符个数(作为节点的权值),建立哈夫曼树。要建立哈夫曼树,首先要对这些数字进行排序,每次取最小的两个数作为子节点,生产一个父节点,并且父节点的数字是两个子节点的数字之和,去除已经取的这两个数,并把生成的父节点的数添加进去重新排序,再次取出两个最小的数进行上面的操作,直到要排序的数字只剩下一个,操作结束,同时建好哈夫曼树(提示:可以把数字放到队列或数组中排序)。
/** * 创建哈弗曼树 * @param nodes * @return */ public static <T> Node<T> createTree(List<Node<T>> nodes){ while(nodes.size() > 1){ Collections.sort(nodes); Node<T> left = nodes.get(nodes.size()-1); Node<T> right = nodes.get(nodes.size()-2); Node<T> parent = new Node<T>(null, left.getWeight()+right.getWeight()); parent.setLeftChild(left); parent.setRightChild(right); nodes.remove(left); nodes.remove(right); nodes.add(parent); } return nodes.get(0); }
3、遍历哈夫曼树,把每一个节点转换成二进制。遍历哈夫曼树可以用递归,也可以用循环。
(1)、用循环遍历哈夫曼树(提示:用字符串的形式表示二进制)。
遍历时,应用到两个集合框架,一个是ArrayList,另一个是ArrayDeque。先从根节点开
始遍历,把根节点先存到ArrayDeque中,用一个while循环并确保ArrayDeque中存到有节点。
然后把ArrayDeque中的节点放到ArrayList中且把这个节点从ArrayDeque中删除,并判断这个
节点是否有左右节点,若有把节点放到ArrayDeque中,并且左节点字符串添加一个0,字符串
长度加1,右节点字符串添加一个1,字符串长度加1。最后返回ArrayList。
public static <T> List<Node<T>> breadth(Node<T> root){ List<Node<T>> list = new ArrayList<Node<T>>(); Queue<Node<T>> queue = new ArrayDeque<Node<T>>(); String str = ""; if(root != null){ queue.offer(root); root.setStr(str); root.setN(0); } while(!queue.isEmpty()){ list.add(queue.peek()); Node<T> node = queue.poll(); if(node.getLeftChild() != null){ queue.offer(node.getLeftChild()); str = node.getStr()+"0"; node.getLeftChild().setStr(str); int n = node.getN()+1; node.getLeftChild().setN(n); } if(node.getRightChild() != null){ queue.offer(node.getRightChild()); str = node.getStr()+"1"; node.getRightChild().setStr(str); int n = node.getN()+1; node.getRightChild().setN(n); } } return list; }
(2)、递归遍历哈夫曼树(中序遍历)。
先访问根节点,分别递归左右节点。同样是递归左节点时,左节点字符串添加一个0,字
符串长度加1,递归右节点时,右节点字符串添加一个1,字符串长度加1。
/** * 访问节点 * */ public static <T> void visit(Node<T> p) { System.out.print(p.getData() + " "); } /** * 递归实现前序遍历 * @param <T> * @param root */ protected static <T> void preorder(Node<T> p) { if (p != null) { visit(p); preorder(p.getLeftChild()); preorder(p.getRightChild()); } }
4、每八个一组转换成可写的形式。
先根据每个字符的权值和二进制长度计算文件中字符转换成二进制的总长度,若总长度不是8
的倍数,在最后面补零凑够8的倍数,并把补零的个数在最后用八位的二进制表示。
然后每八位一组转换成可写的形式往文件中写。我认为最好把补零的个数和要不补的0写在文
件的前面,这样可以在解压时先把补得0删除。在文件的开始最好是先把每一个字符及对应的码值
写进去,以便于解压。
/** * 每八位转换成二进制 * @param s * @return */ public int chengString(String s){ System.out.println("每次取得的八位字符:"+s); int n = ((int)s.charAt(0)-48)*128+((int)s.charAt(1)-48)*64+ ((int)s.charAt(2)-48)*32+((int)s.charAt(3)-48)*16+ ((int)s.charAt(4)-48)*8+((int)s.charAt(5)-48)*4+ ((int)s.charAt(6)-48)*2+((int)s.charAt(7)-48); return n; }
总结,第一次了解文件的压缩,以前经常用文件压缩,但从没有考虑过它的压缩过程(很多事情就发生在我们身边,只是不太注意和深究它)。在做的过程中,遇到很多问题:如何建树,怎么转换成二进制等。解决问题有很多方式,可以查找资料,可以在网上搜索,也可以与别人交流,另外遇到问题可以先分析问题,把一个问题进行分解,变成小问题。同时了解到自己对集合框架的运用不够灵活。要说收获,对如何建哈夫曼树有了了解,对队列Queue的添加、检查和移除有了了解等等。
相关推荐
数据结构课程设计用哈夫曼编码实现文件压缩: 一、实验题目: 用哈夫曼编码实现文件压缩 二、实验目的: 1、了解文件的概念。 2、掌握线性链表的插入、删除等算法。 3、掌握Huffman树的概念及构造方法。 4、掌握...
C# 文件压缩-指定文件压缩
1. 分析给出的多文件打包/解包程序MyZip和单文件压缩程序Compress,将程序MyZip改写为一个能够处理多文件压缩/解压的控制台程序,可利用命令行参数控制其完成如下功能: 1. 将命令行参数指定的一组文件压缩为一个...
如果服务器上安装了RAR程序,那么asp.net可以调用RAR实现文件压缩与解压缩。 不过要注意的是,由于Web程序不能直接调用客户端的程序(除非用ActiveX,ActiveX几乎被废弃),所以如果要想实现让用户把本地文件用网页...
1G的文件压缩成1M的方法1G的文件压缩成1M的方法.rar1G的文件压缩成1M的方法.rar1G的文件压缩成1M的方法.rar1G的文件压缩成1M的方法.rar1G的文件压缩成1M的方法.rar1G的文件压缩成1M的方法.rar1G的文件压缩成1M的方法...
JAVA文件压缩与解压缩实践(源代码+论文),详细文档分析!
1G的文件压缩成1M的方法,很多网上下载的文件只有300MB或400MB,但是解压后,居然可以达到2GB甚至更多,也许你会奇怪,为什么你用WinRAR压缩同样的文件,就没有这样的压缩效果呢?其实这是因为这些文件是用多款不同...
适合练手、课程设计、毕业设计的Java项目源码:文件压缩与解压缩实践(源代码+论文).rar 适合练手、课程设计、毕业设计的Java项目源码:文件压缩与解压缩实践(源代码+论文).rar 适合练手、课程设计、毕业设计的Java...
JAVA文件压缩与解压缩实践报告 主函数 gzip压缩模块代码 压缩模块要完成的就是将文件读入以后进行压缩,再将压缩后的数据写入一个新的文件,其部分代码如下: public class gzip { public static void main(String...
Java把文件压缩成zip,粘贴在项目中即可使用
C++利用Zlib库实现zip文件压缩及解压 支持递归压缩.可配合自动更新功能实现zip压缩包进得软件更新
利用哈夫曼编码思想,设计对一个文本文件(.txt)中的字符进行哈夫曼编码,生成编码压缩文件(.txt),并且还可将压缩后的文件进行解码还原为原始文本文件(.txt)。 实现的功能: (1)压缩:实现对文件的压缩,生成...
教你如何将1G文件压缩成1M 实用啊
c语言实现文件压缩,用huffman编码实现。并修改注册表实现鼠标右击出现如同rar的简单操作。
C# rar 文件压缩 .net 压缩文件 RAR
利用C#实现文件压缩 并生成文件的xml文档说明
java实现多个文件压缩
太好用的图形文件压缩软件,它可以满足文件尺寸大小不变可文件体积大幅减小。而清晰度几乎不变。
哈夫曼编码是一种常用的数据压缩技术,对数据文件进行哈夫曼编码可大大缩短文件的传输长度,提高信道利用率及传输效率。要求采用哈夫曼编码原理,统计文本文件中字符出现的词频,以词频作为权值,对文件进行哈夫曼...