|
文件压缩原理： 首先文件压缩是通过HuffmaCode实现的、整体思路通过读取文件获取字符出现频率，通过字符出现频率可以构建HuffmanTree，每个文件中出现的字符通过HuffmanTree获取HuffmanCode，从而将文件中的字符同过HuffmanTree获取相应编码，并写入压缩文件，从而完成文件压缩。 为什么通过HuffmanCode可以实现文件的压缩呢？ 原因：1.每个文件的字符种类有限。2.每个字符出现次数可能很多。3.HuffmanTree构造的特点：HuffmanTree越靠近根节点的叶子节点权值越大，路径越短；如果文件中的字符重复的越多，靠近根节点的叶子节点的权值越大，而这些字符的路径最短所以HuffmanCode就越短，这样在这些字符多的情况下压缩率越高。 如何产生HuffmanCode？ 1.产生HuffmanCode的条件是先构建HuffmanTree，从构建HuffmanTree的节点中选出权值最小、权值较小的节点；从而形成左右子树，再左右子树的权值相加，作为父亲节点的权值；再将父亲节点入到构建huffmanTree的节点集合中；再继续选最小、次小，直到集合中剩下一个节点时候，这个节点为根节点。 2.通过遍历HuffmanTree的所有叶子节点的路径来获取每个文件中出现的字符的HuffmanCode。 了解了这些压缩原理后，我们该如何实现文件压缩呢？ 文件压缩流程： 1.读取文件，统计字符出现次数。 2.通过统计出来的字符出现次数，来构建HuffmanTree。 3.获取HuffmanCode。 4.写如配置信息（每个字符出现的次数，方便解压时重构huffmanTree）。 5.读取文件，将文件中出现的字符的HuffmanCode依次压缩进压缩文件。 文件解压流程： 1.读取配置信息。 2.通过读取信息重构HuffmanTree。 3.通过编码遍历HuffmanTree来获取字符写入压缩文件。 关于构建HuffmanTree用到技术 1.堆：通过小堆来选取最小值和次小值。（前面有一篇讲堆的博客）。 2.仿函数：在堆中用到了仿函数（通过仿函数来比较CharInfo中的权重大小来建堆）。 3.HuffmanCode：因为HuffmanTree所有的信息的都在叶子节点中，而且每个叶子节点都有唯一确定的路径（根节点到叶子节点的路径），即这条路径就为HuffmanCode，而每个叶子节点又对应唯一的字符。 4.string类：用来保存HuffmanCode。 文件压缩的部分细节： 统计文件中所有字符的出现次数。由于Ascall码字符一共255个，只有前128个字符可以显示，定义字符变量时一定要定义成无符号型变量unsigned char ch如下，这是ch读不到文件的结束标志，所以我们可以用函数feof来代替文件的结束标志EOF,最重要的是文件的打开方式一定要是二进制的形式打开否则读不到汉字字符，将出现乱码。而这255个字符我们将采取哈希映射的方式来存储在_info[256]数组中。以数组下标映射每个字符，以方便字符与出现的次数相对应起来。在数组元素中保存字符编码和字符对应的次数。方便我们引索。
|