哈弗曼压

sean2012

浏览: 47196 次
性别:
来自: 武汉

最近访客更多访客>>

dendy

qq842854683

Xujieli

dub

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

Java项目总结

java基础 java 设计模式编程

哈夫曼编哈弗曼压缩技术总结

一、哈弗曼编码原理
a) 哈弗曼编码概念：哈夫曼编码(Huffman Coding)是一种可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。
b) 哈弗曼编码特点：出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的。
二、哈弗曼编码过程
通过上面写原理描述我们大概可以了解，哈弗曼编码是可以用于文件无损压缩（可还原）技术，如果想对哈弗曼压缩有更深的了解可以查阅其它的相关资料，这里我们开始分享哈弗曼编码的实现过程。
首先我们根据这样一个流程图来创建我们的哈弗曼编码：

具体代码实现：
读取文件中的每个字节，并统计出现的次数

/**
	 * 读取文件，统计文件中元素出现的频率
	 * 
	 * @param path
	 * @throws IOException
	 */
	public int[] readFile(String path) throws IOException {
		FileInputStream fis = new FileInputStream(path);
		BufferedInputStream inputdataStream = new BufferedInputStream(fis);
		/**
		 * 统计文件中元素出现的频率
		 */
		int[] byteCount = new int[256];
		while (inputdataStream.available() > 0) {
			int i = inputdataStream.read();
			if (i < 0) {
				byteCount[-i + 127]++;
				if ((-i + 127) > 256) { // 汉字处理
					System.out.println("大于了256！！！");
				}
			} else {
				byteCount[i]++;
				if (i > 256) {
					System.out.println("大于了256！！！");
				}
			}

		}
		fis.close();
		return byteCount;
	}

byteCount 是一个全局数组，int[] byteCount = new int[256];为什么这个数组的长度为256，因为一个字节的可表示范围就是256，所以我们只需要和256个元素来记录就OK啦！当然这里面我们需要注意的一点是，我们读取文件时read（）方法虽然返回的是一个int型，但其实只读出一个byte而已，然后转成了int型返回；那么竟然是一个byte那么它的表示范围是-128~127，可表示范围的确是256；然而当我们用来表示byteCount数组下标的时候就不符合要求了，下标可能会有负数出现哦！因此为了处理这个问题，我们可以通过判断if (i < 0)时byteCount[-i + 127]++;把i取负加上127就为可以啦!这里很关键哦！一定要梳理清楚！

根据出现的次数构建哈弗曼树
根据上一个方法可获得文件字节出现次数统计结果，拿到这一结果，我们就可以创建一棵哈夫曼树！哈夫曼树的概念、特点和性质就不解说了，不清楚的可以查阅其它资料。

/**
	 * 建立哈弗曼树
	 * 
	 * @throws IOException
	 */
	public HuffmanNode creatHuffmanTree(String scrpath) throws IOException {
		/**
		 * 先放入优先队列排序
		 */
		PriorityQueue<HuffmanNode> huffmanNode = SaveList(scrpath);
		/**
		 * 从优先队列中取出数据建立哈弗曼树
		 */
		while (huffmanNode.size() > 1) {
			/**
			 * 获取了队首的两个最小的结点，并将两结点移出队列
			 */
			HuffmanNode min1 = huffmanNode.poll();
			HuffmanNode min2 = huffmanNode.poll();
			/**
			 * 再新建一个结点，连接两个最小的结点作为一棵新树
			 */
			HuffmanNode newnode = new HuffmanNode(0, min1.times + min2.times);
			newnode.lChild = min1;// 新结点的左孩子
			min1.fNode = newnode; // 父结点
			newnode.rChild = min2;// 新结点的右孩子
			min2.fNode = newnode;// 父结点
			/**
			 * 重新放回优先队列
			 */
			huffmanNode.add(newnode);
		}
		/**
		 * 返回头结点
		 */
		return huffmanNode.peek();
	}

这个方法的技术有两最重要的技术点：
1、链表
2、优先队列PriorityQueue
如果这两技术点熟悉的会这里就可以Pass!否则我们还得继续慢慢来了!
链表
链表的概念、特点和特性就不说了，就看看在java中创建链表的方法.
创建一个链表结点类：
public class HuffmanNode {
public int id = 0; // 次序
public int times = 0; // 频率
public HuffmanNode fNode = null; // 父结点
public HuffmanNode lChild = null; // 左孩子
public HuffmanNode rChild = null; // 右孩子

/**
* 构造函数
*
* @param id
*            次序
* @param times
*            出现的频率
*/
public HuffmanNode(int id, int times) {
this.id = id;
this.times = times;
}
}
        有了这样一个结点类之后，我们就可以很方便的创建链表了，当然这里我们其实不是单纯为了创建一个简单的链表，而是为了使用链表创建二叉树而设计的。所以说，二叉树是需要通过链表来实现。好啦!至于树结点之间如何连接就不说了。

优先队列PriorityQueue
优先队列不难要可以参考api文件手册，它就是一个可排序的队列，说不难但是非常重要！

/**
	 * 将频率存入优先队列
	 * @throws IOException
	 */
	public PriorityQueue<HuffmanNode> SaveList(String scrpath)
			throws IOException {
		/**
		 * 获取统计字节频率表
		 */
		byteCount = readFile(scrpath);
		/**
		 * 创建哈弗曼存储优先队列
		 */
		PriorityQueue<HuffmanNode> huffmanNode = new PriorityQueue<HuffmanNode>(100,new Comparator<HuffmanNode>() {
			/**
			 * 实现比较器内的方法
			 * @param o1
			 * @param o2
			 * @return
			 */
			public int compare(HuffmanNode o1, HuffmanNode o2) {
				return o1.times - o2.times;
			}
		});
		/**
		 * 把所有结点放入优先队列中去
		 */
		for (int i = 0; i < byteCount.length; i++) {
			if (byteCount[i] != 0) {
				HuffmanNode newnode = new HuffmanNode(i, byteCount[i]);
				huffmanNode.add(newnode);
			}
		}
		return huffmanNode;
	}

当我们构建完哈弗曼树之后，我们会发现，优先队列似乎是专门为构建哈弗曼树而创建的数据结构；总之，通过优先队列我们可很方便的实现哈弗曼树。

根据哈弗曼树生成哈弗曼编码
通过上一方法我们可以获取一棵哈弗曼树，由哈弗曼树来生成哈弗曼编码。请问实例分析：

/**
	 * 获得叶子节点的哈弗曼编码
	 * @throws IOException
	 */
	public Code[] getHuffmanCode(String scrpath) throws IOException {
		/**
		 * 获取哈弗曼树
		 */
		HuffmanNode huffmanNode = creatHuffmanTree(scrpath);
		// 只有一个结点的情况
		if (huffmanNode.fNode == null && huffmanNode.lChild == null
				&& huffmanNode.rChild == null) {
			Code hc = new Code();
			hc.node = "0";
			hc.n = hc.node.length();
			saveCode[huffmanNode.id] = hc;

		} else {
			getMB(huffmanNode, "");
		}
		return getsaveCode();
	}

从获取的哈弗曼树来判断，如果这个树只存在一个结点，那很好办，意味着被压缩的文件中只含有一种相同的字节，那么我们可以直接用“0”或“1”编码来代替它，那么在这种情况下自然是压缩比最高的情况，因为无论被压缩文件中有多少个字节，我每个字节只需要用一个二进制位来表示，那么我转换成压缩码后，一个byte就可代替被压缩文件中的8个字节。
当然一个文件中只存在同一种字节，那么被压缩也没有多大意义了，我们压缩是要适用所有的情况，那么我们来看看两个结点以上的编码方式：

/**
	 * 多个结点的情况，即出现两个以上的不同字节
	 * 
	 * @param root
	 *            结点
	 * @param s
	 *            编码
	 */
	public void getMB(HuffmanNode root, String s) {
		if ((root.lChild == null) && (root.rChild == null)) {
			Code hc = new Code();
			hc.node = s;
			hc.n = s.length();
			saveCode[root.id] = hc;
		}
		if (root.rChild != null) {
			getMB(root.rChild, s + '1');
		}
		if (root.lChild != null) {
			getMB(root.lChild, s + '0');
		}
	}

技术重点：
1、哈弗曼编码的存储方式
我们通过递归的方式访问到哈弗曼树的每个叶子结点，根据每个叶子结点生成哈弗曼编码写入编码存储对象中，那么这里我们需要创建一个编码存储对象：

/**
 * 结点编码
*/
public class Code {
		String node; //编码
		int n; //编码长度
}

        每个对象存储编码以及编码的长度，再将对象存储到数组中去，这里又需要创建一个基于Code这个对象的数组，Code[] saveCode = new Code[256]; 这里数组的长度也是256，如果仔细思考后，你会发现，这里与对应的被压缩文件内对应的字节是有联系的，这个数组的下标就是文件中的字节，那么下标对应里面的对象表示的就是他的哈弗曼编码和哈弗曼编码长度；这样我们的哈弗曼编码就生成了。

2、哈弗曼编码的表示
        到这里，其实已经很清楚了，我们用Code类的对象存储了哈弗曼编码，那么我们这里用的时String类表示的，但它最终的表示法不是String类，不然我们就不是实现压缩了，反而扩大了文件存量。我们最终要用二进制位表示写入文件中，那么我们会遇到怎样将哈弗曼二进制编码写入文件的问题，因为java并没有写二进制的方法，而只有写入一个byte,int 或其它基本类型，所以这里我们需要考虑如何将二进制码转换成一个byte写入文件，这样才能称得上是压缩嘛。

三、开始写压缩程序
        很抱歉！讲了这么久才讲到开始写压缩程序，但是请不要失望，因为技术的难点都在前面解决了，接下来我们就可以很顺利的完成压缩程序了，因为我们这个压缩程序是基于哈弗曼编码这个理论基础上，所以把哈弗曼编码的生成解决了，实际上就算是解决了主要问题，那接下来我们快速快决！请看流程图：

请看具体实现：
将哈弗曼编码表写入文件
什么是哈弗曼编码表呢？其实就是我们上一个环节中所做的事，把那个编码数组制成一个编码表写入文件就OK啦！
首先，把256个编码的长度都写进文件，这里我们256个编码中可能会有些编码长度是为0的，没关系！如实的写入就行了，也不在乎它占了那个字节的空间。
再次，把256个哈弗曼编码连成一个字符串（这里如果是要注重程序的空间复杂度，建议取指定长度的字符串后就转成byte写入文件，这样就不至于太占用内存的空间），字符串为空的不用连接，接着一次截取8个字符，转换成二进制位成为一个byte写入文件，记住是要将字符串转换成byte哦！
最后，还有一个很有关键的处理哦！我们在转到最后一个哈弗曼编码的时候也许会发现，哈弗曼编码不足8位，这个时候我们就需要被后缀0了。补多少个0通过判断一下就知道了，反正最后凑成8位就行了，是后缀0哦，不是前导0哦！
请看实例：

/**
	 * 将每个源文件中每个字节所对应的哈弗曼编码长度写入文件
	 * 
	 * @param saveCode
	 *            哈弗曼编码表
	 * @param outdataStream
	 *            文件输出流
	 * @throws IOException
	 *             异常机制
	 */
	private void writeByteSize(Code[] saveCode, BufferedOutputStream outdataStream)
			throws IOException {
		/**
		 * 遍历哈弗曼编码表，写入每个哈弗螺编码的长度
		 */
		for (int i = 0; i < saveCode.length; i++) {
			Code code = saveCode[i];
			if (code != null) {
				outdataStream.write(code.n);
			} else {
				/**
				 * 如果是没有一个字节，表示长度为0，因此写入一个byte =0 进去
				 */
				byte lengthnull = 0;
				outdataStream.write(lengthnull);
			}
		}
	}
/**
	 * 将哈弗曼编码表写入文件
	 * 
	 * @param saveCode
	 *            哈弗曼编码表
	 * @param outdataStream
	 *            文件输出流
	 * @throws IOException
	 */
	private void writeHuffmanCodeTable(Code[] saveCode,
			BufferedOutputStream outdataStream) throws IOException {
		String tranString = "";
		/**
		 * 获取整个哈弗曼编码
		 */
		for (int i = 0; i < saveCode.length; i++) {
			if (saveCode[i] != null) {
				tranString += saveCode[i].node;
			}
		}
		/**
		 * 将整个哈弗曼编码，按每8位依次写入文件
		 */
		String byteString = "";
		char[] codeArray = tranString.toCharArray();
		for (int i = 0; i < codeArray.length; i++) {
			byteString += codeArray[i];
			/**
			 * 满8位转成byte写入文件
			 */
			if (byteString.length() == 8) {
				int byteCode = transCode(byteString);
				outdataStream.write(byteCode); // 写入文件
				byteString = "";
			}
		}
		/**
		 * 剩余不能组成8位的编码，用0补足8位写入文件
		 */
		int surplusByte = (codeArray.length % 8);
		for (int i = 0; i < 8-surplusByte; i++) {
			byteString += '0';
		}
		outdataStream.write(transCode(byteString)); // 写入文件
	}
	

	/**
	 * 8位01字符转换成8位二进制的byte
	 * 
	 * @param byteString
	 *            8位01字符
	 */
	private int transCode(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 {
			System.out.println("字符转二进制时，字符数不是8位！！！");
			return 0;
		}
	}

transCode这个方法作为专门字符串编码转换二进制编码。

将文件中对应的哈弗曼编码写入文件
	其实这一步就很简单啦！重新读取一遍文件，按照哈弗曼编码表，把每个字节对应的哈弗曼编码写入文件，仿照编码表的方式组合成一个一个的byte写入文件，这里就可以看出哈弗曼编码表就像一本字典，我们对照字典就可以查出对应字节的哈夫曼编码了，接下来就写入编码就OK啦！到这里压缩原理其实也出来了！就这样简单！
	请看实例：
/**
	 * 将源文件按照哈弗曼编码将其写入压缩文件
	 * 
	 * @param saveCode
	 *            哈弗曼编码表
	 * @param outdataStream
	 *            文件输出流
	 * @throws IOException
	 */
	private void writeScrHuffmanFile(Code[] saveCode,
			BufferedOutputStream outdataStream) throws IOException {
		/**
		 * 创建源文件输入流，准备读取源文件中的信息，转换成哈弗曼编码将其写入压缩文件
		 */
		FileInputStream inputFileStream = new FileInputStream(scrpath);
		BufferedInputStream inputdataStream = new BufferedInputStream(inputFileStream);
		String tranString = "";
		while (inputdataStream.available() != 0) {// 文件读取结束标志 available()
			int ch = (int) inputdataStream.read();
			if(ch<0){//汉字处理
				tranString += saveCode[-ch+127].node;
			}else{
				tranString += saveCode[ch].node;
			}
			while (tranString.length() > 8) {// 加入的编码长度大于8时，转换成byte存入文件
				int byteCode = transCode(tranString.substring(0, 8));
				System.out.println("写进去"+byteCode);
				outdataStream.write(byteCode); // 写入文件
				// 删除前8位已存入文件的编码
				String temperray = tranString.substring(8, tranString.length());
				tranString ="";
				tranString =temperray.substring(0, temperray.length());
				temperray = "";
			}
		}
		/**
		 * 将剩余不足8位的用0补足8位，写入文件 ，并且将补0个数用一个byte再写入
		 */
		int unnecessary = tranString.length();
		System.out.println("tranString = ==== == = "+tranString);
		for (int i = 0; i < 8-unnecessary; i++) {
			tranString+='0';
		}
		//补足后再写入，并写入补足0的个数
		System.out.println("写进去"+transCode(tranString));
		outdataStream.write(transCode(tranString)); 
		outdataStream.write(8-unnecessary);//写入补足0的个数
		System.out.println("补进去"+(8-unnecessary)+"个0!!!!");
		/**
		 * 压缩文件写完结束，关闭文件输入、输出流
		 */
		outdataStream.flush();
		inputFileStream.close();
	}

到这里我们的压缩程序算是完成了，但细心会发现程序中还有一个细节没有讲到，那就是最后的编码不足8位时的处理，我想你也知道答案了，就是补几个“0”就好了，但是这次却还不够，如果单从压缩的角度来说，确实补几个“0”就OK了。但我们为了解压提供方便，这里我们还需要写入一个标记，要标记最后补了几个0；也许有人会问，为什么写入编码表的时候不要求写补了几个“0”，那是因为我们在之前同时写入了编码表的长度，256个编码对应的长度都已知了，那补了几个“0”是显而易见的！
刚看到流程图，也许大家会觉得这个环节很简单，走到这里才发现有很多细节方面需要处理，这样看来这个环节也不容易啊！但是其实的原理就是这样的！

四、测试
打完收工，可以去测试了！在测试的过程中，可以计算出理论的压缩存量大小，再比较实际压缩存量大小，如果与预期大小一致时，那么有压缩有可能成功了。确认是否真正成功那还需要解压后才能确定。

五、解压
如果哈弗曼压缩测试达到预期结果，其实再来写解压已经很简单了，解压就是压缩的逆过程，在这里也不做多的分享了，仅给出一个流程图作为参考：

在实现解压的过程中，需要注意这样些问题：
1、取出编码时要怎样截取出与哈弗曼编码匹配的编码，然后再去比照哈弗曼编码？
2、我们取出来的编码一般都是没有前导“0”；也就是说一个byte转换成字符串后表示的可能不是8位，byte会自动略去前导“0”，这就需要我们想办法补上前导“0”。
3、读取到最后一个字节时，要记得这最后一个字节表示的是前一个字节补后缀“0”的个数哦！
4、解压这个过程最关键的一步就是查哈弗曼编码表，这里可以多考虑一下如果优化代码，可以让查表更高效。

六、心得
这是java基础阶段的最后一个项目，做完这个项目才让我觉得什么是清晰的代码结构，前面做过泡泡堂的线程小游戏，但后来由于代码量的增加并且也不能有连续的时间去做游戏，所以导致自己过一段时间再去编写程序时，竟一下子理不清程序代码的结构；使得最终线程之间的动作无法匹配，做来做去让自己有些丧失信心了；但通过这次哈弗曼压缩项目的练习，让我对程序的代码结构有了比较深刻的认识，也意识到自己平时编写代码时，并不是解释不够多或不清晰，而是程序代码结构的混乱所带的困扰。
这次压缩项目中，我自己总结出了一套程序设计模式，当然我知道这套程序设计模式早已有人提出，我只是有幸通过身边老师的指导，学习到这些高效的编码模式，总的来说，我更加了解了面向对象程序的优势，每个对象都可以看成一个功能独立的模块，而整个软件工程就是由这些若干的对象拼装在一起，这样从一宏观的角度来说，这对成为了面向对象的一门学说。那么根据面向对象的这一优势，我们可以对象中的功能块分得更加的清晰和简要，例如在一个类当中，实现一个功能需要经历好几个步骤才能完成，这时当每一个步骤作为一个方法，仿照OSI参考模型一般“上层为下层提供接口，下层为上层服务”，以这种层次分明、结构清晰的方式来构建一个类，并且在实现的过程中，不断的测试每层的运行结果及状态，确保方法执行结果正确以及排除方法可能带来的安全隐患；依此层层递推，完成整个类的创建；这样不仅仅带来编写的高效，并且为后期的扩展和维护带来很大的方便，不会再为程序的结构混乱而浪费时间。
这种环环相扣的程序模式的确给我程序之路带来了新的一页。第一阶段结束了，现在对于java越来越有好感，过去觉得C++比java好，甚至有些贬低java不过就是C派生出来的一门语言，学java还不能学它的父亲C或C++，现在发现java编程的高效，让我转而更喜欢上这种更接近现实生活的编码语言。当然我必须承认自己的局限性，无论哪种语言都有它的优势和弱势，不应该仅仅依据这些很表面的东西来判定好坏，而应该更加努力的钻研，希望能够用好这项工具创建更多的价值。