哈弗曼算法实现压缩和解压

//这是我一个学长的，我看了好久才明白，给大家分享，这里的代码只是一个压缩方法的，还有
//一些类已经上传(测试类，结构类都在文件里面)，需要可以下载，这个算法没有用递归遍历整个文件夹，所以之只能压缩
//一个文件，下面是主要压缩步骤：
//整个压缩文件的内容：（写入顺序）
 * 1.将原文件大小写入文件 dos.writeInt(fileSize);
 * 2.将码表的大小写入文件	dos.writeInt(mapSize);
 * 3.将每个字节写入文件fos.write(listBy.get(i));
 * 4.将每个字节对应的哈夫曼编码大小写入文件fos.write(codeSize);
 * 5.将每个字符对应的哈夫曼编码写入文件dos.writeChars(hfmcode_next);
 * 6.写入压缩后的字节数组的大小
 * 7.写入文件内容
//
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.HashMap;
import java.util.List;

import javax.swing.tree.TreeNode;

/**
 * 整个压缩文件的内容：（写入顺序）
 * 1.将原文件大小写入文件 dos.writeInt(fileSize);
 * 2.将码表的大小写入文件	dos.writeInt(mapSize);
 * 3.将每个字节写入文件fos.write(listBy.get(i));
 * 4.将每个字节对应的哈夫曼编码大小写入文件fos.write(codeSize);
 * 5.将每个字符对应的哈夫曼编码写入文件dos.writeChars(hfmcode_next);
 * 6.写入压缩后的字节数组的大小
 * 7.写入文件内容
 * @author yan
 * 
 */
public class yasu {
	private String hashcode_path="D:\\实验文件夹\\HashCode.txt";//存储所有字节哈弗曼编码01串
	/**
	 * 读取文件
	 * 
	 * @param path
	 *            :文件路径
	 * @return:将文件的内容以字节数组的样式返回
	 */
	public static byte[] readFile(String path) {
	
		byte[] dataByte = null;
		try {
			java.io.FileInputStream fis = new java.io.FileInputStream(path);
			//int size = fis.available();// 可读的字节数
			File f = new File(path);
			long size1=f.length();//这样子也可以获取源文件的大小，并且还很准确。
			int size=(int)size1;
			dataByte = new byte[size];
			fis.read(dataByte);

		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return dataByte;
	}

	/**
	 * 将码表的相关信息写入文件
	 * 
	 * @param fileSize
	 *            :原文件大小
	 * @param map
	 *            :存放码表的map
	 * @param listCh
	 *            :存放关键码的字符队列
	 * @param path
	 *            :文件路径
	 * @throws Exception
	 */
	public static void writeMap(int fileSize,
			java.util.HashMap<Byte, String> map, List<Byte> listBy, String path)
			throws Exception {

		java.io.FileOutputStream fos = new java.io.FileOutputStream(path);
		java.io.DataOutputStream dos = new java.io.DataOutputStream(fos);

		dos.writeInt(fileSize);//1. 将原文件大小写入文件
		int mapSize = map.size();// 码表的大小
		dos.writeInt(mapSize);// 2.将码表的大小写入文件
		for (int i = 0; i < mapSize; i++) {
			fos.write(listBy.get(i));// 3.将每个字节写入文件
			String hfmcode_next = map.get(listBy.get(i));// 得到每个字节对应的哈夫曼编码
			byte codeSize = (byte) hfmcode_next.length();
			fos.write(codeSize);// 4.将每个字节对应的哈夫曼编码大小写入文件
			dos.writeChars(hfmcode_next);// 5.将每个字符对应的哈夫曼编码写入文件
		}
		dos.flush();
		fos.close();
	}

	/**
	 * 将压缩好的字节数组写入文件
	 * 
	 * @param b
	 *            :压缩好的字节数组
	 * @param path
	 *            :文件路径
	 */
	public static void writeFile(byte[] b, String path) {
		try {
			java.io.FileOutputStream fos = new java.io.FileOutputStream(path,
					true);
			java.io.DataOutputStream dos = new java.io.DataOutputStream(fos);
			// 写入字节数组的大小
			dos.writeInt(b.length);
			fos.write(b);
			fos.flush();
			fos.close();
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}



	
	/**
	 * 将10字符串以8个为一组转化为一个字节数组
	 * 
	 * @param str
	 * @return
	 */
	//String ->char[]->byte( char数组转换成byte数组 然后把一个8个字节大小的byte数组转换成一个2进制的值,然后强制转型为byte   实现压缩。。。结果得到一个byte类型的值)->
	private byte[] StringToByteArray(String str) {
		char[] c = str.toCharArray();// 将字节串str转化为字符数组c
		int len = c.length;// 字符串字符的个数
		int lenByte;
		String s = "";
		char c_next;
		byte[] b;//存放已经转换成字节的01串
		if (len % 8 == 0) {// 如果字符串的长度能被8整除
			lenByte = len / 8 + 1;//+1是因为最后一个要存放补0的个数
			b = new byte[lenByte];
			for (int i = 0; i < lenByte - 1; i++) {
				for (int j = i * 8; j < (i + 1) * 8; j++) {
					c_next = c[j];
					s = s + c_next;//第i个组的01串，每8个一组(分离出8个01串字符，)
				}
				//System.out.println("第" + i + "个字符串：" + s);
				System.out.println("进入转化8个01串的方法");
				b[i] = CharArrayToByte(s);//把一组01字符串转化成一个字节
				s = "";
				//System.out.println("第" + i + "个字符串转化为字节后的值：" + b[i]);
			}
			b[lenByte - 1] = 0;// 字节数组的最后一个存放补0的个数
		} else {// 如果字符串的长度不能被8整除

			lenByte = len / 8 + 2;
			b = new byte[lenByte];
			int remainder = len % 8;// 求出除8的余数
			int zeroNum = 8 - remainder;// 补0的个数
			//System.out.println("补0数：" + zeroNum);
			//System.out.println("原字符串：" + str);
			for (int i = 0; i < zeroNum; i++) {
				str = str + '0';// 在字符串后面补0
			}
			//System.out.println("补0后的字符串：" + str);
			c = str.toCharArray();
			//System.out.println("补0后的字符串的字符个数：" + c.length);
			for (int i = 0; i < lenByte - 1; i++) {
				for (int j = i * 8; j < (i + 1) * 8; j++) {
					c_next = c[j];
					s = s + c_next;
				}
				//System.out.println("第" + i + "个字符串：" + s);
				b[i] = CharArrayToByte(s);
				s = "";
				//System.out.println("第" + i + "个字符串转化为字节后的值：" + b[i]);
			}
			b[lenByte - 1] = (byte) zeroNum;// 字节数组的最后一个存放补0的个数
		}
		return b;
	}
	
	/**
	 * 将8字符串（8个字节）转化为一个字节，（其实这里便是压缩过程。。。）
	 * 把一个8个字节大小的byte数组转换成一个2进制的值,然后强制转型为byte   实现压缩。。。
	 * @param str: 传入的8字符串
	 *            
	 * @return: 一个字节
	 */
	private byte CharArrayToByte(String str) {
		char[] c = str.toCharArray();// 将字符串str转化为字符数组c
		int len = c.length;
		byte[] b = new byte[len];
		byte value = 0;
		byte value_next;
		for (int i = 0; i < len; i++) {
			b[i] = Byte.parseByte(c[i] + "");//此方法将返回由十进制参数表示的字节值
			// System.out.println(b[i]);
		}
		//把一个8个字节大小的byte数组转换成一个2进制的值,然后强制转型为byte  8位就是2的8次方，则最大为256      实现压缩。。。。。
		for (int i = 0; i < len; i++) {
			value_next = (byte) (b[i] * Math.pow(2, len - i - 1));// 幂计算,括号里面计算一组01串的二进制数
			value = (byte) (value + value_next);
	//b[i] * Math.pow(2, len - i - 1)这个计算的是一个没有符号位的8位01串，它的范围是0到256，但是byte是-128到127，所以会出现负值
	//在解压的时候转换成int类型时候+256
		}
		return value;
	}
	/**
	 * 把哈弗曼编码01串存入文件  
	 */
	public static void Save_hashcode(String path,String hfmcode){
		try {
			FileWriter fw=new FileWriter(path);
			BufferedWriter bw=new BufferedWriter(fw);
			bw.write(hfmcode);
			bw.flush();
			fw.close();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	/**
	 * 压缩文件
	 * 
	 * @param path1
	 *            :原文件路径
	 * @param path2
	 *            :压缩后的文件路径
	 * @throws Exception
	 */
	public void CompressFile(String path1, String path2) throws Exception {
		// 从文件中得到字节数组
		System.out.println("进入压缩方法");
		byte[] b = yasu.readFile(path1);
		int b_size = b.length;// 原文件大小
		byte[] b_compress;// 字节数组，存放压缩的字符串

		 String hfmcode = "";// 文件内所有字节的哈夫曼编码
		String hfmcode_next;// 文件中每个字节的哈夫曼编码

		// ********上面那么多就是想要得到码表和存放关键码队列
		Tree hfm = new Tree();
		HashMap<Byte, String> map = hfm.M(path1);//这个是存有byte和相应的编码的haspmap键值对
		// 接下来获得存放关键码的队列（存有字节名称的list集合）
		List<Byte> listBy = hfm.L(path1);

		for (int i = 0; i < b_size; i++) {
			// 得到每个字节的哈夫曼编码
			hfmcode_next = map.get(b[i]); // 字节b[i]对应的哈夫曼编码
		//	System.out.println("第" + i + "个： " + b[i] + "的编码：" + hfmcode_next);
			hfmcode = hfmcode + hfmcode_next;// 将每个字节的哈夫曼编码依次相加为一个01字符串
		}
		// hfmcode存放源文件所有字节一一对应的哈夫曼编码
		//System.out.println("01串大小：" + hfmcode.length());
		//System.out.println("01串：" + hfmcode);
		char[] ch = hfmcode.toCharArray(); // 将源文件的哈夫曼编码转化成字符数组
		//System.out.println("01串的大小：" + ch.length);
		// 将源文件的哈夫曼编码转化 得到对应的字节数组,这个方法StringToByteArray(hfmcode);
		//实现了将8个byte字节转换成一个2进制数然后又转换为byte,实现压缩
		b_compress = StringToByteArray(hfmcode);
		//for (int i = 0; i < b_compress.length; i++) {
			//System.out.println("第" + i + "个字节" + b_compress[i]);
	//	}
		System.out.println("进入写入***********");
		// 1.将文件大小和码表相关信息写入文件
		writeMap(b_size, map, listBy, path2); 
		// 2.将字节数组写入文件
		writeFile(b_compress, path2);
		Save_hashcode(hashcode_path,hfmcode);
		System.out.println("完成！！");
	}