哈夫曼压缩

上一篇博文简要地谈了一下哈夫曼编码，此文主要说说用哈夫曼编码实现的简单的的最常用的静态无损压缩--哈夫曼压缩。

 

压缩（Compression）

（麻麻说过中西结合效果好...）

 

首先，建立哈夫曼树的结点类

 

package com.Tree20131009;


/**
 * Class node of Huffman tree
 * 
 * @author YangKang
 * 
 */
public class HfmNode {

	int data = 0; // 存储的字符
	int weight = 0;//节点数据出现的次数（权值）
	HfmNode leftChild = null;// 左边子结点
	HfmNode rightChild = null;// 右边子结点
	HfmNode parent = null;// 父结点

	/**
	 * HfmNode constructor
	 * @param data
	 * @param weight
	 */
	public HfmNode(int data, int weight) {
		this.data = data;
		this.weight = weight;
	}
}

 

 

 

接下来就是读取文件，统计字符出现的频率，并排序。

 

为了简便自定义如下存储格式基本信息

saveCode , Code []  //哈夫曼编码表

 

 

由于文件输入流中可能因为有汉字的存在，而在read（）方法返回负数。故要对汉子进行相应的处理。

但暂时没有加入汉字的编码和解码。

 

	// 获取统计字节频率表
	int[] byteCount;

	/**
	 * 读取文件，统计文件中元素出现的频率
	 * 
	 * @param path 文件路径名
	 * @return 统计的字符元素和频率的数组
	 */
	public int[] readFile(String path) throws IOException {
		// 创建一个文件输入流对象
		java.io.FileInputStream fis = new java.io.FileInputStream(path);
		java.io.BufferedInputStream bis = new java.io.BufferedInputStream(fis);

		// LogTool.INFO("文件输入流创建成功");
		// LogTool.INFO(fis.toString());

		int[] byteCount = new int[256];
		// 读入 所有的文件字节
		while (bis.available() > 0) {
			int i = bis.read();
			// LogTool.INFO(new Integer(i).toString());

			if (i < 0) {// 越界处理
				// byteCount[-i + 127]++;
				LogTool.INFO("统计汉字成功");
				if ((-i + 127) > 256) { // 汉字处理
					LogTool.INFO("汉字，编码大于了256！！！");
				}
			} else {
				// 统计字符的频率
				byteCount[i]++;
				//LogTool.INFO("统计字符成功" + i);
				if (i > 255) {
					LogTool.ERROR("数组越界，大于了256！！！");
				}
			}
		}
		// 关闭文件输入流
		fis.close();
		return byteCount;
	}

 

 

 

字符频率排序的方法。

 

 鄙人图简单用的是优先队列，优先队列比较符合哈夫曼树的构造方法；其特点为数字越小，优先权越高。也可以用冒泡排序等自定义排序，一定要重写比较器中的compare(o1, o2)方法，因为自然排序只是对于基本数据类型而非对象。否则会报java.lang.ClassCastException异常（好高端的异常，之前都没有见过）。

 

	/**
	 * 将频率存入优先队列
	 * 
	 * @throws IOException
	 */
	public PriorityQueue<HfmNode> saveList(String scrpath) throws IOException {

		// 获取统计字节频率表
		byteCount = readFile(scrpath);
		
		for (int i = 0; i < byteCount.length; i++) {
			System.out.println("ASCII  "+i+"\t次数  "+byteCount[i]);
		}

		// 创建优先队列
		PriorityQueue<HfmNode> nodeQueue = new PriorityQueue<HfmNode>(256,
				new Comparator<HfmNode>() {

					/**
					 * 实现比较器内的方法
					 * 
					 * @param node1
					 * @param node2
					 * @return
					 */
					public int compare(HfmNode node1, HfmNode node2) {
						return node1.weight - node2.weight;
					}
				});

		// 把所有结点放入优先队列中去
		for (int i = 0; i < byteCount.length; i++) {
			if (byteCount[i] != 0) {
				// 创建哈夫曼二叉树的叶子节点
				HfmNode newnode = new HfmNode(i, byteCount[i]);
				// LogTool.INFO("叶子结点创建成功");
				nodeQueue.add(newnode);
			}
		}
		return nodeQueue;
	}

 

 

再然后，我们就要种树啦...

	/**
	 * the method of creating a huffman tree
	 * 
	 * @return root of tree
	 * @throws IOException
	 */
	private HfmNode creatTree(String srcpath) throws IOException {

		// 获取统计字节频率表
		byteCount = readFile(srcpath);

		// 放入优先队列排序
		PriorityQueue<HfmNode> nodeQueue = saveList(srcpath);

		// 构建哈夫曼树
		while (nodeQueue.size() > 1) {
			// 获取了队首的两个最小的结点，并将两结点移出队列
			HfmNode min1 = nodeQueue.poll();
			HfmNode min2 = nodeQueue.poll();
			// 父节点的权值是左右子节点的权值之和
			HfmNode parentNode = new HfmNode(0, min1.weight + min2.weight);
			// LogTool.INFO("构建哈夫曼度为2的结点成功");

			// 建立树枝和树叶之间的连接关系
			parentNode.leftChild = min1;
			min1.parent = parentNode;
			parentNode.rightChild = min2;
			min2.parent = parentNode;
			nodeQueue.add(parentNode);
		}
		// 返回父结点
		HfmNode root = nodeQueue.peek();
		return root;
	}

 

种完树后就可以收获果实啦。  不过之前，那个竹篮来装岂不是更好。

 

哈夫曼字符编码类

package com.Tree20131009;

/**
 * 哈夫曼编码类
 * 
 * @author YangKang
 * 
 */
public class Code {
	public String node;// 哈夫曼编码
	public int length; // 哈夫曼编码长度
}

 

获取字符的哈夫曼编码，并存储到编码表中

	/**
	 * 获取叶子节点的哈夫曼编码的方法
	 * 
	 * @param root 根节点
	 * @param sWeight 由权值的编码
	 */
	private void getMB(HfmNode root, String sWeight) {
		if ((root.leftChild == null) && (root.rightChild == null)) {// 叶子节点
			Code hc = new Code();
			// 得到叶子节点的哈夫曼编码
			hc.node = sWeight;
			// 读取叶子节点的长度
			hc.length = sWeight.length();
			LogTool.INFO("叶子节点：" + root.data + "  编码：" + hc.node);
			// 将叶子节点的数据保存到数组中
			saveCode[root.data] = hc;
		}

		if (root.leftChild != null) {// 左边权值0，右边权值1
			// 递归遍历
			getMB(root.leftChild, sWeight + '0');
		}
		if (root.rightChild != null) {// 左边权值0，右边权值1
			// 递归遍历
			getMB(root.rightChild, sWeight + '1');
		}
	}

 

 然后就是将文件数据以哈夫曼编码的方式存储为压缩文件

 

压缩文件存储格式如下，前面2部分的左右方便解压缩。


 前面2部分写入压缩文件就不详细说明了，重点在源文件的字符转码。

将源文件数据经过哈夫曼编码后写入到压缩文件中

	/**
	 * 将源文件按照哈弗曼编码将其写入压缩文件
	 * 
	 * @param saveCode 哈弗曼编码表
	 * @param bos 缓冲输出流
	 * @throws IOException
	 */
	private void writeScrHfmFile(Code[] saveCode, BufferedOutputStream bos)
			throws IOException {

		// 创建源文件输入流，准备读取源文件中的信息，转换成哈夫曼编码将其写入压缩文件
		FileInputStream fis = new FileInputStream(srcpath);
		BufferedInputStream bis = new BufferedInputStream(fis);
		String tranString = "";
		while (bis.available() != 0) {// 文件读取结束标志 available()
			int ch = (int) bis.read();
			if (ch < 0) {// 汉字处理
				tranString += saveCode[-ch + 127].node;
			} else {
				tranString += saveCode[ch].node;
			}
			while (tranString.length() > 8) {// 加入的编码长度大于8时，将前8位写入文件转换成byte存入文件
				int byteCode = trans2int((tranString.substring(0, 8)));
				bos.write(byteCode); // 写入文件

				// 删除前8位已存入文件的编码
				String tempString = tranString
						.substring(8, tranString.length());
				tranString = "";
				// 以8为一段，分段截取字符串
				tranString = tempString.substring(0, tempString.length());
				tempString = "";
			}
		}

		// 将剩余不足8位的用0补足8位，写入文件 ，并且将补0个数用一个byte再写入
		int izerofill = tranString.length();
		for (int i = 0; i < 8 - izerofill; i++) {
			tranString += '0';
		}

		// 补足后再写入，并写入补足0的个数
		bos.write(trans2int(tranString));
		bos.write(8 - izerofill);// 写入补足0的个数
		// 压缩文件写完结束，关闭文件输入、输出流
		bos.flush();
		fis.close();
	}
}

 

由于java中没有系统定义的二进制的写入，所以，需要自己定义字符串满8位就转换为一个byte类型并写入文件。文件流读写参数或返回值通常是int类型。所以只要转换为int类型就好。

	/**
	 * 8位01字符转换成8位二进制的byte
	 * 
	 * @param byteString 8位01字符串
	 */
	private int trans2int(String byteString) {
		char[] charCode = byteString.toCharArray();
		if (byteString.length() == 8) {
			int byteCode = ((int) (charCode[0] - 48) * 128)
					+ ((int) (charCode[1] - 48) * 64)
					+ ((int) (charCode[2] - 48) * 32)
					+ ((int) (charCode[3] - 48) * 16)
					+ ((int) (charCode[4] - 48) * 8)
					+ ((int) (charCode[5] - 48) * 4)
					+ ((int) (charCode[6] - 48) * 2)
					+ ((int) (charCode[7] - 48) * 1);
			return byteCode;
		} else {
			return 0;
		}
	}

 这样，一个简单的哈夫曼压缩就OK啦

 

接下来是解压缩(Decompression)的过程

 

获取压缩文件的译码表

 

	/**
	 * 获取哈夫曼译码表方法
	 * 
	 * @param scrpath2  压缩文件路径
	 * @return 哈夫曼译码表
	 * @throws IOException
	 */
	private Code[] getSaveCode(String scrpath2) throws IOException {

		// 创建哈夫曼译码表
		Code[] saveCode = new Code[256];

		// 打开压缩文件
		FileInputStream fis = new FileInputStream(scrpath2);
		BufferedInputStream bis = new BufferedInputStream(fis);

		// 读取哈夫曼译码表的长度
		int codeTableSize = 0; // 表的总长度
		// 将编码表转换成译码表
		for (int n = 0; bis.available() > 0 && n < 256; n++) {
			int i = bis.read();
			Code code = new Code();
			code.length = i;
			code.node = null;
			saveCode[n] = code;
			codeTableSize += i;
		}

		String codeString = ""; // 取出编码表中的编码
		int length = bis.available(); // 文件的总长度
		int codeByteSize = codeTableSize / 8 + 1;// 译码表的字节总长度

		// 读取哈夫曼编码表
		if (length > 0) {
			for (int t = 0; t < codeByteSize; t++) {
				Integer i = new Integer(bis.read());

				// 将字符串序列转化为二进制序列
				String readString = Integer.toBinaryString(i);
				if (readString.length() < 8) {// 补前导0,因为toBinaryString转化出来的二进制数会略去前导0
					readString = zeroFill(readString);// 补0机制
				}
				codeString += readString;// 收集译码表中的译码
			}
		} else {
			LogTool.INFO("文件为空，读取无效");
		}

		// 还原编码表为译码表
		for (int i = 0, j = 0; i < 256 && j < codeString.length(); i++) {
			// 截取译码表中的每个译码信息
			saveCode[i].node = codeString.substring(j, saveCode[i].length + j);
			j += saveCode[i].length;
		}
		fis.close();// 关闭输入流
		return saveCode; // 返回译码表
	}

 

 

 将压缩文件的数据部分编码与译码表一一判断，判断成立就写入哈夫曼译码之后的字符

 

 

/**
	 * 进行判断，比较对应的哈夫曼编码，遍历找出对应的原始数据
	 * 
	 * @param saveCode 哈夫曼译码表
	 * @param data 从文件中读取的数据
	 * @param codeMax  哈夫曼译码的最大长度
	 * @param codeMin 哈夫曼译码的最小长度
	 * @param bos 缓冲输出流
	 * @return 截取匹配字符后的字符串
	 * @throws IOException
	 */
	private String compareCode(Code[] saveCode, String data, int codeMax,
			int codeMin, BufferedOutputStream bos) throws IOException {

		LogTool.INFO("文件数据部分的长度：" + data.length());

		// 从最短的哈夫曼编码取起，取到最长的哈夫曼编码，跟哈夫曼编码表对比
		for (int j = codeMin; j <= codeMax && data.length() >= codeMin
				&& j <= data.length(); j++) {

			String tempData = data.substring(0, j); // 取编码
			
			for (int k = 0; k < saveCode.length; k++) {// 将取来的编码与哈夫曼编码表逐个进行比较
				
				if (!saveCode[k].node.equals("")
						&& tempData.length() == saveCode[k].length
						&& tempData.equalsIgnoreCase(saveCode[k].node)) {// 比较成立时，写入相应的原始数据，删除已匹配的编码
					LogTool.INFO("saveCode[" + k + "].node = "
							+ saveCode[k].node + "\ttempData = " + tempData
							+ "  \t比较结果：" + tempData.equalsIgnoreCase(tempData));

					bos.write(k);// 将哈夫曼对应的原码写进目标文件
					LogTool.INFO("ASCII对应  " + k);
					counter++;
					tempData = "";// 清除原始数据
					LogTool.INFO("哈夫曼编码长度 " + j + " 当前字符串长度 " + data.length());

					tempData = data.substring(j, data.length());
					data = "";// 清除原始数据
					data = tempData; // 截去已匹配的数据
					break;
				}

			}
		}
		LogTool.INFO("译码后写入的文件数据-->" + data);
		return data;
	}

 

 

接下来就是写入文件啦

 

	/**
	 * 根据哈弗曼编码表还原数据，写入目标文件
	 * 
	 * @param saveCode 哈弗曼编码表
	 * @param despath2 目标文件路径
	 * @throws IOException
	 */
	private void restore(Code[] saveCode) throws IOException {

		int codeMax = Integer.MIN_VALUE; // 自定义的值，只是为了方便程序
		int codeMin = Integer.MAX_VALUE;// 自定义的值，只是为了方便程序
		int codeLength = 0;// 统计哈夫曼码表的总长度

		// 统计哈夫曼编码表的长度,以及最大编码长度和最小编码长度
		for (int i = 0; i < saveCode.length; i++) {
			if (!saveCode[i].node.equals("")) {
				if (saveCode[i].length > codeMax) {
					codeMax = saveCode[i].length; // 获得编码最大长度
				}
				if (saveCode[i].length < codeMin) {
					codeMin = saveCode[i].length; // 获得编码最小长度
				}
				codeLength += saveCode[i].length;// 获得哈夫曼表的总长度
			}

		}
		codeLength = codeLength / 8 + 1;// 获取哈夫曼表的字节总长度
		// 打开目标文件
		FileOutputStream fos = new FileOutputStream(despath);
		BufferedOutputStream bos = new BufferedOutputStream(fos);

		// 打开压缩文件
		FileInputStream fis = new FileInputStream(scrpath);
		BufferedInputStream bis = new BufferedInputStream(fis);
		bis.skip(saveCode.length + codeLength);// 跳过哈夫曼编码表

		// 开始读取压缩数据，还原原始数据
		String data = ""; // 取出正文的编码
		int dataLength = bis.available();
		for (int t = 0; t < dataLength; t++) {
			Integer i = new Integer(bis.read());
			LogTool.INFO("解压后字符信息-->" + i.intValue());
			String readString = Integer.toBinaryString(i);
			if (readString.length() < 8) {// 补前导0,因为toBinaryString转化出来的二进制数会略去前导0
				readString = zeroFill(readString);// 补0机制
			}
			LogTool.INFO("解压后字符的二进制序列 --> " + readString);
			data += readString; // 取出正文的编码

			LogTool.INFO("译码前data --> " + data);
			while (data.length() > codeMax) {//
				// 当取出的编码超过最长哈夫曼编码长度时，进行判断，比较对应的哈夫曼编码，找出对应的原始数据
				data = compareCode(saveCode, data, codeMax, codeMin, bos);// 比较对应的哈夫曼编码，如果匹配成功，删除已匹配的编码段，返回未匹配的编码段

				LogTool.INFO("译码后data --> " + data);
			}
		}

		// 将最后一个还没有匹配的编码最后一次匹配（长度介于codeMin和codeMax），写入文件
		Integer i = new Integer(bis.read());
		LogTool.INFO("解压后字符信息" + i.intValue());
		String readString = Integer.toBinaryString(i);
		readString = zeroFill(readString);// 补0机制

		int size = bis.read(); // 补0的个数
		LogTool.INFO("读取的字符编码字符 -->" + readString);
		readString = readString.substring(0, 8 - size);
		data += readString;
		LogTool.INFO("最后的data= " + data + "被补了" + size + "个0！！！");
		while (data.length() > 0) {
			data = compareCode(saveCode, data, codeMax, codeMin, bos);// 比较对应的哈夫曼编码，如果匹配成功，删除已匹配的编码段，返回未匹配的编码段
		}

		bos.flush(); // 强行输出
		fos.close(); // 关闭输出流
		fis.close(); // 关闭输入流
		LogTool.INFO("counter=" + counter);
	}

 

 

由于Integer.toBinaryString(i)方法返回的二进制序列会略去前导0，所以需要添上。

/**
	 * 给字节补前导0，转成字符串返回
	 * 
	 * @param s 二进制字符串序列
	 * @return 补零后的字符串
	 */
	private String zeroFill(String s) {
		String str = "";
		for (int j = 0; j < 8 - s.length(); j++) {
			str += "0";
		}
		str += s;// 把前导0补回来啦
		return str;
	}

 

这样一个哈夫曼解压过程也就完成了

 

运行示例

 

 

 

源代码打包上传地址：http://download.csdn.net/detail/u011458382/6393211
 

希望大家多多支持和指正。