Huffman编码压缩和解压文档，C++实现-白红宇

Huffman编码压缩和解压文档，C++实现

阅读量：6227 次

发布时间：2019-06-21

本文共 4677 字，大约阅读时间需要 15 分钟。

注：本演示代码采用自上而下得到huffman编码（二叉树）

关于huffman树及相关算法这里就略过，这里探讨的是如何进行编码和解压缩。先说一下大致步骤

1.首先，读取文档（txt格式），将其存入string类型的变量pretext里

2.进行词频统计

3.创建Huffman树，并以此得到各字符的二进制编码

4.对pretext进行遍历，通过上面得到编码表，将其转化为二进制字符串code，这个二进制串可能十分长

5.将二进制串进行八位一编码，得到压缩后的compresstext文本

至此，压缩完成

还原步骤如下：

1.将compress化为二进制串newcode

2.将二进制串newcode对应如上得到的huffman树，根据二进制串依次遍历该树，得到对应原始字符，这些字符连接起来，即得到原文本newtext（也可对二进制串进行打表，注：打表也需要逐个遍历，查看对应二进制字符是否在表内，经博主测试，大量数据下，根据huffman树解码快一些）

需要注意的问题：

1.将二进制八位一编码，可能最后剩余并非是整八位，因此需要对最后几位进行补位，使其成为整八位，并记录补位长度（补了几位，记录有效位也可），这里代码为了简便，将补位长度直接放在compresstext的首部

2.一些数字和二进制之间的转换可能需要自己写函数实现

3.创建Huffman树时，采用stl的优先队列注意排序写法

4.中文为16位宽，处理时看做两个字符即可

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;#define MaxBitL 256;struct HuffmanTreeNode{ unsigned char leafchar; bool bit; int weight; HuffmanTreeNode *left,*right; HuffmanTreeNode(unsigned char c,unsigned int w,HuffmanTreeNode *l,HuffmanTreeNode *r):leafchar(c),bit(0),weight(w),left(l),right(r){}};struct cmp{ bool operator ()(HuffmanTreeNode* &a,HuffmanTreeNode* &b) const { return a->weight>b->weight; }};unordered_map
                
                  freqTable;//字符频率统计表unordered_map
                 
                   dictTable;//字符到二进制序列的映射map
                  
                    RedictTable;//二进制序列到字符的映射unordered_map
                   
                     codeToCharTable;//二进制到字符（压缩）unordered_map
                    
                      charToCodeTable;//二进制到字符（解压）priority_queue
                     
                      
                       ,cmp> pq;//优先队列void ComputeFreqTable(const string &text){ for(unsigned char c:text) freqTable[c]++; cout<<"ComputeFreqTable Finished"<
                       
                        weight>second->weight) swap(first,second); HuffmanTreeNode *s=new HuffmanTreeNode('\0',first->weight+second->weight,first,second); s->right->bit=1; pq.push(s); } cout<<"CreatHuffmanTree Finished"<
                        
                         bit+'0'); if(!r->left&&!r->right) { dictTable[r->leafchar]=bin; RedictTable[bin]=r->leafchar; } dictHelp(r->left,bin); dictHelp(r->right,bin); bin.pop_back(); }}void ComputeDictTable(HuffmanTreeNode *r){ string bin; dictHelp(r,bin); cout<<"ComputeDictTable Finished"<
                         
                          =8) { temp=codetemp.substr(0,8); codetemp=codetemp.substr(8,codetemp.size()-8); } else { len=8-codetemp.size(); string tail(len,'0'); codetemp+=tail; compressText+=codeToCharTable[codetemp]; break; } compressText+=codeToCharTable[temp]; } char head='0'+len; compressText=head+compressText; cout<<"compressCode Finished"<
                          
                           second; bin.clear(); } } cout<<"ConvertCodeToText Finished"<
                           
                            left&&!r->right) { return r->leafchar;} int bit=str[++i]-'0'; if(bit==1) r=r->right; else r=r->left; } return '\0';}string DeCodeToText(string &decompressText,HuffmanTreeNode *r){ string NewText=""; unsigned int i=0; while(i

运行结果：

1.对随机字符：随机生成10000个字符，进行huffman编码，压缩率仅仅为95%左右

ComputeFreqTable Finishedusetime : 488 msCreatHuffmanTree Finishedusetime : 493 msComputeDictTable Finishedusetime : 497 msCreatcodeToCharTable Finishedusetime : 504 msencode Finishedusetime : 508 mstry! : compressCode Finishedusetime : 573 msdecompressCode Finishedusetime : 577 msusetime : 581 msSame CodeSame TextPreText Length : 10000   ComText Length : 9481Rate : 94.81%rt : 0.591 s

2.对英语文章：文章选自china daily，题材来源不同，共计12199字，多次测试，压缩率稳定在70%左右

WriteTextByFile Finishedusetime : 1 msComputeFreqTable Finishedusetime : 3 msCreatHuffmanTree Finishedusetime : 3 msComputeDictTable Finishedusetime : 3 msCreatcodeToCharTable Finishedusetime : 4 msencode Finishedusetime : 7 mstry! : compressCode Finishedusetime : 61 msdecompressCode Finishedusetime : 64 msusetime : 66 msSame CodeSame TextPreText Length : 12199   ComText Length : 8489Rate : 69.5877%rt : 0.068 s

3.中文字符：文章选自《福尔摩斯探案集》东方探案部分，文字总计437700字，压缩率89%左右，花费时间较长，为342.452 s

WriteTextByFile Finishedusetime : 4 msComputeFreqTable Finishedusetime : 59 msCreatHuffmanTree Finishedusetime : 60 msComputeDictTable Finishedusetime : 60 msCreatcodeToCharTable Finishedusetime : 61 msencode Finishedusetime : 168 mstry! : compressCode Finishedusetime : 342272 msdecompressCode Finishedusetime : 342356 msusetime : 342420 msSame CodeSame TextPreText Length : 437700   ComText Length : 389238Rate : 88.928%rt : 342.452 s

4.时间对比：将英文累积到432673，花费时间为193.675s，远远小于编码中文时间，压缩率稳定在70%左右

WriteTextByFile Finishedusetime : 7 msComputeFreqTable Finishedusetime : 80 msCreatHuffmanTree Finishedusetime : 81 msComputeDictTable Finishedusetime : 81 msCreatcodeToCharTable Finishedusetime : 82 msencode Finishedusetime : 183 mstry! : compressCode Finishedusetime : 193529 msdecompressCode Finishedusetime : 193597 msusetime : 193652 msSame CodeSame TextPreText Length : 432673   ComText Length : 300885Rate : 69.541%rt : 193.675 s

总结：Huffman编码对英文支持较好，时间主要花费在将二进制字符串转化为字符这一过程上，但是在实际计算机中，二进制序列是自动化为字符的，这里仅仅是为了模拟这一过程，因此，huffman编码在通信中还是有较大的应用价值

转载于:https://www.cnblogs.com/xLester/p/7570291.html

你可能感兴趣的文章