数据结构之霍夫曼压缩，更易理解文件压缩过程

中间遇到过很多问题，不断的找办法，其实网上有很多前辈遇到过类似的问题，基本上我们目前这个学习阶段遇到的都有解决方法，我体会很深，需要不断坚持和学习；在学习霍夫曼的过程中，我了解了其他的lzw字典压缩方法，可以用于文件夹的压缩，这也算意外收获吧，凡事亲力亲为，必然收获很大；

<!--EndFragment-->

 

1.霍夫曼树应用（利用霍夫曼编码实现了文件的压缩和解压，代码有点多,树的运用主要在Tree这个类里面）；

功能:实现单个文件压缩的和解压;（500MB左右的文件夹我用系统给的api里面的方法实现了，代码很短，用eclipse写的，这个不能实现文件夹的操作，另外一个博客里面写了压缩文件件夹的方法）;

压缩：

1.利用字节流读取计算文件里面每一字节出现次数;

2.用出现次数来作为节点权值构建哈弗曼树;

3.利用节点类构建哈弗曼树的时候给节点添加属性来记录编码;

4.利用递归得到每一个叶子节点的哈弗曼编码，然后获得所有字节的01串；

5.利用已经得到的01串进行byte和string类型转换实现进一步压缩;

6. 接下来便是写文件，但是这才是需要细心的地方：

       （写入顺序）压缩文件的内容：

         a.将原文件大小写入文件// dos.writeInt(fileSize);

         b.将码表的大小写入文件//dos.writeInt(mapSize);

         c.将每个字节写入文件//fos.write(listBy.get(i));

         d.将每个字节对应的哈夫曼编码大小写入文件//fos.write(codeSize);

         e.将每个字符对应的哈夫曼编码写入文件

        //   dos.writeChars(hfmcode_next); 

         f.写入压缩后的字节数组的大小

         g.写入压缩后的文件内容

解压：

  1.fileSize = dis.readInt();// 得到原文件的大小

  2.int mapSize = dis.readInt();// 得到码表的大小

  3. 利用循环读取码表内容，开始存入为名称，大小，编码（前面两个使用byte类型写入，编码是writeChars(),则取出来时也要对应，将取得的字节，名称，还有编码存入map，清空hadmcode_next最后得到码表map。

   4.int len = dis.readInt();// 得到压缩好的字节数组的大小

   5.得到压缩时存入的文件的字节数组，转换成Int[]补0然后得到01串

   6.解码过程，取得数组中第一个数或者字节，然后遍历码表，用码表键的字节名称与之进行匹配，解码

 

（写的有点口语化，如果看不清楚，请直接去程序里面看，写的很详细！）

 

 

使用方法：

（没有写界面，因为只能压缩一个单文件）首先的新建一个用于测试的文件，最好里面的字节重复率高一点，因为这样哈弗曼编码会越短进而压缩率会高； 打开Main类,已经new了一个jieya和yasuo类的实例，可以分别调用实现压缩和解压；文件路径可以修改一下；

 

3.详细设计(详细代码附在文件里面，需要的话可以免费下载)

注意：这个程序有5个类，分别是Node,Tree,yasuo,jieya，Main;

 

<!--EndFragment-->

<!--EndFragment-->