哈夫曼编码 哈夫曼树

简介: 1.定义   哈夫曼编码主要用于数据压缩。   哈夫曼编码是一种可变长编码。该编码将出现频率高的字符,使用短编码;将出现频率低的字符,使用长编码。   变长编码的主要问题是,必须实现非前缀编码,即在一个字符集中,任何一个字符的编码都不是另一个字符编码的前缀。

1.定义

  哈夫曼编码主要用于数据压缩。

  哈夫曼编码是一种可变长编码。该编码将出现频率高的字符,使用短编码;将出现频率低的字符,使用长编码。

  变长编码的主要问题是,必须实现非前缀编码,即在一个字符集中,任何一个字符的编码都不是另一个字符编码的前缀。如:0、10就是非前缀编码,而0、01不是非前缀编码。

2.哈夫曼树的构造

  按照字符出现的频率,总是选择当前具有较小频率的两个节点,组合为一个新的节点,循环此过程知道只剩下一个节点为止。

  对于5个字符A、B、C、D、E,频率分别用1、5、7、9、6表示,则构造树的过程如下:

  

  上面过程对应的哈夫曼树为:

  

假设规定左边为0,右边为1,则变长编码为:

  A 1:010

  B 5:011

  C 7:10

  D 9:11

  E 6: 00

3.哈夫曼构造代码

 1 #include <iostream>
 2 #include <string.h>
 3 using namespace std;
 4 struct Node{
 5     char c;
 6     int value;
 7     int par;
 8     char tag;    //tag='0',表示左边;tag='1',表示右边
 9     bool isUsed;    //判断这个点是否已经用过
10     Node(){
11         par=-1;
12         isUsed=false;
13     }
14 };
15 
16 int input(Node*,int);   //输入节点信息
17 int buildedTree(Node*,int); //建哈夫曼树
18 int getMin(Node*,int);  //寻找未使用的,具有最小频率值的节点
19 int outCoding(Node*,int);   //输出哈夫曼编码
20 
21 int main ()
22 {
23     int n;
24     cin>>n;
25     Node *nodes=new Node[2*n-1];
26     input(nodes,n);
27     buildedTree(nodes,n);
28     outCoding(nodes,n);
29     delete(nodes);
30     return 0;
31 }
32 
33 int input(Node* nodes,int n){
34     for(int i=0;i<n;i++){
35         cin>>(nodes+i)->c;
36         cin>>(nodes+i)->value;
37     }
38     return 0;
39 }
40 
41 int buildedTree(Node* nodes,int n){
42     int last=2*n-1;
43     int t1,t2;
44     for(int i=n;i<last;i++){
45         t1=getMin(nodes,i);
46         t2=getMin(nodes,i);
47         (nodes+t1)->par=i; (nodes+t1)->tag='0';
48         (nodes+t2)->par=i; (nodes+t2)->tag='1';
49         (nodes+i)->value=(nodes+t1)->value+(nodes+t2)->value;
50     }
51     return 0;
52 }
53 
54 int getMin(Node* nodes,int n){
55     int minValue=10000000;
56     int pos=0;
57     for(int i=0;i<n;i++)
58     {
59         if((nodes+i)->isUsed == false && (nodes+i)->value<minValue){
60             minValue=(nodes+i)->value;
61             pos=i;
62         }
63     }
64     (nodes+pos)->isUsed=true;
65     return pos;
66 }
67 
68 int outCoding(Node* nodes,int n){
69     char a[100];
70     int pos,k,j;
71     char tmp;
72     for(int i=0;i<n;i++){
73         k=0;
74         pos=i;
75         memset(a,'\0',sizeof(a));
76         while((nodes+pos)->par!=-1){
77             a[k++]=(nodes+pos)->tag;
78             pos=(nodes+pos)->par;
79         }
80         strrev(a);    //翻转字符串
81         cout<<(nodes+i)->c<<" "<<(nodes+i)->value<<":"<<a<<endl;
82     }
83     return 0;
84 }
View Code

 执行示例:

  

相关文章
|
11月前
|
移动开发 JavaScript 小程序
|
11月前
|
前端开发 JavaScript
JS-instanceof 的实现原理
`instanceof` 运算符在前端 JavaScript 中用于检测对象的原型链是否包含指定构造函数的 `prototype` 属性。它通过遍历对象的原型链来实现。每个对象都有一个内部链接 `[[Prototype]]` 指向其原型对象,当访问属性或方法时,JavaScript 引擎会沿着原型链查找。`instanceof` 的具体实现是通过比较对象的原型链中的原型与构造函数的 `prototype` 属性,直到找到匹配的原型或到达原型链的顶端。示例代码展示了如何使用 `instanceof` 检查对象的继承关系。此外,`instanceof` 可用于验证继承关系和类型检查,支持多态性。
|
Linux 程序员 网络安全
Linux安装minikube指南
在linux安装minikube时遇到两个问题,在此记录整个安装过程,希望能够给遇见同样问题的读者一些参考
1737 0
Linux安装minikube指南
|
存储 缓存 安全
一起学点ARM的微架构?
一起学点ARM的微架构?
546 0
|
存储 弹性计算 运维
阿里云「无影云桌面」无需新用户4核8G仅需199元/年
阿里云「无影云桌面」无需新用户4核8G仅需199元/年
1034 0
|
Web App开发 缓存 安全
|
存储 SQL 弹性计算
十分钟教你了解阿里云数据库RDS
阿里云关系型数据库(Relational Database Service,简称RDS)是一种稳定可靠、可弹性伸缩的在线数据库服务。基于阿里云分布式文件系统和SSD盘高性能存储,RDS支持MySQL、SQL Server、PostgreSQL、PPAS(Postgre Plus Advanced Server,高度兼容Oracle数据库)和MariaDB TX引擎,并且提供了容灾、备份、恢复、监控、迁移等方面的全套解决方案,彻底解决数据库运维的烦恼。
1630 0
十分钟教你了解阿里云数据库RDS
|
存储 Kubernetes 应用服务中间件
阿里云Kubernetes CSI实践—CPFS存储卷使用
1. 前言 CPFS(Cloud Paralleled File System)是一种并行文件系统。CPFS 的数据存储在集群中的多个数据节点,并可由多个客户端同时访问,从而能够为大型高性能计算机集群提供高 IOPS、高吞吐、低时延的数据存储服务。
4805 0
阿里云Kubernetes CSI实践—CPFS存储卷使用
|
弹性计算 网络安全 存储
阿里云弹性公网IP和ECS独立IP区别对比和优势详解
阿里云弹性公网IP是可以独立购买和持有的公网IP地址资源,弹性公网IP和ECS独立公网IP有什么区别?云吞铺子分享: 什么是弹性公网IP? 弹性公网IP(EIP):即Elastic IP Address,简称EIP,EIP是可以独立购买和持有的公网IP地址资源,购买EIP后,可以将EIP绑定到专有网络类型的ECS实例、专有网络类型的私网SLB实例和NAT网关上。
8631 0
|
Web App开发
利用阿里云搭建WordPress网站 – 数据库缓存和管理
WordPress是一种非常流行的博客网站平台,也可以当作一个内容管理系统(CMS)来使用, 是世界上使用最广泛的博客系统之一。WordPress有非常多优秀的插件,使得这个开源产品变得非常容易扩展,满足不同的需求。
5119 0