文件的压缩

本节主要是利用huffman树的原理来对文件进行处理，从而达到压缩文件的效果。huffman树又称为最优二叉树。是带权路径最短的树。

先说说怎么建huffman树，其构造方法为：

1.根据给定的n个权值的结点，选出两个结点值最小的数作为左、右子树，这个二叉树的根结点为左、右结点的权值之和。

2.将新的权值加入到剩余结点中，删除原来的两个结点

3.重复1 2，直到最后只有一个结点为止。

Huffman压缩是一个无损的压缩算法。通过构建huffman树，可以得到每个叶结点的huffman编码，然后把源文件的字节用huffman编码来存储，从而达到减小空间占用，实现压缩。

要实现文件的压缩，可以分为如下几步：

一、根据传入的文件，统计每个字节出现的次数

二、根据每个字节出现的次数，构建一棵huffman树

三、根据huffman树，得到每个字节的huffman编码

四、把源文件和huffman编码写入文件中去

通过这几步就基本上可以实现文件的压缩。

第一步：

 

/**
	 * 根据传入的文件，统计每个字节出现的次数
	 * @param path	文件的路径
	 * @return	int数组
	 */
	public int[] fileByteCount(String path){
		//存储文件中每个字节出现的次数
		try{
			FileInputStream fis=new FileInputStream(path);
			BufferedInputStream bis=new BufferedInputStream(fis);
			while(fis.available()>0){
				//文件是否读完
				int i=fis.read();
				byteCount[i]++;	//用数组存储每个字节出现的次数		
			}
			fis.close();
			bis.close();
		}catch(Exception ef){
			ef.printStackTrace();
		}	
		return byteCount;
	}

 第二步：

/**
	 * 创建最优二叉树的方法
	 * @param arr：传入的数组
	 * @param TreeNode:返回根结点
	 */
	public TreeNode createHuffman(int[] arr){
		//实例化一个优先队列对象
		PriorityQueue<TreeNode> queue = new PriorityQueue<TreeNode>(11,new MyComparator());
		TreeNode root=null;
		//遍历数组，将数组元素构建成结点,并添加到队列中
		for (int i=0;i<arr.length;i++){
			if(arr[i]!=0){
				//创建结点,结点值不为0
				TreeNode node = new TreeNode(i,arr[i]);
				//将结点添加到队列中
				queue.add(node);
			}
		}
		//遍历队列，每次取出两个最小元素作为叶子结点，它们的和作为父结点建立二叉树,
		//并从队列中删除这两个元素，同时把它们的父结点添加到队列中
		while(queue.size()>1){
			//同时取两个最小元素
			TreeNode node1 = queue.poll();
			TreeNode node2 = queue.poll();			
			//根据取得的元素创建父结点
			TreeNode fnode = new TreeNode(0,node1.getZijie()+node2.getZijie());			
			//建立引用关系
				fnode.setLeft(node1);
				fnode.setRight(node2);
				node1.setParent(fnode);
				node2.setParent(node2);		
			//将父结点添加到队列中
			queue.add(fnode);				
		}	
		root =queue.peek();
		return root;
	}	

 第三步：

/**
	 * 根据根结点创建哈夫曼编码
	 * 规则：左子结点为：1，右子结点为：0
	 * @param root：根结点
	 */
	public void createCode(TreeNode root,String code){
		//首先是确定各结点的路径
			//得到子结点
			TreeNode left = root.getLeft();	
			TreeNode right = root.getRight();
			//打印叶子节点
			if (left==null&&right==null){				
				System.out.println(root.getObj()+"的编码为："+code);
				//byteCode 的下标是字节，值为其哈夫曼编码
				byteCode[(Integer)root.getObj()]=code;
			}
			if (left!=null){
				//递归
				createCode(left,code+"0");
			}
			if (right!=null){
				//递归
				createCode(right,code+"1");
			}
	}

 第四步：是最重要的一步，也是最关键的一步：

/**
	 * 把源文件和huffman编码写入文件中去
	 * @param path	源文件路径
	 * @param path1	要写入的文件路径
	 * @param str	huffman编码的String数组
	 */
	public void writeToFile(String path,String path1,String []str){
		try{
			FileOutputStream fos = new FileOutputStream(path1);
			DataOutputStream Dos = new DataOutputStream(fos);// 创建输出流	
			for (int k = 0; k< str.length; k++) {
				if (str[k] != null){ 
					Dos.writeInt(k);
					Dos.writeInt(str[k].length());	
				}else{
					str[k]="";
					Dos.writeInt(k);
					Dos.writeInt(0);
				}			
			}	
			//先把编码写入文件
			int count=0;//记录中转的字符个数
			int i=0;//第i个字节
			String writes="";
			String tranString ="";
			String waiteString ;
			while(i<256||count>=8){
				//等待的字符大于8
				if(count>=8){
					waiteString="";
					//讲writes前8位取出
					for (int t = 0; t < 8; t++) {
						waiteString = waiteString + writes.charAt(t);
					}
					// 将writes前八位去掉
					if (writes.length() > 8) {
						tranString = "";
						for (int t = 8; t < writes.length(); t++) {
							tranString = tranString + writes.charAt(t);
						}
						writes = "";
						writes = tranString;
					}else {
						//刚好只有8位
						writes = "";
					}
					count = count - 8;// 写出一个8位的字节
					int intw = changeString(waiteString);// 得到String转化为int
					// 写入文件
					Dos.writeInt(intw);
				}else if(count<8){
					// 得到第i个编码信息等待写入
					if (str[i]!= null ) {
						count = count + str[i].length();
						if(str[i].length()!=0){
						}
						writes = writes + str[i];
						i++;
					}
				}
			}
			// 把所有编码没有足够8的整数倍的String补0使得足够8的整数倍，在写入
			if (count > 0&&count<8) {
				waiteString = "";// 清空要转化的编码
				int buzero=0;
				for (int t = 0; t < 8; t++) {
					if (t < writes.length()) {
						waiteString = waiteString + writes.charAt(t);
					} else {
						waiteString = waiteString + "0";
						//补了多少个0
						buzero++;	
					}
				}
				Dos.writeInt(changeString(waiteString));
				Dos.writeInt(buzero);
			}
			try{
				// 将源文件中的所有byte转化为01字符串，写入压缩文件
				FileInputStream fis = new FileInputStream(path);
				BufferedInputStream bis = new BufferedInputStream(fis);
				count =0;
				writes="";
				tranString ="";
				int idata=bis.read();
				while(bis.available()>0||count>=8){
					//如果缓冲区等待写入的字符超过8
					if(count>=8){
						waiteString="";
						for (int t = 0; t < 8; t++) {
							waiteString = waiteString + writes.charAt(t);
						}
						// 将前八位删掉
						if (writes.length() > 8) {
							tranString = "";
							for (int t = 8; t < writes.length(); t++) {
								tranString = tranString + writes.charAt(t);
							}
							writes = "";
							writes = tranString;

						} else {
							writes = "";
						}
						count = count - 8;// 写出一个8位的字节
						int intw = changeString(waiteString);
						Dos.writeInt(intw);
					}else {
						// 如果不够8位，就继续取下一个字节
						count = count + str[idata].length();
						writes = writes + str[idata];
						idata = bis.read();
					}					
				}
				count = count + str[idata].length();
				writes = writes + str[idata];
				// 把count剩下的写入
				int endsint = 0;
				if (count > 0) {
					waiteString = "";// 清空要转化的码
					for (int t = 0; t < 8; t++) {
						if (t < writes.length()) {
							waiteString = waiteString + writes.charAt(endsint);
						} else {
							waiteString = waiteString + '0';
							endsint++;
						}
					}
					Dos.writeInt(changeString(waiteString));// 写入所补的0；
					Dos.writeInt(endsint);
					System.out.println(endsint);
					Dos.flush();
				}
				fis.close();
				bis.close();
				fos.close();
				Dos.close();
			}catch(Exception ef){
				ef.printStackTrace();
			}
		}catch(Exception ef){
				ef.printStackTrace();
		}
	}

 然后根据源文件的路径，调用方法，并制定生成的文件路径及文件名，这样就可以进行文件压缩啦。但这只是简单的压缩，可能对一些小文件进行压缩时，压缩的文件比源文件可能还大，这样还不如不压缩，这里可能还存在一些小问题，希望牛人指出。

 

 

 

<!--EndFragment-->