哈夫曼压缩软件的制作

一、关于压缩的基础知识

引用

压缩软件是利用算法将文件有损或无损地处理，以达到保留最多文件信息，而令文件体积变小的应用软件。压缩软件一般同时具有解压缩的功能。压缩软件的的基本原理是查找文件内的重复字节,并建立一个相同字节的"词典"文件,并用一个代码表示,比如在文件里有几处有一个相同的词"中华人民共和国"用一个代码表示并写入"词典"文件,这样就可以达到缩小文件的目的。常见的压缩软件有WinRAR ,好压(Haozip),WinZip,7-Zip,WinMount,Peazip等等。

哈夫曼树作为数据结构二叉树章节中最为华彩的一部分，有着其独特的魅力。给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，这样的二叉树便是哈夫曼树，也称为最优二叉树。
       
二、关于哈夫曼算法

引用

  Huffman算法是一种基于统计的压缩方法。它的本质就是对文本文件中的字符进行重新编码，对于使用频率越高的字符，其编码也越短。但是任何2个字符的编码， 是不能出现向前包含的。也就是说字符A(假设为00)的编码的前段，不可能为字符B（则B的编码不可能为001，因为这里B的编码中包含了A的前段00，这会给解码难带来不必要的困难，所以这是不允许的）的编码。经过编码后的文本文件，主要包含2个部分：Huffman码表部分和压缩内容部分。解压缩的时候，先把Huffman码表取出来，然后对压缩内容部分各个字符进行逐一解码,形成源文件。
        哈夫曼编码生成步骤：
        ①扫描要压缩的文件，对字符出现的频率进行计算。
        ②把字符按出现的频率进行排序，组成一个队列。
        ③把出现频率最低（权值）的两个字符作为叶子节点，它们的权值之和为根节点组成一棵树。
        ④把上面叶子节点的两个字符从队列中移除，并把它们组成的根节点加入到队列。
        ⑤把队列重新进行排序。重复步骤③④⑤直到队列中只有一个节点为止。
        ⑥把这棵树上的根节点定义为0（可自行定义0或1）左边为0，右边为1。这样就可以得到每个叶子节点的哈夫曼编码了。

三、开发的大体思路

压缩：
        1、将要压缩的文件一个一个字节的读出来即扫描要压缩的文件，并统计每个字节的权值即出现的频率。
        2、以每个字节的权值来构造哈夫曼树，并给每个字节进行哈夫曼编码。
        3、将每个字节和其对应得哈夫曼编码存放进一个Map中，即码表。
        4、以这个码表为依照，将文件中的所有字节一一进行编码（生成10字符串），最后在把所有字节的编码依次末尾相加合成一个10字符串。
        5、将这个10字符串重新组合，8个为一组，若最后一组不足8个则补0，并记录补0的个数，将每一组的10字符串转化为一个字节，
并将所有的10字符串合成一个字节数组，数组的最后一个元素存放补0的个数。
        6、创建一个压缩文件，先将码表的大小写入文件，再将码表写入文件（码表里还有每个字节的哈夫曼编码长度的信息）。
        7、最后将之前生成的字节数组写入文件（文件的主要信息）。

        解压缩：
        1、将压缩的文件同样一个一个字节的读出来。
        2、先读出码表的大小，再通过码表的大小读出码表，并将码表的信息存放进一个Map。
        3、再接着读出后面的所有字节，并转化成一个10字符串。
        4、通过与码表的匹配，从10字符串的第一个字符开始读，若读到的子字符串与码表的某个字节的的编码相同，解压出相应的字节，把该字节保存起来。
并把上面的子字符串从编码中删除，重复上一步骤，直到该项编码解析完成，最后将此10字符串还原成原来的文件的一个个字节。
        5、再将这些字节写入一个新的文件，后缀名改成和原来文件一样，就能打开了。


1、压缩文件

/**
 * 压缩的文件操作
 * 
 * @author king
 * 
 */
public class CompressFileOption {

	/**
	 * 读取文件
	 * 
	 * @param path
	 *            :文件路径
	 * @return:将文件的内容以字节数组的样式返回
	 */
	public static byte[] readFile(String path) {
		byte[] dataByte = null;
		try {
			java.io.FileInputStream fis = new java.io.FileInputStream(path);
			int size = fis.available();// 可读的字节数
			dataByte = new byte[size];
			fis.read(dataByte);

		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return dataByte;
	}

	/**
	 * 将码表的相关信息写入文件
	 * 
	 * @param fileSize
	 *            :原文件大小
	 * @param map
	 *            :存放码表的map
	 * @param listCh
	 *            :存放关键码的字符队列
	 * @param path
	 *            :文件路径
	 * @throws Exception
	 */
	public static void writeMap(int fileSize,
			java.util.HashMap<Byte, String> map, List<Byte> listBy, String path)
			throws Exception {

		java.io.FileOutputStream fos = new java.io.FileOutputStream(path);
		java.io.DataOutputStream dos = new java.io.DataOutputStream(fos);

		dos.writeInt(fileSize);// 将原文件大小写入文件
		int mapSize = map.size();// 码表的大小
		dos.writeInt(mapSize);// //将码表的大小写入文件
		for (int i = 0; i < mapSize; i++) {
			fos.write(listBy.get(i));// 将每个字节写入文件
			String hfmcode_next = map.get(listBy.get(i));// 得到每个字节对应的哈夫曼编码
			byte codeSize = (byte) hfmcode_next.length();// 每个字节对应的哈夫曼编码大小
			fos.write(codeSize);// 将每个字节对应的哈夫曼编码大小写入文件
			dos.writeChars(hfmcode_next);// 将每个字符对应的哈夫曼编码写入文件
		}
		dos.flush();
		fos.close();
	}

	/**
	 * 将压缩好的字节数组写入文件
	 * 
	 * @param b
	 *            :压缩好的字节数组
	 * @param path
	 *            :文件路径
	 */
	public static void writeFile(byte[] b, String path) {

		try {
			java.io.FileOutputStream fos = new java.io.FileOutputStream(path,
					true);
			java.io.DataOutputStream dos = new java.io.DataOutputStream(fos);
			// 写入字节数组的大小
			dos.writeInt(b.length);
			fos.write(b);
			fos.flush();
			fos.close();
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	/**
	 * 将10字符串转化为一个字节
	 * 
	 * @param str
	 *            :传入的字符串
	 * @return:一个字节
	 */
	private byte CharArrayToByte(String str) {
		char[] c = str.toCharArray();// 将字符串str转化为字符数组c
		int len = c.length;
		byte[] b = new byte[len];
		byte value = 0;
		byte value_next;
		for (int i = 0; i < len; i++) {
			b[i] = Byte.parseByte(c[i] + "");
			// System.out.println(b[i]);
		}
		for (int i = 0; i < len; i++) {
			value_next = (byte) (b[i] * Math.pow(2, len - i - 1));// 幂计算
			value = (byte) (value + value_next);
		}
		return value;
	}

	/**
	 * 将10字符串以8个为一组转化为一个字节数组
	 * 
	 * @param str
	 * @return
	 */
	private byte[] StringToByteArray(String str) {
		char[] c = str.toCharArray();// 将字节串str转化为字符数组c
		int len = c.length;// 字符串字符的个数
		int lenByte;
		String s = "";
		char c_next;
		byte[] b;
		if (len % 8 == 0) {// 如果字符串的长度能被8整除
			lenByte = len / 8 + 1;
			b = new byte[lenByte];
			for (int i = 0; i < lenByte - 1; i++) {
				for (int j = i * 8; j < (i + 1) * 8; j++) {
					c_next = c[j];
					s = s + c_next;
				}
				System.out.println("第" + i + "个字符串：" + s);
				b[i] = CharArrayToByte(s);
				s = "";
				System.out.println("第" + i + "个字符串转化为字节后的值：" + b[i]);
			}
			b[lenByte - 1] = 0;// 字节数组的最后一个存放补0的个数
		} else {// 如果字符串的长度不能被8整除

			lenByte = len / 8 + 2;
			b = new byte[lenByte];
			int remainder = len % 8;// 求出除8的余数
			int zeroNum = 8 - remainder;// 补0的个数
			System.out.println("补0数：" + zeroNum);
			System.out.println("原字符串：" + str);
			for (int i = 0; i < zeroNum; i++) {
				str = str + '0';// 在字符串后面补0
			}
			System.out.println("补0后的字符串：" + str);
			c = str.toCharArray();
			System.out.println("补0后的字符串的字符个数：" + c.length);
			for (int i = 0; i < lenByte - 1; i++) {
				for (int j = i * 8; j < (i + 1) * 8; j++) {
					c_next = c[j];
					s = s + c_next;
				}
				System.out.println("第" + i + "个字符串：" + s);
				b[i] = CharArrayToByte(s);
				s = "";
				System.out.println("第" + i + "个字符串转化为字节后的值：" + b[i]);
			}
			b[lenByte - 1] = (byte) zeroNum;// 字节数组的最后一个存放补0的个数
		}
		return b;
	}

	/**
	 * 压缩文件
	 * 
	 * @param path1
	 *            :原文件路径
	 * @param path2
	 *            :压缩后的文件路径
	 * @throws Exception
	 */
	public void CompressFile(String path1, String path2) throws Exception {
		// 从文件中得到字节数组
		byte[] b = CompressFileOption.readFile(path1);
		int b_size = b.length;// 原文件大小
		byte[] b_compress;// 字节数组，存放压缩的字符串

		String hfmcode = "";// 文件内所有字节的哈夫曼编码
		String hfmcode_next;// 文件中每个字节的哈夫曼编码
		// 计算字符串中每个字节的权值，并返回一个存放字节和它对应权值的节点队列
		List<TreeNode> list = calWeight.calweight(b);
		int size = list.size();
		Huffman hfm = new Huffman();
		// 构建哈夫曼树并返回根节点
		TreeNode root = hfm.createHuffman(list);
		// 创建哈夫曼编码使其与字符一一对应
		hfm.createHfmCode(root, "");

		java.util.HashMap<Byte, String> map = hfm.getMap();// 得到码表
		List<Byte> listBy = hfm.getList();// 得到存放关键码队列

		System.out.println("mapsize---->:" + map.size());
		System.out.println("b---->:" + b.length);
		for (int i = 0; i < b_size; i++) {
			// 得到每个字节的哈夫曼编码
			hfmcode_next = map.get(b[i]);
			System.out.println("第"+i+"个： " + b[i] + "的编码：" + hfmcode_next);
			hfmcode = hfmcode + hfmcode_next;// 将每个字节的哈夫曼编码依次相加为一个01字符串
		}
		System.out.println("01串大小：" + hfmcode.length());
		System.out.println("01串：" + hfmcode);
		char[] ch = hfmcode.toCharArray();
		System.out.println("01串的大小：" + ch.length);

		b_compress = StringToByteArray(hfmcode);// 得到字节数组
		for (int i = 0; i < b_compress.length; i++) {
			System.out.println("第" + i + "个字节" + b_compress[i]);
		}
		// 将文件大小和码表相关信息写入文件
		writeMap(b_size, map, listBy, path2);
		// 将字节数组写入文件
		writeFile(b_compress, path2);
	}

2、解压缩

/**
 * 解压缩的文件操作
 * 
 * @author king
 * 
 */
public class UncompressFileOption {

	public static long fileSize;

	/**
	 * 将8位10字符串前面缺0的补上0
	 * 
	 * @param str
	 * @return
	 */
	private String addZero(String str) {
		int strLen = str.length();
		int zeroNum;
		if (strLen < 8) {// 若字符串长度小于8则补0
			zeroNum = 8 - strLen;
			for (int i = 0; i < zeroNum; i++) {
				str = "0" + str;
			}
		}
		return str;
	}

	/**
	 * 将整型数组还原成之前的10串，即文件内容的哈夫曼编码
	 * 
	 * @param n
	 * @return
	 */
	private String InttoBinaryString(int[] n) {
		int len = n.length;
		String[] s = new String[len];// 一个字符串数组存放二进制数据
		String BinaryStr = "";
		for (int i = 0; i < len - 1; i++) {
			s[i] = Integer.toBinaryString(n[i]);
			s[i] = addZero(s[i]);
			BinaryStr = BinaryStr + s[i];
		}
		System.out.println("二进制形式表示:" + BinaryStr);
		int BinaryStrLen = BinaryStr.length();// 得到为减0前的字符串大小
		int zeroSub = n[len - 1];// 之前在末尾补0的个数，现在减去
		System.out.println("减0前的字符串大小:" + BinaryStrLen);
		System.out.println("需要在字符串末尾减0的个数表示:" + zeroSub);
		BinaryStr = BinaryStr.substring(0, BinaryStrLen - zeroSub);
		System.out.println("减0后的字符串大小:" + (BinaryStrLen - zeroSub));
		System.out.println("减0后的二进制形式表示:" + BinaryStr);
		return BinaryStr;
	}

	/**
	 * 字符串匹配，判断字符串child是否为parent的前子串
	 * 
	 * @param parent
	 * @param child
	 * @return
	 */
	private boolean StringMatch(String parent, String child) {

		char[] p = parent.toCharArray();
		char[] c = child.toCharArray();
		// System.out.println("数组p的长度：" + p.length);
		// System.out.println("数组c的长度：" + c.length);
		boolean b = false;
		for (int i = 0; i < c.length; i++) {
			if (c[i] == p[i]) {
				b = true;
			} else {
				b = false;
				break;// 有一个字符不匹配则跳出循环
			}
		}
		return b;
	}

	/**
	 * 解压缩文件
	 * 
	 * @param path2
	 *            :压缩后的文件路径
	 * @param path3
	 *            :解压缩后的文件路径
	 * @throws Exception
	 */
	public void UncompressFile(String path2, String path3) throws Exception {

		HashMap<Byte, String> map = new HashMap<Byte, String>();
		java.io.FileInputStream fis = new java.io.FileInputStream(path2);
		java.io.DataInputStream dis = new java.io.DataInputStream(fis);

		java.io.FileOutputStream fos = new java.io.FileOutputStream(path3);

		fileSize = dis.readInt();// 得到原文件的大小
		int mapSize = dis.readInt();// 得到码表的大小
		byte[] mapKey = new byte[mapSize];// 创建一个字符数组,存放码表中的字节
		byte codeSize;// 每个字节对应的哈夫曼编码大小
		String hfmcode_next = "";
		// 读取码表内容
		for (int i = 0; i < mapSize; i++) {
			mapKey[i] = (byte) fis.read();// 得到第i个字节
			codeSize = (byte) fis.read();// 得到每个字节对应的哈夫曼编码大小
			char[] codeChar = new char[codeSize];
			for (int j = 0; j < codeSize; j++) {
				codeChar[j] = dis.readChar();
				hfmcode_next = hfmcode_next + codeChar[j];
			}
			map.put(mapKey[i], hfmcode_next);// 将键值对放入Map中
			hfmcode_next = "";
		}
		int len = dis.readInt();// 得到压缩好的字节数组的大小
		System.out.println("压缩好的字节数组的大小: " + len);
		byte[] b = new byte[len];// 字节数组，存放压缩的字节串
		int[] n = new int[len];// 整型数组
		fis.read(b);// 得到压缩好的文件的字节数组
		for (int i = 0; i < b.length; i++) {
			System.out.println("第" + i + "个字节:" + b[i]);
			// 将字节还原成原来的整型数据
			if (b[i] < 0) {
				n[i] = b[i] + 256;
			} else {
				n[i] = b[i];
			}
			System.out.println("第" + i + "个字节的整型表示:" + n[i]);
		}
		String formerStr = InttoBinaryString(n);// 得到原10串

		System.out.println("formerStr:" + formerStr);
		int size = map.size();
		System.out.println("mapsize:" + size);

		int endIndex = formerStr.length();
		System.out.println("endIndex:" + endIndex);
		int beginIndex;

		// byte[] fileData = new byte[fileSize];
		int count = 0;// 记录文件当前是第几个字节

		while (!formerStr.isEmpty()) {// 如果字符串不为空

			String child;
			for (int i = 0; i < mapKey.length; i++) {
				child = map.get(mapKey[i]);
				if (formerStr.isEmpty()) {// 若字符串为空
					break;
				}
				if (StringMatch(formerStr, child)) {// 若匹配
					// 一个字节字节的写入文件
					fos.write(mapKey[i]);
					count++;
					beginIndex = child.length();
					formerStr = formerStr.substring(beginIndex, endIndex);
					endIndex = endIndex - beginIndex;
				}
			}
		}
		fos.flush();
		fos.close();
	}

五、项目展示










六、项目感想

1、如今最大的缺陷就是相率问题还没有解决，一旦压缩大的文件就要等很久，甚至失去响应。
2、界面依旧很简陋，需要改进。

评论

1 楼 if(i!=我){} 2012-10-31  

1、用了流，却不知道流是用来干什么的
2、缓冲、缓冲、缓冲！
3、哈夫曼算法对巩固树的相关知识很有帮助，但不是一个实用的压缩算法。想研究压缩，就从gzip或者deflate开始吧。