文件压缩(哈弗曼编码)

哈弗曼文件压缩的基本原理:

1.统计要压缩文件中各字符出现的频率。采用哈弗曼压缩的前提是：待压缩的文件中各字符出现的频率相差甚远，这样才体现出哈弗曼压缩的优点。

   该方法可以通过使用hashMap()来统计次数。

public static HashMap<Byte, Integer> count(String path) {
		HashMap<Byte, Integer> map = new HashMap<Byte, Integer>();//
		// 创建一个HashMap得对象，用来放数字以及该数字出现的次数
		try {

			File f = new File(path);

			FileInputStream fis = new FileInputStream(f);// 申明一个文件输入流
			// 转成缓冲流
			BufferedInputStream bis = new BufferedInputStream(fis);
			// name = f.getName();
			int t = bis.read();
			while (t != -1) {// 如果未到达结尾
				byte b = (byte) t;
				if (map.containsKey(b)) {// 如果map里面包含number键
					int value = map.get(b);// 就可以通过get函数得到number对应的value的值
					value++;// 使次数加1
					map.put(b, value);
				} else {// 如果map里面不包含number键
					map.put(b, 1);// number的次数只有一次
				}
				// 继续读取下一个
				t = bis.read();

			}

		} catch (Exception ef) {
			ef.printStackTrace();
		}

		return map;
	}

 

2.通过字节频率构造结点对象，并将所有的结点对象放到优先队列中去。每个结点对象包含两个域：从文件中读到的字节和该字节出现的频率，两者是一一对应起来的。

public static PriorityQueue<TreeNode> createQueue(HashMap<Byte, Integer> map) {
		PriorityQueue<TreeNode> nodeQueue = new PriorityQueue<TreeNode>(10,
				new Comparator<TreeNode>() {// 构造一个优先队列
					public int compare(cn.gyl608.TreeNode o1,
							cn.gyl608.TreeNode o2) {// 自动排序的方法
						return o1.count - o2.count;
					}

				});
		// 遍历
		Set<Byte> keys = map.keySet();
		// 得到迭代器
		Iterator<Byte> iter = keys.iterator();
		while (iter.hasNext()) {// 如果后面还有元素
			byte key = iter.next();// 取得K
			int value = map.get(key);// 根据K得到v

			TreeNode node = new TreeNode(key, value);// 构造成一个结点

			nodeQueue.add(node);// 将结点加到优先队列中去
		}
		return nodeQueue;// 返回这个优先队列
	}

 3.根据优先队列中的结点对象来创建哈弗曼树。

创建哈弗曼树的基本思路：

(1)先得到队列中结点对象的字节频率域最小和次小的两个结点对象，并将这两个结点对象从队列中移除。

(2)将这两个结点对象构造成新的结点对象(该结点的频率域值是：将得到的两个结点对象的频率域值相加，数据域值在压缩中没用到，故可以不考虑)并将新得到的结点对象加入到队列中。

(3)重复(1)(2)步骤，直到队列中只剩下一个结点对象。

 

 

public static TreeNode createHfmTree(PriorityQueue<TreeNode> nodeQueue) {
		TreeNode last = null;// 申明一個指向隊列最後一個結點，也就是樹的根部
		while (nodeQueue.size() > 1) {// 如果隊列中至少還存在兩個結點
			TreeNode node1 = nodeQueue.poll();// 取出并移除隊列的頭
			TreeNode node2 = nodeQueue.poll();
			TreeNode node3 = new TreeNode();// 重新生成一個新的結點
			node3.setCount(node1.getCount() + node2.getCount());// 它的頻率則是前兩個頻率之和
			node3.setLeft(node1);// 將這三個結點建立樹形結构
			node3.setRight(node2);
			node1.setParent(node3);
			node2.setParent(node3);
			nodeQueue.add(node3);// 將新生成的結點加到最優隊列中去,它會自動將其排序
			if (nodeQueue.size() == 1) {// 如果只剩下一个结点
				last = nodeQueue.poll();// 得到这个结点
				last.setParent(null);// 并将这个结点的父结点设为空
			}
		}
		return last;// 返回根结点
	}

 

 4.对叶子结点进行哈弗曼编码

我们必须要明白一点：是对叶子结点的数据域（文件中出现的各字符）进行编码，而并非是频率域，频率域只是方便我们建哈弗曼树而已。

public static HashMap<Byte, String> getHfmCode(TreeNode node, String s) {
		if (node.getLeft() != null) {// 如果根结点的左子树不为空
			getHfmCode(node.getLeft(), s + "0");// 递归调用
		}// if
		if (node.getRight() != null) {// 如果根结点的右子树不为空
			getHfmCode(node.getRight(), s + "1");// 递归调用
		}// if
		if (node.getLeft() == null || node.getRight() == null) {// 如果是叶子结点
			map.put(node.getData(), s);// 则将叶子结点的值以及该字节的编码写到map中去。
		}// if
		return map;// 返回map表
	}

 

5.通过哈弗曼编码将待压缩文件的字符转换成01字符串

6.将得到的字符串转换成byte数组。

(1)先判断该字符串是否能被8整除，如果能被8整除，该字节数组的长度是整除8得到的商+1，数组中最后一个元素的值是倒数第二个补0的个数。如果不能被8整除，该字节数组的长度就应该是整除8得到的商+2,数组中最后一个元素的值是倒数第二个补0的个数。

(2)然后将每8个字符转换成一个10进制，存到byte数组中去。

public static byte[] createByteArray(String str01) {
		int chu=str01.length()/8;
		String s1=str01.substring(chu*8);//截取得到字符串8整数后的字符
		byte c[]=s1.getBytes();
		int s = 0;
		int i = 0, j;
		int temp = 0;
		for(int n=0;n<c.length;n++){
			temp+=(c[n]-48)*Math.pow(2, 7-n);//求倒数第2个字节的大小
		}
		byte b[] = str01.getBytes();// 将字符数组转换成字节数组，方便将二进制转为十进制
		for (int k = 0; k < b.length; k++) {
			b[k] = (byte) (b[k] - 48);
		}
		byte a[];
		if (b.length % 8 == 0) {// 如果该字符串正好是8的倍数
			a = new byte[b.length / 8 + 1];
			a[a.length - 1] = 0;// 那么要返回数组的最后一个数就为0
		} else {
			a = new byte[b.length / 8 + 2];
			a[a.length - 1] = (byte) (8 - b.length % 8);// 那么该数组的最后一个数就是补0的个数
		}
		while (i < a.length - 2) {// a数组中最后一个是补0的个数，实际操作到次后个元素
			for (j = 0; j < b.length; j++) {
				if (b[j] == 1) {// 如果数组c的值为1
					s = (int) (s + Math.pow(2, (7 - (j - 8 * i))));// 累积求和
				}// if
				if (j == 8 * (i + 1) - 1) {// 当有8个元素时
					a[i] = (byte) s;// 就将求出的和放到a数组中去
					i++;
					s = 0;// 并从新使s的值赋为0
				}// if
				
			}// for
		}// while
		a[a.length - 2] = (byte) temp;
		return a;
	}

 

 

7.将待压缩文件的文件名，以及字节——哈弗曼编码的码表，字节数组写到文件中。以便解压缩过程中需要用到。

 

解压缩的基本思路：

1.先将带压缩文件的文件名，码表和字节数组读取出来。

2.将字节数组中的每个元素值转换成二进制，并将其连接成一个字符串。

3.将字符串中的每个字符与码表中的编码比较，若相等，则从下个字符开始比较，若不相等，在继续跟下一个字符组成新的字符串，再与编码比较，依次进行比较。

4.将解析得到的字符写到文件中。

 

评论

2 楼 fenger_chui 2011-09-02  

基本功很扎实呀

1 楼 pclnn 2011-08-13  

初学者路过，瞻仰，多有收获，多谢分享。