利用哈夫曼树实现文件的压缩与解压缩 压缩： 1、统计出文件中相同字符出现的次数 2、获取哈夫曼编码 次数作为权值构建哈夫曼树 3、重新编码，写回压缩文件 保存头文件： 源文件后缀 编码信息的行数 每个字符的权 保存编码
解压缩： 1、获取原文件后缀 2、获取每个字符出现的次数，即权值 3、利用之前后的的权值，还原哈夫曼树 4、找到对应的叶子节点，将信息保存到解压文件中 在写压缩文件之前，首先需要实现堆和哈夫曼树 源代码戳这里 (https://coding.net/u/g33_N/p/fileCompress/git)
#define _CRT_SECURE_NO_DEPRECATE #include"HuffManTree.h" #include<assert.h> struct FileInfo { FileInfo() :_count(0) {} unsigned char _ch;//当前字符 size_t _count;//当前字符出现的次数 std::string _strCode;//当前字符的哈夫曼编码 //重载+ FileInfo operator+(const FileInfo& fileInfo) { FileInfo ret(*this); ret._count += fileInfo._count; return ret; } //重载< bool operator<(const FileInfo& fileInfo)const { return _count<fileInfo._count; } //重载!= bool operator != (const FileInfo& fileInfo)const { return _count != fileInfo._count; } }; class CompressFile { public: CompressFile() { for (size_t idx = 0; idx < 256; ++idx) { _fileInfo[idx]._ch = idx; _fileInfo[idx]._count = 0;//每一个字符出现的次数初始化为0 } } void FileCount(const std::string& strFileName) { //统计字符出现的次数 FILE* fOut = fopen(strFileName.c_str(), "r");//打开一个文件 assert(fOut); unsigned char rBuf[1024];//存取读到的文件内容 while (1) { size_t rSize = fread(rBuf, 1, 1024, fOut);//返回从文件中读到的字节数 if (rSize == 0) break; for (size_t idx = 0; idx < rSize; ++idx) { _fileInfo[rBuf[idx]]._count++;//统计每个字符出现的次数 } } } //获取编码信息 void GetHuffManCode() { // 创建HuffManTree HuffmanTree<FileInfo> ht(_fileInfo, sizeof(_fileInfo) / sizeof(_fileInfo[0]), FileInfo()); _GetHuffManCode(ht.GetRoot());//获取哈夫曼编码 } //文件压缩 void FileCopress(const std::string& strFileName)//参数为要压缩的文件名 { FileCount(strFileName); GetHuffManCode(); unsigned char value = 0;//一个字节，保存8位编码 unsigned char wBuff[1024];//保存编码信息 int wSize = 0; FILE* fOut = fopen(strFileName.c_str(), "rb"); assert(fOut); std::string fileName = GetFileName(strFileName.c_str());//获取文件名 fileName += ".hzp";//给文件名加后缀（压缩后） FILE* fIn = fopen(fileName.c_str(), "wb");//打开一个文件写入压缩信息 assert(fIn); unsigned char rBuf[1024]; std::string strCode; int pos = 0; //保存编码信息 std::string strHead; strHead += GetPostFix(strFileName.c_str());//获取文件后缀 strHead += '\n'; char strLineCount[32];//编码信息的行数 size_t lineCount = 0; //统计每个字符出现的次数 a:1 size_t idx = 0; while (idx<256) { if (_fileInfo[idx]._count) { if（_fileInfo[idx]._ch!='\n'） strCode += _fileInfo[idx]._ch; strCode += ':'; _itoa(_fileInfo[idx]._count, strLineCount, 10); strCode += strLineCount; lineCount++; strCode += '\n'; } idx++; } _itoa(lineCount, strLineCount, 10); strHead += strLineCount;//保存行数 strHead += '\n'; strHead += strCode;//保存编码信息 fwrite(strHead.c_str(), 1, strHead.length(), fIn);//此处写入文件的大小一定是写入内容的实际大小，否则写入文件的内容之后会出现随机值 fseek(fOut, 0, SEEK_SET);//跳到文件开头，之前已读到结尾 //遍历编码，8位一字节写入Buff中 while (1) { size_t rSize = fread(rBuf, 1, 1024, fOut); if (rSize == 0) break; for (size_t idx = 0; idx < rSize; ++idx) { std::string strCode = _fileInfo[rBuf[idx]]._strCode; for (size_t idx = 0; idx < strCode.length(); ++idx) { value <<= 1;//若编码为0，左移一位 if (strCode[idx] == '1')//若编码为1，value或1 { value |= 1; } if (++pos == 8)//满8位，将value写入buff里 { wBuff[wSize++] = value; if (wSize == 1024)//buff大小满1024写入文件 { fwrite(wBuff, 1, 1024, fIn); wSize = 0;//写入文件之后将buff索引置0 } pos = 0;//value写入buff后，pos置0 value = 0;//value也置0，重新保存下一个字节 } } } } if (pos < 8)//若编码读完后，pos<8,buff大小也不满1024，将编码左移至最高位，然后写入buff,最终写入文件 { value <<= (8 - pos); wBuff[wSize++] = value; fwrite(wBuff, 1, wSize, fIn); } //关闭文件 fclose(fOut); fclose(fIn); } //解压缩 void UnCompressFile(const std::string& compressFile) { FILE* fOut = fopen(compressFile.c_str(), "rb");//打开一个压缩文件 assert(fOut); //获取源文件后缀 std::string strPostFix = ReadLine(fOut); //获取信息行数 int LineCount = atoi(ReadLine(fOut).c_str()); //获取压缩后的编码 int idx = 0; while (idx < LineCount) { std::string strCode = ReadLine(fOut);//读取每一行信息 _fileInfo[(unsigned char )strCode[0]]._count = atoi(strCode.substr(2).c_str());//获取每个字符出现的次数，也就是权 ++idx; } //利用上边获取到的权还原哈夫曼树 HuffmanTree<FileInfo> ht(_fileInfo, sizeof(_fileInfo) / sizeof(_fileInfo[0]), FileInfo()); HuffmanTreeNode<FileInfo>* pRoot = ht.GetRoot();//获取哈夫曼树的根 _GetHuffManCode(pRoot);//获取哈夫曼编码 std::string fileName = GetFileName(compressFile.c_str());//获取文件名 std::string strFix = GetPostFix(compressFile.c_str());//文件后缀 fileName += strPostFix;//解压缩后文件名及后缀 FILE* fIn = fopen(fileName.c_str(), "wb");// 打开一个文件写入解压缩后的信息 assert(fIn); unsigned char rBuff[1024]; int pos = 8; unsigned char wBuff[1024]; size_t wSize = 0; long long FileSize = pRoot->_weight._count;//压缩信息的大小 HuffmanTreeNode<FileInfo>* pCur = pRoot; //解压缩 while (1&&pCur) { int rSize = fread(rBuff, 1, 1024, fOut); if (rSize == 0) return; for (int idx = 0; idx < rSize; ++idx) { while (1) { --pos; if (rBuff[idx] & (1 << pos))//若当前位为1，则访问右子树，为0，则访问左子树 pCur = pCur->_pRight; else pCur = pCur->_pLeft; if (pCur&&pCur->_pLeft == NULL&&pCur->_pRight == NULL)//当前节点为叶子节点 { wBuff[wSize++] = pCur->_weight._ch;//将当前字符写入buff if (wSize == 1024)//若buff满1024，写入文件 { fwrite(wBuff, 1, wSize, fIn); wSize = 0; } if (0 == --FileSize)//若buff不满1024，但文件已读完，将其直接写入文件 { fwrite(wBuff, 1, wSize, fIn);//此处大小一定为buff中内容的大小，否则会出现随机值，第三个参数的类型为size_t,int无法写入 break; } pCur = pRoot;//每找到一个叶子节点，便将当前节点指向根节点，否则会崩溃 } if (pos == 0)//若pos为8，置0，重新计数 { pos = 8; break; } } } } //关闭文件 fclose(fOut); fclose(fIn); } private: //获取哈弗曼编码 void _GetHuffManCode(HuffmanTreeNode<FileInfo>* pRoot) { if (pRoot) { _GetHuffManCode(pRoot->_pLeft); _GetHuffManCode(pRoot->_pRight); if (pRoot->_pLeft == NULL&&pRoot->_pRight == NULL)//叶子节点 { HuffmanTreeNode<FileInfo>* pCur = pRoot; HuffmanTreeNode<FileInfo>* pParent = pCur->_pParent; std::string strCode; while (pParent) { if (pParent->_pLeft == pCur)//若当前节点是双亲结点的左孩子,编码为0 { strCode += '0'; } if (pParent->_pRight == pCur)//若当前节点是双亲结点的左孩子,编码为1 { strCode += '1'; } pParent = pParent->_pParent; pCur = pCur->_pParent; } std::reverse(strCode.begin(), strCode.end());//由于上边获取编码是从叶子节点开始的，所以拿到编码后需要逆置 _fileInfo[pRoot->_weight._ch]._strCode = strCode;//将编码保存到结构体内 } } } std::string GetFileName(const std::string strFilePath)//获取文件名 { //com.txt //E://code//com.txt size_t last = strFilePath.find_last_of("/");//找到租后一个‘/’ size_t first = strFilePath.find_first_of(".");//找到第一个‘.’ std::string fileName = strFilePath.substr(last + 1, first);//获取中间的子串，即文件名 return fileName; } std::string GetPostFix(const std::string strFilePath)//获取文件后缀 { //com.txt //E:\code\com.txt size_t first = strFilePath.find_last_of(".");//找到读后一个‘.’ size_t end = strFilePath.size() - 1;//字符串的结尾 std::string fileName = strFilePath.substr(first, end);//获得子串，即文件后缀 return fileName; } std::string ReadLine(FILE* fp)//读取文件的每一行内容 { std::string strLine; if (feof(fp))//检查文件是否为空 return strLine; unsigned char c = fgetc(fp); while (c != '\n') { strLine += c; if (feof(fp)) return strLine; c = fgetc(fp); } return strLine; } private: FileInfo _fileInfo[256]; };结果如图：
