哈夫曼压缩及解压的具体实现

数据结构中的哈夫曼编码可以用来制作一个压缩和解压的小项目。因此，需要先写出哈夫曼的编码，具体步骤如下：
首先要创建一个数组，其大小为256，用于存储字节，再从给定路径中逐个读取字节，统计每个字节出现的次数，跟据出现的次数进行排序，此时可以用一个优先队列PriorityQueue，但是PriorityQueue中比较器的方法需要重写过。代码如下：

public class MyComparator implements Comparator<Node>{
	public int compare(Node o1, Node o2) {
		return o1.count - o2.count;
	}
}

比较的是两者的次数，并传入先序队列的构造方法。根据队列的排序逐个取出，然后根据排序构造哈夫曼树，代码如下：

public Node bulid(PriorityQueue<Node> queue) {
		// 当队列中至少有2个结点时
		while (queue.size() > 1) {
			Node node1 = queue.poll();
			Node node2 = queue.poll();
			// 创建2个子结点的父结点
			Node root = new Node(node1.count + node2.count);
			node1.parent = root;
			node2.parent = root;
			root.left = node1;
			root.right = node2;
			queue.add(root);

		}
		Node root = queue.poll();
		return root;
	}

然后根据构造的树进行遍历，得到相应的哈夫曼编码，并记录下来。代码如下：

public void traverse(Node root) {
		if (root != null) {
			if ((root.left == null) && (root.right == null)) {
				// System.out.println(root.b);
				data data = new data();
				data.b = root.b;
				data.s = root.sign;
				list.add(data);// 将数组加入队列
			}
			traverse(root.left);
			traverse(root.right);
		}
	}

然后就可以开始进行压缩的工作，先将刚刚的字符串及对应的01编码逐个对应存入文件中，作为头文件。而后用源文件的路径创建输入流，将源文件逐个按字符串输入，根据字符串得到相应的01字符串，将01字符串存入一个byte数组中，待所有源文件均读取完毕后，将得到的与源文件相对于的01字符串数组每8个一取，得到相对于的byte数组。

/**
	 * 将8位的字符串转化为一个byte类型的字符串
	 * 
	 * @param str所需转换的01字符串
	 * @return转换后的byte的字符串
	 */
	public byte change(String str) {
		// 因为转换成数字，而原先传入的只是其字符，所以要减去0所对于的字符码，从而转换的byte才不会溢出
		int s = ((int) str.charAt(0) - 48) * 128 + ((int) str.charAt(1) - 48)
				* 64 + ((int) str.charAt(2) - 48) * 32
				+ ((int) str.charAt(3) - 48) * 16 + ((int) str.charAt(4) - 48)
				* 8 + ((int) str.charAt(5) - 48) * 4
				+ ((int) str.charAt(6) - 48) * 2 + ((int) str.charAt(7) - 48);
		byte by = (byte) s;
		return by;
	}

若最后末尾不足8位，需要补0，并且要记录补0的个数。

// 文件字符串01个数 = 字符次数 * 编码长度
			for (int i = 0; i < list.size(); i++) {
				data data = list.get(i);
				if (data.b < 0) {
					data.b += 256;
				}
				addnum += (datas[data.b] * data.s.length());
			}
			addzero = 8 - (addnum % 8);
			dos.write(addzero);

然后将转换后的byte数组逐个写入压缩文件中。如此，便基本实现了哈夫曼压缩。需要注意的是，如果字符所对应的哈夫曼编码超过8位，可以不用哈夫曼编码，而直接写入该字节即可。这可以算是对哈夫曼压缩的优化。
解压时只有逐个文件写入的顺序读出并进行还原即可以得到原来的文件。
值得注意的是，若创建的为文件基本输入输出流的话，是不可以直接读入一个int，当读取的数据超过一个byte类型的话，需要把int转换为一个byte数组存入，byte数组的大小为4。具体代码如下：

private byte[] Int2Byte(int num) {
		byte[] bs = new byte[4];
		bs[0] = (byte)((num >>> 24) & 0xFF);
		bs[1] = (byte)((num >>> 16) & 0xFF);
		bs[2] = (byte)((num >>> 8) & 0xFF);
		bs[3] = (byte)((num >>> 0) & 0xFF);
		return bs;
	}

同样在解压时需要把byte数组还原为一个int,具体实现如下：

private int Byte2Int(byte b[]){
		int n1=(int)b[0];
		int n2=(int)b[1];
		int n3=(int)b[2];
		int n4=(int)b[3];
		int n=((n1 << 24)& 0xFF)+((n2 << 16)& 0xFF)+((n3 << 8)& 0xFF)+((n4 << 0)& 0xFF);
		return n;
	}