哈弗曼编码__压缩任意格式文件.doc

哈弗曼编码__压缩任意格式文件.doc 本程序是本人学习数据结构时自己写的，可以压缩、解压缩任意格式文件。由于本人水平有限，里面会有缺陷，若有兴趣，可以多多指正!!! Email:e9999e@163.com ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////[BEGIN]//////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //时间:2012年5月9日10:24:19 //编译器:VC++6.0 //数据组织:参见程序的详细说明 //功能:哈弗曼压缩文件(可以 压缩并解压 任何格式文件)，参见程序的详细说明 //历时:2天 /* *************************************************************************** Bug修复 *************************************************************************** 【2012.5.10 18:13:00 修复了:文件中只有一种英文字符无法压缩和解压缩的Bug。解决参见本文件中哈夫曼树的创建函数】 【2012.5.10 20:49:00 修复了:不能准确还原文件的Bug，是解压文件与原文件大小等完全相同，另外还可以压缩、解压其他任何类型文件(doc、jpg等)。具体修复办法参见压缩、解压缩】 */ /* *************************************************************************** 程序的详细说明 *************************************************************************** 本程序是适用于所有格式文件。。。。 //-----------------【注意，以下是对于文本文件的思考。因为是二进制操作文件，故适用于所有格式文件】 如何实现压缩文件呢，首先考虑到字符存储问题，英文是一个字节存储的，汉子是两个字节存储的。 都属于定长存储(定长编码)，可以利用哈夫曼树对其进行编码，使其转换为变长的前缀编码。 那么，如何实现编码的转换呢 , 考虑到汉子也可以将其两个字节分别处理，故这里采用单个字节处理的办法， 将每个字节进行编码。 首先读取文件，计算出每个字节出现的次数。次数即权值，对其进行构造哈夫曼树，然后求出编码，将编码存储在一个 二维数组中。再次打开想要压缩的文件，每读入一个字节，就对其进行编码，并写入压缩文件。 由于将编码后的数据写入压缩文件时，需整个字节操作，即编码数据刚好整个字节时(可 以是多个字节)写入压缩文件， 故此处利用一个整形变量作为缓冲。 解压缩时，需再次将 与压缩时相同的哈夫曼树 构造出来，以便进行译码。因此压缩时存储了，原文件中各个字节出现的 次数(也就是权值)，这样就能再次构造出哈夫曼树。【注意】这里当然也可以将哈夫曼树存储下来，解压时再次重构。 解压时，读取字符出现的次数，重构出哈夫曼树，进行译码。这里也是读取整个字节(可以是多个)，按位进行译码。 */ ///////////////////////////////////////////////////////////////////////////////////////// #include #include #include using namespace std; ///////////////////////////////////////////////////////////////////////////////////////// //HuffmanNode 节点定义 struct HuffmanNode { unsigned char value; //字符内容 double cost; //权值 HuffmanNode *leftChild, *rightChild,*parent; HuffmanNode(int weight = 0) : value(0), cost(weight), leftChild(NULL), rightChild(NULL), parent(NULL) {} }; ///////////////////////////////////////////////////////////////////////////////////////// //常量、全局变量定义 const double MaxCost = 10000000000.0; //最大权值 const int MaxCodeLen = 300; //原文件、压缩文件、解压缩文件——文件名 const char strSrcFileName[300] = "压缩前.txt"; const char strCompreFileName[300] = "压缩文件.HuffYaSuo"; const char strDeComFileName[300] = "解压后.txt"; int g_numTimes[256]; //存储各个字符出现次数 HuffmanNode *g_pHuffTree = NULL; //指向最终的哈弗曼树 unsigned int code[256][MaxCodeLen]; //存储压缩时使用的编码，有遍历哈夫曼树得到 unsigned int tempCode[MaxCodeLen]; //临时存储编码，用于将编码赋给code[][] ///////////////////////////////////////////////////////////////////////////////////////// //统计出字符出现次数 //统计各个字符出现次数 void CountNumTimes(void) { memset(g_numTimes, 0, 256*sizeof(double)); //注意，以二进制文件打开。若以ASCII文件打开会出问题!!!!!------>【即，文件可能读取不完】 ifstream fin(strSrcFileName, ios_base::binary); unsigned char cTemp; //不要用fin >> cTemp，因为 >> 会对输入进行格式化，导致有的字符读入失败 while(fin.read((char *)&cTemp,sizeof(cTemp))) { g_numTimes[cTemp]++; } fin.close(); } ///////////////////////////////////////////////////////////////////////////////////////// //构造哈夫曼树 //找出根节点权值最小的一颗树，被CreateHuffTree()调用 HuffmanNode * FindMinCostTree(HuffmanNode **&pTreeList) { double cost = MaxCost; int num = -1; for(int i=0; i<256; i++) { if(pTreeList[i] != NULL && !(pTreeList[i]->cost-0<0.000001 && pTreeList[i]->cost-0>-0.000001) && pTreeList[i]->cost < cost) { cost = pTreeList[i]->cost; num = i; } } if(num != -1) { HuffmanNode *pTree = pTreeList[num]; pTreeList[num] = NULL; return pTree; } else { return NULL; } } //将两颗树合并，被CreateHuffTree()调用 void MergeTwoTree(HuffmanNode *firstMin, HuffmanNode *secondMin, HuffmanNode **&pTreeList) { HuffmanNode *pHuffNode = new HuffmanNode(firstMin->cost + secondMin->cost); pHuffNode->leftChild = firstMin; pHuffNode->rightChild = secondMin; firstMin->parent = pHuffNode; secondMin->parent = pHuffNode; for(int i=0; i<256; i++) { if(pTreeList[i] == NULL) { pTreeList[i] = pHuffNode; break; } } } //构造哈弗曼树 void CreateHuffTree(void) { HuffmanNode **pTreeList = new HuffmanNode *[256]; for(int i=0; i<256; i++) { pTreeList[i] = new HuffmanNode(g_numTimes[i]); pTreeList[i]->value = i; } HuffmanNode *firstMin, *secondMin; while(1)//每次循环求的两个根节点权值最小的树，并合并 { firstMin = FindMinCostTree(pTreeList); secondMin = FindMinCostTree(pTreeList); if(secondMin == NULL) { g_pHuffTree = firstMin; //----------------------------【解决Bug】------------------------------- //只有一个节点情况，对应于文件中只有一种字符，为了解决无法编码，需将 其作为根节点的左孩子，或右孩子，此处为左孩子 if(g_pHuffTree->leftChild==NULL && g_pHuffTree->rightChild==NULL) { g_pHuffTree->leftChild = new HuffmanNode; g_pHuffTree->leftChild->value = g_pHuffTree->value; } //---------------------------------------------------------------------- break; } MergeTwoTree(firstMin, secondMin, pTreeList); } delete []pTreeList; } //--------------测试-------------------------------- //前序遍历哈夫曼树 //void PreOrderTraverse(HuffmanNode *pNode) //{ // static int outNum = 0; // if(pNode != NULL) // { // cout << (int)pNode->value << ":" << (int)pNode->cost << " "; // ++outNum%15==14 ? (cout << endl) : (cout << ""); // // PreOrderTraverse(pNode->leftChild); // PreOrderTraverse(pNode->rightChild); // } //} //-------------------------------------------------- ///////////////////////////////////////////////////////////////////////////////////////// //求出压缩时的编码 //初始化code等数组全部成员为-1 void InitCode() { for(int i=0; ivalue; // while(pNode != g_pHuffTree) // { // pNode->parent->leftChild==pNode ? tempCode[i++]=0 : tempCode[i++]=1; // pNode = pNode->parent; // } // int j = 0; // for(i=i-1; i>=0; i--,j++) // { // code[num][j] = tempCode[i]; // } //} //求出编码 void FindCode(HuffmanNode *pNode) { static num = 0; static codeNum = 0; if(pNode!=NULL && pNode->leftChild==NULL && pNode->rightChild==NULL)//是叶节点 { // CodeBack(pNode); //向上回溯求编码 CopyCode(pNode->value); //将临时存储空间的编码复制给编码存储数组。注意，也可以利用上一句进行求的编码 } if(pNode!=NULL && pNode->leftChild!=NULL) { tempCode[codeNum++] = 0; //左子树，将编码0写入临时存储空间 FindCode(pNode->leftChild); //递归左子树 tempCode[--codeNum] = -1; //回退，将退回路径上的编码从临时存储空间清除 } if(pNode!=NULL && pNode->rightChild!=NULL) { tempCode[codeNum++] = 1; //右子树，将编码1写入临时存储空间 FindCode(pNode->rightChild);//递归右子树 tempCode[--codeNum] = -1; //回退，将退回路径上的编码从临时存储空间清除 } } ///////////////////////////////////////////////////////////////////////////////////////// //压缩 //压缩文件 void CompressionFile() { //注意，以二进制文件打开。若以ASCII文件打开会出问题!!!!!------>【即，文件可能读取不完】 ifstream fin(strSrcFileName, ios_base::binary); ofstream fout(strCompreFileName, ios_base::binary); //将字符出现的次数写入文件，以便下次构造哈夫曼树，解码 fout.write((char *)g_numTimes, sizeof(g_numTimes)); //----------------------------【解决Bug】------------------------------- //将文件长度(字节数)写入文件，以便解压缩时，准确无误还原文件 fin.seekg(0, ios_base::end); int fileLen = fin.tellg(); fout.write((char *)&fileLen, sizeof(fileLen)); fin.seekg(0, ios_base::beg); //---------------------------------------------------------------------- unsigned char cTemp; //存储从文件读入的单字节字符 unsigned int outBuff = 0; //缓冲编码，以便写入整个字节 int numOutBuff = 0; //指示outBuff当前中的编码位数，以便满32个 (numOutBuff到达31)，写入文件 int i = 0; //指示当前字符的正在往outBuff中加入的编码在数组中的 位置 while(fin.read((char *)&cTemp,sizeof(cTemp))) { i = 0; while(-1 != code[cTemp][i]) { outBuff |= (code[cTemp][i]<<(numOutBuff)); ++numOutBuff; if(numOutBuff > sizeof(outBuff)*8-1) { fout.write((char *)&outBuff,sizeof(outBuff)); outBuff = 0; numOutBuff = 0; } i++; } } //----------------------------【解决Bug】------------------------------- //将最后未写入的内容写入压缩文件(【注意，此处还是编码之后的】) fout.write((char *)&outBuff,sizeof(outBuff)); //---------------------------------------------------------------------- fin.close(); fout.close(); } ///////////////////////////////////////////////////////////////////////////////////////// //解压缩 //解压缩文件 void DeCompressionFile() { //注意，以二进制文件打开，若以ASCII文件打开会出问题!!!!!------>【即，文件可能读取不完】 ifstream fin(strCompreFileName, ios_base::binary); ofstream fout(strDeComFileName, ios_base::binary); //从文件读入字符出现次数，构造哈夫曼树 fin.read((char *)g_numTimes, 256*4); CreateHuffTree();//构造哈夫曼树 //读取原文件长度(字节数)，以便准确无误还原文件，不多也不少一个字节，【注意】计算机操作文件最小单位为字节 int fileLen = 0; fin.read((char *)&fileLen, sizeof(fileLen)); unsigned int inBuff; //存储读取的内容 int numInBuff = sizeof(inBuff)*8+100; //初始时大于inBuff的字节数 HuffmanNode *pNode = g_pHuffTree; //指向哈夫曼树的节点 int i = -1; //0左子树，1右子树，初始为-1 bool flagOver = 0; //指示是否结束最外层循环的标记 int numBytes = 0; //记录输出文件(解压后的文件)当前字节数，等于fileLen时停止解压 while(!flagOver) { pNode = g_pHuffTree; while(!(pNode->leftChild==NULL && pNode->rightChild==NULL)) { if(numInBuff > sizeof(inBuff)*8-1) { numInBuff = 0; if(!(fin.read((char *)&inBuff,sizeof(inBuff))))//读取文件内容 { flagOver = 1;//修改结束标记 } } i = inBuff>>(numInBuff) & 1;//读取一个编码 numInBuff++; if(i == 0)//编码为0，往哈弗曼树的左子树 { pNode = pNode->leftChild; } else//否则，右子树 { pNode = pNode->rightChild; } } if(pNode->leftChild==NULL && pNode->rightChild==NULL)//到达叶节点，就是最终译码字符，写入解压文件 { fout.write((char *)&pNode->value,sizeof(pNode->value)); //----------------------------【解决Bug】------------------------------- if(++numBytes == fileLen)//已解压原文件所有内容，停止 { break; } //---------------------------------------------------------------------- } } fin.close(); fout.close(); } ///////////////////////////////////////////////////////////////////////////////////////// int main(void) { cout << "******************* 提示 *******************\n"; cout << "输入 1 压缩文件: " << strSrcFileName << endl; cout << "输入 2 解压缩文件: " << strCompreFileName << endl; cout << "输入 3 压缩并解压文件: " << strSrcFileName << "--->" << strCompreFileName << "--->" << strDeComFileName << endl; cout << "输入其他退出 \n\n\n"; cout << "请输入:"; int flag = 0; cin >> flag; //压缩文件 if(1 == flag || 3 == flag) { CountNumTimes(); //统计出次数 CreateHuffTree(); //构造哈夫曼树 InitCode(); //初始化编码数组 FindCode(g_pHuffTree); //遍历哈夫曼树，得出各个字符的编码 CompressionFile(); //压缩文件 cout << "压缩文件成功!!!" << endl; ifstream fin(strSrcFileName, ios_base::binary); ifstream fin_2(strCompreFileName, ios_base::binary); fin.seekg(0, ios_base::end); float fileLen = fin.tellg(); cout << "压缩前大小为: " << fileLen/1024 << " KB" << endl; fin_2.seekg(0, ios_base::end); float fileLen_2 = fin_2.tellg(); cout << "压缩后大小为: " << fileLen_2/1024 << " KB" << endl; cout << "压缩了 " << (fileLen-fileLen_2)/1024 << " KB" << endl; fin.close(); fin_2.close(); } //解压文件 if(2 == flag || 3 == flag) { DeCompressionFile(); //解压缩 cout << "解压文件成功!!!" << endl; ifstream fin_3(strCompreFileName); ifstream fin_4(strDeComFileName); fin_3.seekg(0, ios_base::end); float fileLen_3 = fin_3.tellg(); cout << "解压前大小为: " << fileLen_3/1024 << " KB" << endl; fin_4.seekg(0, ios_base::end); float fileLen_4 = fin_4.tellg(); cout << "解压后大小为: " << fileLen_4/1024 << " KB" << endl; fin_3.close(); fin_4.close(); } return 0; } ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////[END]////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////