原理:Huffman树的应用:Huffman编码,为出现频率较高的字符指定较短的码字,而为出现频率较低的字符指定较短的码字,可以实现二进制文件的压缩。
创新互联公司专注于企业营销型网站建设、网站重做改版、湖州网站定制设计、自适应品牌网站建设、H5技术、商城网站定制开发、集团公司官网建设、成都外贸网站制作、高端网站制作、响应式网页设计等建站业务,价格优惠性价比高,为湖州等各大城市提供网站开发制作服务。Heap.h
#pragma once #include//仿函数 template struct Lesser { bool operator()(const T& l, const T& r) { return l < r; } }; template struct Greater { bool operator()(const T& l, const T& r) { return l > r; } }; template > class Heap { public: Heap() {} Heap(const T* a, size_t size) { for (size_t i = 0; i < size; ++i) { _a.push_back(a[i]); } for (int i = (_a.size()-2)/2; i >= 0; --i) { _AdjustDown(i); } } void Push(const T& x) { _a.push_back(x); _AdjustUp(_a.size()-1); } void Pop() { assert(!_a.empty()); swap(_a[0], _a[_a.size()-1]); _a.pop_back(); _AdjustDown(0); } T& Top() { assert(!_a.empty()); return _a[0]; } bool Empty() { return _a.empty(); } size_t Size() { return _a.size(); } protected: void _AdjustUp(int child) { Compare cmp; int parent = (child-1)/2; while (child > 0)//parent>=0 ? { if (cmp(_a[child], _a[parent])) { swap(_a[child], _a[parent]); child = parent; parent = (child-1) / 2; } else { break; } } } void _AdjustDown(int parent) { Compare cmp; int child = parent*2 + 1; while (child < _a.size()) { if (child+1 < _a.size() && cmp(_a[child+1], _a[child])) { ++child; } if (cmp(_a[child], _a[parent])) { swap(_a[child], _a[parent]); parent = child; child = parent*2 + 1; } else { break; } } } protected: vector _a; };
HuffmanTree.h
#pragma once #include "Heap.h" templatestruct HuffmanTreeNode { HuffmanTreeNode * _left; HuffmanTreeNode * _right; HuffmanTreeNode * _parent; T _weight; HuffmanTreeNode(const T& weight) :_left(NULL) ,_right(NULL) ,_parent(NULL) ,_weight(weight) {} }; template class HuffmanTree { typedef HuffmanTreeNode Node; public: HuffmanTree() :_root(NULL) {} ~HuffmanTree() { _Destory(_root); } HuffmanTree(const T* a, size_t size, const T& invalid) { _root = _CreateTree(a, size, invalid); } Node* GetRoot() { return _root; } protected: Node* _CreateTree(const T* a,size_t size, const T& invalid) { assert(a); struct Compare { bool operator()(const Node* l, const Node* r) { return l->_weight < r->_weight; } }; Heap minHeap; for (size_t i = 0; i < size; ++i) { if (a[i] != invalid) { minHeap.Push(new Node(a[i])); } } while (minHeap.Size() > 1) { Node* left = minHeap.Top(); minHeap.Pop(); Node* right = minHeap.Top(); minHeap.Pop(); Node* parent = new Node(left->_weight + right->_weight); parent->_left = left; parent->_right = right; left->_parent = parent; right->_parent = parent; minHeap.Push(parent); } return minHeap.Top(); } void _Destory(Node* root) { if (root == NULL) return; _Destory(root->_left); _Destory(root->_right); } protected: Node* _root; }; void HuffmanTreeTest() { int a[] = {0,1,2,3,4,5,6,7,8,9}; HuffmanTree ht(a, 10, -1); }
FileCompress.h
#pragma once #include "HuffmanTree.h" #includestruct CharInfo { char _ch; int _count; string _code; CharInfo(unsigned char ch = 0) :_ch(ch) ,_count(0) {} CharInfo operator+(const CharInfo& x) { CharInfo tmp; tmp._count = _count + x._count; return tmp; } bool operator!=(const CharInfo& x) const { return _count != x._count; } bool operator<(const CharInfo& x) const { return _count < x._count; } }; template class FileCompress { public: FileCompress() { for (size_t i = 0; i < 256; ++i) { _infos[i] = i; } } void Compress(const char* filename) { assert(filename); FILE* fOutFile = fopen(filename, "rb"); assert(fOutFile); char ch = fgetc(fOutFile); int charCount = 0;//统计字符总数 while (!feof(fOutFile)) { ++charCount; _infos[(unsigned char)ch]._count++; ch = fgetc(fOutFile); } //创建Huffman树 CharInfo invalid(0); HuffmanTree t(_infos, 256, invalid); //由Huffman树生成Huffman编码 _GenerateHuffmanCode(t.GetRoot()); //压缩 string compressFilename = filename; compressFilename += ".compress"; FILE* fInCompress = fopen(compressFilename.c_str(), "wb"); assert(fInCompress); fseek(fOutFile, 0, SEEK_SET); ch = fgetc(fOutFile); char value = 0; int size = 0; while (!feof(fOutFile)) { string& code = _infos[(unsigned char)ch]._code; for (size_t i = 0; i < code.size(); ++i) { value <<= 1; if (code[i] == '1') { value |= 1; } ++size; if (size == 8) { fputc(value, fInCompress); size = 0; value = 0; } } ch = fgetc(fOutFile); } if (size > 0)//补位 { value <<= (8-size); fputc(value, fInCompress); } //写配置文件,方便解压缩时读取 string configFilename = filename; configFilename += ".config"; FILE* fInConfig = fopen(configFilename.c_str(), "wb"); assert(fInConfig); string line; char buffer[128]; //将字符总数写入配置文件第一行 line += itoa(charCount, buffer, 10); line += "\n"; fputs(line.c_str(), fInConfig); line.clear(); for (size_t i = 0; i < 256; ++i) { if (_infos[i]._count) { line += _infos[i]._ch; line += ','; line += itoa(_infos[i]._count, buffer, 10); line += '\n'; fputs(line.c_str(), fInConfig); } line.clear(); } fclose(fOutFile); fclose(fInCompress); fclose(fInConfig); } void UnCompress(const char* filename) { //读取配置文件 string configFilename = filename; configFilename += ".config"; FILE* fOutConfig = fopen(configFilename.c_str(), "rb"); assert(fOutConfig); string line; //读取字符总数 _ReadLine(fOutConfig, line); int charCount = atoi(line.c_str()); line.clear(); while (_ReadLine(fOutConfig, line)) { if (!line.empty()) { unsigned char ch = line[0]; _infos[ch]._count = atoi(line.substr(2).c_str()); line.clear(); } else { line.clear(); _ReadLine(fOutConfig, line); unsigned char ch = '\n'; _infos[ch]._count = atoi(line.substr(1).c_str()); line.clear(); } } //重建Huffman树 CharInfo invalid(0); HuffmanTree t(_infos, 256, invalid); //读.compress文件,写.uncompress文件 string compressFilename = filename; compressFilename += ".compress"; FILE* fOutCompress = fopen(compressFilename.c_str(), "rb"); assert(fOutCompress); string uncompressFilename = filename; uncompressFilename += ".uncompress"; FILE* fInUncompress = fopen(uncompressFilename.c_str(), "wb"); assert(fInUncompress); HuffmanTreeNode * root = t.GetRoot(); HuffmanTreeNode * cur = root; int pos = 7; char ch = fgetc(fOutCompress); while (1) { if (ch & (1< _right; else cur = cur->_left; if (cur->_left == NULL && cur->_right == NULL) { fputc(cur->_weight._ch, fInUncompress); cur = root; if (--charCount == 0)//字符已读取完,遇到补位的0不再读取 { break; } } --pos; if (pos == -1) { ch = fgetc(fOutCompress); pos = 7; } } fclose(fOutCompress); fclose(fInUncompress); } protected: void _GenerateHuffmanCode(HuffmanTreeNode * root) { if (root == NULL) return; _GenerateHuffmanCode(root->_left); _GenerateHuffmanCode(root->_right); if (root->_left == NULL && root->_right == NULL) { HuffmanTreeNode * cur = root; HuffmanTreeNode * parent = root->_parent; string& code = _infos[(unsigned char)cur->_weight._ch]._code; while (parent) { if (parent->_left == cur) code += '0'; if (parent->_right == cur) code += '1'; cur = parent; parent = cur->_parent; } reverse(code.begin(), code.end()); } } bool _ReadLine(FILE* filename, string& line) { char ch = fgetc(filename); if (ch == EOF) return false; while (ch != EOF && ch != '\n') { line += ch; ch = fgetc(filename); } return true; } protected: CharInfo _infos[256]; }; void CompressTest() { //压缩 FileCompress compress; int CompressBegin = GetTickCount(); compress.Compress("Input.BIG"); int CompressEnd = GetTickCount(); cout<<"压缩用时:"< uncompress; int UncompressBegin = GetTickCount(); uncompress.UnCompress("Input.BIG"); int UncompressEnd = GetTickCount(); cout<<"解压缩用时:"< Test.cpp
#includeusing namespace std; #include #include "FileCompress.h" int main() { CompressTest(); UncompressTest(); return 0; } 下面是对一个大小为8.04MB文件的测试:
结果成功压缩、解压缩:
压缩后的文件大小:
压缩后的文件:
配置文件:
用Beyond Compare文本比较工具检查原文件与解压后的文件:
无差异
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
分享文章:C++实现文件压缩及解压缩-创新互联
URL标题:http://njwzjz.com/article/cceoch.html