文件压缩(哈弗曼编码)

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

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++;// 使次数加1map.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();// 取得Kint value = map.get(key);// 根据K得到vTreeNode 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");// 递归调用}// ifif (node.getRight() != null) {// 如果根结点的右子树不为空getHfmCode(node.getRight(), s + "1");// 递归调用}// ifif (node.getLeft() == null || node.getRight() == null) {// 如果是叶子结点map.put(node.getData(), s);// 则将叶子结点的值以及该字节的编码写到map中去。}// ifreturn 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的值为1s = (int) (s + Math.pow(2, (7 - (j - 8 * i))));// 累积求和}// ifif (j == 8 * (i + 1) - 1) {// 当有8个元素时a[i] = (byte) s;// 就将求出的和放到a数组中去i++;s = 0;// 并从新使s的值赋为0}// if}// for}// whilea[a.length - 2] = (byte) temp;return a;}

?

?

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

?

解压缩的基本思路：

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

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

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

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

?

1 楼 pclnn 2011-08-13 初学者路过，瞻仰，多有收获，多谢分享。 2 楼 fenger_chui 2011-09-02 基本功很扎实呀