压缩软件(哈夫曼算法实现) 项目总结_C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > 压缩软件(哈夫曼算法实现) 项目总结

压缩软件(哈夫曼算法实现) 项目总结

 2011/10/31 8:28:57  王者无敌Java  http://javaprince.iteye.com  我要评论(0)
  • 摘要:一、在讲具体代码实现之前,先给大家普及一下压缩软件的相关知识引用压缩软件是利用算法将文件有损或无损地处理,以达到保留最多文件信息,而令文件体积变小的应用软件。压缩软件一般同时具有解压缩的功能。压缩软件的的基本原理是查找文件内的重复字节,并建立一个相同字节的"词典"文件,并用一个代码表示,比如在文件里有几处有一个相同的词"中华人民共和国"用一个代码表示并写入"词典"文件,这样就可以达到缩小文件的目的。常见的压缩软件有WinRAR,好压(Haozip),WinZip,7-Zip,WinMount
  • 标签:总结 实现 项目 压缩 软件 算法
  一、在讲具体代码实现之前,先给大家普及一下压缩软件的相关知识引用压缩软件是利用算法将文件有损或无损地处理,以达到保留最多文件信息,而令文件体积变小的应用软件。压缩软件一般同时具有解压缩的功能。压缩软件的的基本原理是查找文件内的重复字节,并建立一个相同字节的"词典"文件,并用一个代码表示,比如在文件里有几处有一个相同的词"中华人民共和国"用一个代码表示并写入"词典"文件,这样就可以达到缩小文件的目的。常见的压缩软件有WinRAR ,好压(Haozip),WinZip,7-Zip,WinMount,Peazip等等。

        哈夫曼树作为数据结构hashu.html" target="_blank">二叉树章节中最为华彩的一部分,有着其独特的魅力。给定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.浏览要压缩的文件并指定压缩后的文件路径


3.压缩文本文件的效果


4.解压缩文件及效果




5.压缩bmp格式图片文件效果明显,但是压缩和解压的时间都很长,需改进


  • 大小: 24.6 KB
  • 大小: 25.4 KB
  • 大小: 27.2 KB
  • 大小: 6.6 KB
  • 大小: 7.2 KB
  • CompressFile.rar (533.6 KB)
  • 下载次数: 312
  • 大小: 8.7 KB
  • 查看图片附件
发表评论
用户名: 匿名