压缩软件（哈夫曼算法实现）.doc

压缩软件（哈夫曼算法实现） 项目总结 算法CC++C#DOS 　　一、在讲具体代码实现之前，先给大家普及一下压缩软件的相关知识 引用 压缩软件是利用算法将文件有损或无损地处理，以达到保留最多文件信息，而令文件体积变小的应用软件。压缩软件一般同时具有解压缩的功能。压缩软件的的基本原理是查找文件内的重复字节,并建立一个相同字节的词典文件,并用一个代码表示,比如在文件里有几处有一个相同的词中华人民共和国用一个代码表示并写入词典文件,这样就可以达到缩小文件的目的。常见的压缩软件有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、压缩文件 Java代码 ? /** ? ?*?压缩的文件操作 ? ?*? ? ?*?@author?king ? ?*? ? ?*/?? public?class?CompressFileOption?{ ?? ?? ????/** ? ?????*?读取文件 ? ?????*? ? ?????*?@param?path ? ?????*????????????:文件路径 ? ?????*?@return:将文件的内容以字节数组的样式返回 ? ??