服务器之家

服务器之家 > 正文

C++实现Huffman的编解码

时间:2021-09-03 14:45     来源/作者:漆黑烈焰使

Huffman编码主要是通过统计各元素出现的频率,进而生成编码最终达到压缩的目的。

这里是Huffman树中节点的结构。

?
1
2
3
4
5
6
7
8
typedef struct Tree
{
 int freq;//频率
 int key;//键值
 struct Tree *left, *right;
 Tree(int fr=0, int k=0,Tree *l=nullptr, Tree *r=nullptr):
  freq(fr),key(k),left(l),right(r){};
}Tree,*pTree;

首先用一个名为freq的hashtable来记录各个元素的频率:

?
1
2
3
4
5
6
7
8
9
10
void read(){
 int a;
 
 std::ios::sync_with_stdio(false);
 while(cin>>a){
  if(freq.find(a)==freq.end()) {freq[a]=1;}
  else {freq[a]++;}
 }
 
}

Huffman树的构建过程如下代码所示:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void huffman()
{
 int i;
 string c;
 int fr;
 auto it = freq.begin();
 while(it!=freq.end()){
  Tree *pt= new Tree;
  pt->key = it->first;
  pt->freq = it->second;
  it++;
  th.Insert(pt);//此处的th为一种优先队列
 }
 
 while(true)//构建哈夫曼树
 {
 
  Tree *proot = new Tree;
  pTree pl,pr;
  pl = th.findMin();
  th.Delete(0);
  if(th.isEmpty()){
    th.Insert(pl);
    break;
  }
 
  pr = th.findMin();
  th.Delete(0);
  //合并节点
  proot->freq = pl->freq + pr->freq;
  std::ios::sync_with_stdio(false);
  proot->left = pl;
  proot->right = pr;
  th.Insert(proot);
  //合并后再插入
 }
 
 string s;
 
 print_Code(th.findMin(), s);
 
 del(th.findMin());
}

其中print_Code和del函数如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void print_Code(Tree *proot, string st)//从根节点开始打印,左0右1
{
 if(proot == NULL)
  return ;
 if(proot->left)
 {
  st +='0';
 }
 print_Code(proot->left, st);
 std::ios::sync_with_stdio(false);
 if(!proot->left && !proot->right)
 {
  cout<<proot->key<<" ";
  for(size_t i=0; i<st.length(); ++i){
   cout<<st[i];ml+=st[i];
  }
  cout<<endl;encoded[proot->key]=ml;ml="";
 }
 st.pop_back();
 if(proot->right)
  st+='1';
 print_Code(proot->right, st);
}
 
 
void del(Tree *proot)
{
 if(proot == nullptr)
  return ;
 del(proot->left);
 del(proot->right);
 delete proot;
}

至此就完成了Huffman的编码。

当然,由于huffman的编码都是0或1,因此需要进行位的表示才能完成压缩。注意,位需要以8个为一组进行写入:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
while(in>>a){
   int x=atoi(a.c_str());
   auto m=encoded.find(x);
   //encoded是另外一个哈希表用于记录元素及它的编码
   if(m==encoded.end()) continue;
   else {
     string t=m->second;
     ss+=t;
   }
   
 }
 unsigned char buf = 0;
 int count = 0;
 int i = 0;
 while(ss[i] != '\0')//位写入,8个为一组
 {
  buf = buf | ((ss[i++]-'0') << (7 - count));
  count++;
  if (count == 8)
  {
   count = 0;
   fout << buf;
   buf = 0;
  }
 }
 if(count != 0)
  fout << buf;

至此就完成了Huffman的编码以及压缩,效果十分可观:
当对69.6M的txt文件(其中含有大约10000000个数据)进行压缩时,产生的encoded.bin文件仅为24.6MB:Ubuntu测试环境:

C++实现Huffman的编解码

下面进行Huffman解码的解说:

Huffman解码首先是根据编码表进行huffman树的重建:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void decode(){
 auto it=decoded.begin();
 Tree *p=proot;
 while(it!=decoded.end()){
   string s=it->first;int t=it->second;int i=0;
   while(i<s.length()){
    if(s[i]=='0') {
     if(proot->left==nullptr) proot->left=new Tree(5);
     proot=proot->left;
     }
    else{
     if(proot->right==nullptr) proot->right=new Tree(5);
     proot=proot->right;
     }
    i++;
   }
   proot->data=t;
   proot=p;
   it++;
 }
 
}

然后读取bin文件的一系列位:

?
1
2
3
4
5
6
7
while (f.get(c)){
   stringstream a;
   for (int i = 7; i > 0; i--)
    a<<((c >> i) & 1);
   a<<(c&1);
   m+=a.str();//将位转为字符串
 }

然后用Huffman树根据左0右1进行查找并输出:

?
1
2
3
4
5
6
7
8
9
10
int i=0;Tree *p=proot;
 
 while(i<m.length()){
   if(m[i]=='0'&&proot->left!=nullptr)
    {proot=proot->left;i++;}
   else if(m[i]=='1'&&proot->right!=nullptr)
    {proot=proot->right;i++;}
   else
    {cout<<proot->data<<endl;proot=p;}
 }

至此就完成了Huffman树的解码:

C++实现Huffman的编解码

总的来说,Huffman对于大数据的压缩效果是很好的,运行时间也很快,大概需要20s就可以完成对1000000个数据的编码压缩。

难点在于位的写入与读取,花了相当多的精力进行操作。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。

原文链接:https://blog.csdn.net/u013065237/article/details/70669860

标签:

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
返回顶部