一、实现功能
1.压缩文本文件 ：xzip 源文件名字 压缩后文件名字
2.解压文本文件 ：xuzip 压缩文件名字 解压后文件名字
3.压缩比大约18%左右(与文件内容有关系)
因为文件内容都是重复的所以这里压缩比比较高。
4.做成了类似Linux内置命令的样子放在了/bin目录下(这样可以自动补全路径)
最后cmp比对一下压缩前后的两个文件发现两个文件完全一样。
二、理论证明
压缩文本文档为什么可行?
1.一个char占8位,所以哈弗曼编码格式压缩之后，应该是少于8个字符(8层字符最多拥有２^8个叶子节点)。即使有些时候多于8个长度字符(树可能不是平衡的，大部分集中到了某一支)但是出现的频度不同，编码短的出现的频度高，所以还是可以达到压缩的效果。
2.ASCII码数量一共128个字符，从0～127编码，ASCII码中表示的字符首位都是０，所以建树一般应该会小于8层，所以利用哈弗曼编码形成新的编码方式的每个字符平均是小于八位的，从而实现压缩的功能。
压缩一般文件是否可行?
理论上是行不通的，不排除个别时候可以，但是绝大多数大文件应该是不可以只利用哈弗曼编码压缩的。因为对于一般文件来说，他并不是我们之前那种可以显示的字符，就是说我们如果按一个字节一个字节读出来的话就会有一些乱码，因为有首位是1的情况，那么8位就有２^8种编码方式，利用哈弗曼建树的话平均就是8层（２ ^8个叶子节点），达不到压缩的效果。比如我尝试压缩一个图片，图片反而变大了，虽然解码后还是图片本身，但是没有达到压缩的效果。
三、代码设计
1.数据结构
(1)哈弗曼树采用二叉链表存储，节点如下:
struct HuffmanNode{
HuffmanNode(char k,int w):key(k),weight(w),lchild(NULL),rchild(NULL){}
HuffmanNode(){}//提供三种构造方法
HuffmanNode(int w):weight(w),lchild(NULL),rchild(NULL){}
char key;
int weight;
HuffmanNode *lchild;
HuffmanNode *rchild;
};
(2)设计了两个类
HuffmanTreel类:用来处理关于哈弗曼编码的问题
主要方法有:
void buildTree(const map<char,unsigned> &mp,int mode);//建树
void getStr(HuffmanNode *p,string &str);//h获得新字符的编码方式
File类：用来从文件中读取数据和写入数据、编码、译码等工作
主要方法有:
map<char,unsigned> getMap(const string &s);//统计文件出现频率建立map,用来建树
void encoded(string src,string des);//src是源文件，des是压缩后的文件,编码
void decoding(string src,string des);//src是压缩文件,des是解压后的文件,译码
void writeHead(string &des);//向文件头部写入解压所需要的信息
string getBin(unsigned num);//私有方法内部辅助方法,把数字转为二进制
2.设计思想
File类继承HuffmanTree类的方法，首先读取文件，统计文件中每个字符出现的频度，在利用得到的Map建立树，建树的时候利用优先队列(根据需要重载),也可以自己写一个堆结构实现，然后再重新读取文件，利用新建成的树对文件重新编码，在把新编码凑够８位，或者32位转换成char或者int写入文件(此处逻辑处理写的比较复杂)。译码时首先读出首部个字符频度的信息，建立Map,建立树，利用建立的树恢复文件。
/* 编码函数，根据vector中的新编码方式，重新编码写入文件 */
void File::encoded(string src,string des)
{
getMap(src);
buildTree(mp,0);
//将map信息写入文件头部
writeHead(des);
char ch;//存放每次读取到的一个字符数据
string tmp = "";//存取链接到的32为字符串
int num = 0;//记录tmp中的01个数
int flag = 0;//凑够32位时，用来跳过一次读取,并且记录上次剩余
int lack0 = 0;
ifstream in(src,ios::in | ios::binary );
ofstream out(des,ios::out | ios::binary | ios::app);
if(!in) cout << "Error" << endl;
if(!out) cout << "Error" << endl;
while(in.peek() != EOF){
if(!flag)//flag非0对应上一个字符超出的情况,flag是的话说明上次tmp中有剩余就不读取了
ch = in.get();
if(num < 32){
int lack = 32 - num;//算出差多少个01
if(!flag){//当前串从0开始使用
/* 分两种情况一种下当前字符不足，另一种下一个字符超出 */
if((int)v[ch].size() <= lack){//不足
tmp += v[ch];
num += (int)v[ch].size();
}else{
//tmp字符串大于lack时候只要取需要的，做好标记
tmp += v[ch].substr(flag,lack);
flag = lack;
num += lack;
}
}else{//上一轮有剩余此时串是空的
tmp += v[ch].substr(flag);
num += tmp.size();
flag = 0;//flag重新置为0
}
}
if(num == 32){//凑够32个字节
unsigned int w = 0;
/* out << strToInt(tmp);//转换成整数写入 */
w = strToInt(tmp);
/* out << w; *///这样是以字符串的形式写入的
out.write((char*)(&w),sizeof(w));
/* cout << "w = " << w << endl; */
tmp.clear();
num = 0;
}
}
long long size = out.tellp();
/* 最后不够需要补0补齐 */
if(num != 0){
lack0 = 32 - num;
tmp.append(lack0,'0');
unsigned int w = 0;
w = strToInt(tmp);
/* out << w; */
out.write((char*)(&w),sizeof(w));
/* cout << "w = " << w << endl; */
}
/* cout << "size = " << size << endl; */
/* cout << "lack0 = " << lack0 << endl; */
out.write((char*)&size,sizeof(long long ));
out.write((char*)&lack0,sizeof(int));
in.close();
out.close();
return ;
}
3.不足和改进
(1)写完之后看别人的代码，发现写的太麻烦了，虽然没有库函数提供按位读出的功能，但是可以自己实现一个函数:
int getBit(ifstream &in)
{
static int i = 0;//用来计数返回了几位了
static unsigned char ch;//接受读取到的信息
unsigned char bit[8] = {128,64,32,16,8,4,2,1};
i++;
if(i == 8)
{
ch = in.get();
i = 0;
}
return ch&bit[i];
}
(2)另外树也不必采用二叉链表来存储,用数组来存储也是可以的。
源码:github