19.01.2011

                     文件压缩总结
          历时10多天，文件压缩终于能用了。从最开始的构造huffman树到最后的解压缩，遇到了不少纠结的难题。下面就和大家分享一下做文件压缩的心得。
          1.构建huffman树。由于数据结构基础有限，也想不到高明的压缩方法，便只能用书上的一种简单而实用的方法---huffman编码。Huffman树是一种特殊的二叉树，我把构建它分成了4部，建立了4个方法：
          a.统计传入数据中每个字符出现的次数，这个数据可以是一个文件，也可以是一个字符串。字符作为key，次数作为value存入一个map中。
          b.将上面得到的map作为参数，建立一个由TreeNode组成的ArrayList其中map的key值作为TreeNode的flag，map中的value作为TreeNode的weight。
          c.上面一步便得到了由huffman树叶子节点组成的ArrayList，然后就是建树了，由于huffman树的叶结点的个数为n，那么它的中间结点的个数肯定是n-1，由次每次对ArrayList由小到大排序，取出前面的最小值和次小值，新建一个结点，对这3个结点进行连接，然后新节点入队，前面两个出队，循环n-1次最终可得到连接好的huffman树。
          d.将得到的huffman树进行编码，得到编好码的huffman树。
          这4步c和d是最难的，d步的代码想了很久也没有想出来，最后还是问了别人才搞到递归算法，后来自己还设计了一种非递归的算法，递归和非递归的代码如下：

/**
  * 先序遍历huffman树,并得到其编码（递归算法）
  * @param root: 要遍历的huffman树
  * @param hfmCode: 所遍历结点的huffman编码
  */
public void preVisitTree(TreeNode root , String hfmCode){
	//如果根不为0
	if(root != null){
		root.setHuffmanCode(hfmCode);
		String lCode = hfmCode + "0";
		preVisitTree(root.getLchild() , lCode);
		String rCode = hfmCode+"1";
		preVisitTree(root.getRchild() , rCode);
	}
}

/**
  * 非递归获取哈夫曼编码
  * @param root: 哈夫曼树根节点
  */
public void setHfmCode(TreeNode root){
	java.util.ArrayList<TreeNode> treeList = new java.util.ArrayList<TreeNode>();
	treeList.add(root);
	TreeNode tempNode;//临时引用
	String hfmCode = "";
	//对huffman树层次遍历
	while(!treeList.isEmpty()){
		tempNode = treeList.remove(0);//头元素出队进行运算
		hfmCode = tempNode.getHuffmanCode();
		if(tempNode.getLchild() != null){
			treeList.add(tempNode.getLchild());
			hfmCode = tempNode.getHuffmanCode();
			tempNode.getLchild().setHuffmanCode(hfmCode + "0");
		}
		if(tempNode.getRchild() != null){
			treeList.add(tempNode.getRchild());
			hfmCode = tempNode.getHuffmanCode();
			tempNode.getRchild().setHuffmanCode(hfmCode + "1");
		}
	}
}

     
         2.压缩文件到指定目录。至此，压缩的第一部就已经完成，我们得到了一个由file中所有字节作为flag，其个数作为weight的带huffman编码的树。
          我们压缩后的文件应该分为两部分：码表和压缩体。
          码表是一个由字节作为key，字节对应的huffman编码作为value的map对象。个人认为如果将码表压缩在文件前端，对解压缩应该要方便一些。因为解压缩一开始就可以把码表读出来保存在map对象中。码表压缩时第一位应该保存一个int值，是map的size()。而且压缩码表的时候可以用一个小技巧，压缩时的码表是map<Byte , String>由于解压缩是是用字符串找字节，而map中的方法containsKey()和get()都只能是由key值找value值，为了方便可以先存value(String)再存key(Byte)，当然也可以先存key(Byte)再存value(String)上一部就留给解压缩码表时完成。值得注意的是无论先存什么，为了后来操作方便都应该在存入String前存入一个int值是这个String(huffman)编码的长度。
      压缩压缩体的时候也有许多小技巧，为了方便操作，第一个存入的数据可以是这个压缩体的大小。而第二个则是字符串末尾补零的个数，因为将文件的所有字节转换为一个字符串，这个串不一定就是8的倍数，最后很有可能要补0，为此我专门写了一个方法来计算压缩体的大小和补零的个数，利用的则是层次遍历第一部的到的huffman树，代码如下：

/**
  * 得到补零的个数和压缩后文件的字节数 
  * @param src:源文件地址
  * @param root:压缩用huffman树根节点
  */
public void getCompressInfo(String src, TreeNode root) {
	// 辅助计数器
	int tempCount = 0; 
	// 建立一个结点队列
	java.util.ArrayList<TreeNode> treeList = new java.util.ArrayList<TreeNode>();
	treeList.add(root); 
	TreeNode tempNode;// 临时变量
	while (!treeList.isEmpty()) {
		tempNode = treeList.remove(0);
		// 如果是叶子结点,则累加其1,0个数
		if (tempNode.getLchild() == null && tempNode.getRchild() == null) {
			// 统计补零个数
			numOfZero += tempNode.getWeight() * tempNode.getHuffmanCode().length();
			numOfZero = numOfZero % 8;
			// 统计字节数
			tempCount += tempNode.getWeight() * tempNode.getHuffmanCode().length();
			count += tempCount / 8;
			tempCount = tempCount % 8;
		}
		// 如果有左右孩子则入队
		if (tempNode.getLchild() != null) {
			treeList.add(tempNode.getLchild());
		}
		if (tempNode.getRchild() != null) {
			treeList.add(tempNode.getRchild());
		}
	}
	if (tempCount != 0) {
		count++;
	}
	numOfZero = 8 - numOfZero;
}

     存好这两个数据以后则将源文件中的字节一个个的读出来，读出一个，从map中找到其对应的huffmanCode，一步步累加，当这个huffmanCode大于等于8的时候则将前八位转换成一个int(这里可以自己写方法也可以用效率更高的Java API方法Integer.parseInt)，写入后八位。然后截取掉前八位，这两个步骤都可以用String类中的substring方法。
3.将文件解压缩。解压缩是压缩的逆过程，但比压缩更加纠结。解压缩第一步就是读出码表将其保存如一个map<String , Byte>中。
读完码表后便可以对压缩体解压。解压时需要注意的是要和压缩时压缩进去的数据一一对应。错一点点就会产生蝴蝶效应，全部解错。另外和压缩一样，解压缩也可以读一个换成String然后在码表中找到对应的字节，剩下的找不到的前加到下一个String，其中最要注意的就是在用Integer.toBinaryString时，前面位的0可能丢失，如果得到的字符串不足八位，则前面一定要补零。实现这一步的关键代码如下：

// 处理前面所有未补零的字节
while (count > 1) {
	b = dis.read();//从压缩文件中读取第一个压缩体的字节		String tempStr = Integer.toBinaryString(b);// 得到压缩后的字节，并将其转化为字符串
	int strLen = tempStr.length();//如果tempStr不足八位.前面补零
	if(strLen < 8){
		for(int i = 0 ; i < 8-strLen ; i++){
			tempStr = "0" + tempStr;
		}
	}
	str = str + tempStr;
	count--;
	// 一位一位的查找map中是否由对应的字节,有则写入
	while (str.length() != 0) {
		if (str.length() == 1) {
			firstCode += str;
			str = "";
		}
		if (str.length() > 1) {
			firstCode += str.substring(0, 1);
			str = str.substring(1);
		}
		if (map.containsKey(firstCode)) {
			dos.write(map.get(firstCode));// 得到串对应的value值，并写入
			firstCode = "";// 将firstCode重新初始化
		}
	}
}

if(numOfZero != 0){//处理最后的补零位
	b = dis.read();
	String tempStr = Integer.toBinaryString(b);
	if(tempStr.length() < 8){
		int k = 8 - tempStr.length();
		for(int i = 0 ; i < k ; i++){
			tempStr = "0" + tempStr;
		}
	}
	tempStr = tempStr.substring(0,8 - numOfZero);
	str = str+tempStr;
	for(int i = 0 ; i < tempStr.length() ; i++){
		// 一位一位的查找map中是否由对应的字节,有则写入
		if(str.length() == 1){
			firstCode += str;
			str = "";
		}
		if (str.length() > 1) {
			firstCode += str.substring(0,1);
			str = str.substring(1);
		}
		if (map.containsKey(firstCode)) {
			dos.write(map.get(firstCode));// 得到串对应的value值，并写入
			firstCode = "";// 将firstCode重新初始化
		}
	}
}

     由这三步，压缩基本就可以实现了，在这次做压缩的过程中，遇到了许多的bug，我们应当直面惨淡的bug，不断的System.out.println()测试每一步数据，找到他再仔细思考，找到一个修改一个。让写出的程序可以针对每一种特殊情况的发生。