哈夫曼编码原理详解及应用实例,哈夫曼编码算法流程图全文编程语言及工具

摘要:作为一种常用的编码方式即哈夫曼编码,很多人在它的原理即应用方面都弄不不清楚,本文主要以哈夫曼编码原理与应用实例及算法流程图俩进一步说明。

哈夫曼编码(HuffmanCoding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。

设某信源产生有五种符号u1、u2、u3、u4和u5,对应概率P1=0.4,P2=0.1,P3=P4=0.2,P5=0.1。首先,将符号按照概率由大到小排队,如图所示。编码时,从最小概率的两个符号开始,可选其中一个支路为0,另一支路为1。这里,我们选上支路为0,下支路为1。再将已编码的两支路的概率合并,并重新排队。多次重复使用上述方法直至合并概率归一时为止。从图(a)和(b)可以看出,两者虽平均码长相等,但同一符号可以有不同的码长,即编码方法并不唯一,其原因是两支路概率合并后重新排队时,可能出现几个支路概率相等,造成排队方法不唯一。一般,若将新合并后的支路排到等概率的最上支路,将有利于缩短码长方差,且编出的码更接近于等长码。这里图(a)的编码比(b)好。

赫夫曼码的码字(各符号的代码)是异前置码字,即任一码字不会是另一码字的前面部分,这使各码字可以连在一起传送,中间不需另加隔离符号,只要传送时不出错,收端仍可分离各个码字,不致混淆。

长游程的主码和基码均用赫夫曼规则进行编码,这称为修正赫夫曼码,其结果有表可查。该方法已广泛应用于文件传真机中。

哈夫曼编码的算法是查找最优路径的一种算法,首先在所有未分配parent域的节点中找出最小的两个节点,将他们的全值相加,组成新的节点,并且将它标记为原来两个最小节点的parent。这样调用递归,最后就能够成一颗完整的哈夫曼树。然后对每个节点进行遍历编码,得到最终的哈夫曼编码库。流程图如下:

哈夫曼算法的过程为:统计原始数据中各字符出现的频率;所有字符按频率降序排列;建立哈夫曼树:将哈夫曼树存入结果数据;重新编码原始数据到结果数据。哈夫曼算法实现流程如图3所示。

哈夫曼算法的实质是针对统计结果对字符本身重新编码,而不是对重复字符或重复子串编码。实用中.符号的出现频率不能预知,需要统计和编码两次处理,所以速度较慢,无法实用。而自适应(或动态)哈夫曼算法取消了统计,可在压缩数据时动态调整哈夫曼树,这样可提高速度。因此,哈夫曼编码效率高,运算速度快,实现方式灵活。

采用哈夫曼编码时需注意的问题:

(1)哈夫曼码无错误保护功能,译码时,码串若无错就能正确译码;若码串有错应考虑增加编码,提高可靠性。

(2)哈夫曼码是可变长度码,因此很难随意查找或调用压缩文件中间的内容,然后再译码,这就需要在存储代码之前加以考虑。

(3)哈夫曼树的实现和更新方法对设计非常关键。

哈夫曼编码,主要用途是实现数据压缩。

设给出一段报文:CASTCASTSATATATASA。字符集合是{C,A,S,T},各个字符出现的频度(次数)是W={2,7,4,5}。若给每个字符以等长编码A:00T:10C:01S:11,则总编码长度为(2+7+4+5)*2=36。

若按各个字符出现的概率不同而给予不等长编码,可望减少总编码长度。各字符出现概率为{2/18,7/18,4/18,5/18},化整为{2,7,4,5}。以它们为各叶结点上的权值,建立霍夫曼树。左分支赋0,右分支赋1,得霍夫曼编码(变长编码)。A:0T:10C:110S:111。它的总编码长度:7*1+5*2+(2+4)*3=35。比等长编码的情形要短。霍夫曼编码是一种无前缀编码。解码时不会混淆。带权路径长度达到最小的二叉树即为霍夫曼树。在霍夫曼树中,权值大的结点离根最近。

霍夫曼算法

2.重复以下步骤,直到F中仅剩下一棵树为止:

①在F中选取两棵根结点的权值最小的扩充二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。

②在F中删去这两棵二叉树。

③把新的二叉树加入F。

#include《stdio.h》

#include《stdlib.h》

#include《string.h》

#defineMAX32767

typedefchar*HuffmanCode;

typedefstruct

{

intWeight;//字母的权

intParent,Leftchild,Rightchild;

}HuffmanTree;

voidSelect(HuffmanTree*HT,intn,int*s1,int*s2)

intmin1=MAX;

intmin2=MAX;

intpos1,pos2;

inti;

for(i=0;i《n;i++)

if(HT[i].Parent==-1)//选择还没有父亲的节点

if(HT[i].Weight《=min1)

pos2=pos1;min2=min1;

pos1=i;min1=HT[i].Weight;

}

elseif(HT[i].Weight《=min2)

pos2=i;min2=HT[i].Weight;

*s1=pos1;*s2=pos2;

intm=2*n-1;//总的节点数

ints1,s2;

for(i=0;i《m;i++)

if(i《n)

HT[i].Weight=w[i];

else

HT[i].Weight=-1;

HT[i].Parent=-1;

HT[i].Leftchild=-1;

HT[i].Rightchild=-1;

for(i=n;i《m;i++)

Select(HT,i,&s1,&s2);//这个函数是从0到n-1中选两个权最小的节点

HT[i].Weight=HT[s1].Weight+HT[s2].Weight;

HT[i].Leftchild=s1;

HT[i].Rightchild=s2;

HT[s1].Parent=i;

HT[s2].Parent=i;

voidPrint(HuffmanTree*HT,intm)

if(m!=-1)

printf(“%d”,HT[m].Weight);

Print(HT,HT[m].Leftchild);

Print(HT,HT[m].Rightchild);

char*cd;

intstart;

intCurrent,parent;

cd=(char*)malloc(sizeof(char)*n);//用来临时存放一个字母的编码结果

cd[n-1]=‘\0’;

start=n-1;

for(Current=i,parent=HT[Current].Parent;parent!=-1;Current=parent,parent=HT[parent].Parent)

if(Current==HT[parent].Leftchild)//判断该节点是父节点的左孩子还是右孩子

cd[--start]=‘0’;

cd[--start]=‘1’;

hc[i]=(char*)malloc(sizeof(char)*(n-start));

strcpy(hc[i],&cd[start]);

free(cd);

printf(“letters:%c,weight:%d,编码为%s\n”,letters[i],HT[i].Weight,hc[i]);

printf(“\n”);

voidEncode(HuffmanCode*hc,char*letters,char*test,char*code)

intlen=0;

inti,j;

for(i=0;test[i]!=‘\0’;i++)

for(j=0;letters[j]!=test[i];j++){}

strcpy(code+len,hc[j]);

len=len+strlen(hc[j]);

printf(“TheTest:%s\nEncodetobe:”,test);

printf(“%s”,code);

voidDecode(HuffmanTree*HT,intm,char*code,char*letters)

printf(“TheCode:%s\nDecodetobe:”,code);

for(i=m-1;HT[i].Leftchild!=-1&&HT[i].Rightchild!=-1;position++)

if(code[position]==‘0’)

i=HT[i].Leftchild;

i=HT[i].Rightchild;

printf(“%c”,letters[i]);

intmain()

intn=27;

intm=2*n-1;

charletters[28]={‘a’,‘b’,‘c’,‘d’,‘e’,‘f’,‘g’,‘h’,‘i’,‘j’,‘k’,‘l’,‘m’,

‘n’,‘o’,‘p’,‘q’,‘r’,‘s’,‘t’,‘u’,‘v’,‘w’,‘x’,‘y’,‘z’,‘’};

intw[28]={64,13,22,32,103,21,15,47,57,1,5,32,20,

57,63,15,1,48,51,80,23,8,18,1,16,1,168};

charcode[200];

chartest[50]={“thisisaboutbuildmylife”};

HuffmanTree*HT;

HuffmanCode*hc;

HT=(HuffmanTree*)malloc(m*sizeof(HuffmanTree));

hc=(HuffmanCode*)malloc(n*sizeof(char*));

CreateTree(HT,n,w);

Print(HT,m-1);

Huffmancoding(HT,n,hc,letters);

Encode(hc,letters,test,code);

Decode(HT,m,code,letters);

return0;

推荐阅读:

下载发烧友APP

哈夫曼编码可以使得编码的总长最短,从而相同的位长可以传送更多的信息。下面来看看c语言是如何实现哈夫曼...

摘要:哈夫曼编码作为一种编码方式,已经在生活中得到了实际的运用,下面我们以java实现的哈夫曼编码...

THE END
1.递归,搜索,和回溯算法腾讯云开发者社区我们先来简单的介绍一下三个用到递归的算法例子,来看看他们有什么共同点 本质上就是:在解决子问题的时候,衍生出了相同的子问题,在解决相同子问题是,又衍生出了更小的相同子问题。 三、如何看待递归这个过程 递归一共有三层。 第一层:.细节的去看待,递归的细节展开图 第二层:利用二叉树中经典递归题,非常明显https://cloud.tencent.com/developer/article/2477481
2.怎么绘制递归算法流程图?教你简单的制作方法递归流程图是一种描述递归算法执行过程的图形化工具,它可以帮助理解递归算法的实现原理,展示递归函数调用的过程和递归函数在不同层次上的执行情况。那么要怎么绘制递归算法流程图呢?接下来就让我们一起来看看。https://www.liuchengtu.com/tutorial/diguiliuchengtu.html
3.递归算法流程图递归递归算法 流程图_递归 本文详细介绍了递归的概念,包括直接递归和间接递归,并强调了递归使用时需要注意的结束条件和栈内存溢出问题。通过递归累和的例子,展示了如何用递归解决数学问题。此外,还探讨了如何利用递归进行文件搜索,特别是在无法预知目录层级的情况下,递归遍历以找到特定文件。https://blog.csdn.net/weixin_39629780/article/details/111112798
4.条件语句算法流程图及程序课件.pptx条件语句算法流程图及程序课件条件语句概述条件语句算法流程图条件语句的程序实现条件语句的应用场景与案例分析条件语句的优化与调试技巧条件语句与其他控制结构的结合使用条件语句概述01条件语句是一种程序控制结构,用于根据特定条件执行不同的操作或流程。条件语句定义根据条件表达式的真假,条件语句可分为if-else语句和switchhttps://m.renrendoc.com/paper/314217433.html
5.算法架构图思维导图模板图 有向图、无向图、带权图 算法 指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,代表这用系统的方法描述解决问题的策略机制 一句话:一种解决特定问题的思路和方法 常见 排序 冒泡、快速、插入、归并、计数、选择、堆排序、桶排序 常用实践 LRU、LFU、Hash、一致性Hash 算法思维 递归、回溯https://www.processon.com/view/6146a1cf1e085315dc4c5be6
6.C语言函数的系统化精讲(三)一、递归举例 ● 二、递归举例 ○ 2.1求n的阶乘 ○ 2.2 顺序打印?个整数的每?位 ● 三、递归与迭代 ○ 3.1递归的思考 ○ 3.2求第n个斐波那契数 ● 总结 一、递归举例 .通过上回 (【C语言】函数的系统化精讲(二))我们了解到递归的限制条件,递归在书写的时候,有2个必要条件:递归在书写https://open.alipay.com/portal/forum/post/145201074
7.一文弄懂递归第二步,我们要明白每一层要给上一层提供什么信息。继续看阶乘的算法,我们可以发现,每一层都会返回一个n?f(n?1)。其中这个就是我们留下来的信息,而这个信息就会被逐步返回,直到返回第一层。这也叫做recursive case。也就是没有到终止条件时,递归会做什么。 https://zhuanlan.zhihu.com/p/165052663
8.全国教师资格考试信息技术练习题(二)通过对全国统考教师资格《信息技术》初中、高中试卷分析得出:算法与程序设计部分主要的考点是算法流程图和结构化程序设计的三种基本结构。 二、算法与程序设计模块习题及解析 1.某计算公式的流程图如图1所示,输出结果s的值为( )。 A.14 B.30 C.55 D.91 http://www.zgjsks.com/html/2020/lianxiti_1218/507469.html
9.数据结构C语言实现二叉树的基本操作——二叉树的层次遍历求在上一篇内容中,咱们详细介绍了二叉树的三种遍历算法以及算法的递归与非递归之间的转换。在今天的内容中我们将会继续介绍二叉树的一些基本操作如二叉树的层次遍历、求二叉树的深度、求二叉树的结点总数、求二叉树第K层的结点数、求二叉树的叶结点数……以及如何通过C语言来实现这些基本操作。 https://blog.51cto.com/u_16231477/10890209
10.使用流程图表示算法(计算机基础)流程图是表示算法也是表示业务逻辑的一种方式使用图形表示算法的方式是一种极好的方法。 下图是流程图预定义的符号: 下面是流程图示例(既表示业务逻辑也表示程序逻辑): 绘制流程图直接使用word文档就行流程图绘制方式: 1.点击插入-->形状-->流程图,图片示例如下: 通过这些形状以及我们提供的流程图示例,就可以进行https://www.pianshen.com/article/81431148068/
11.循环与递归算法实验(8页)M Main函数输入字符输入字符调用递归函数进行判断调用递归函数进行判断是则返回1,否返回0 是则返回1,否返回0 转化成自然语言后输出转化成自然语言后输出 图2.1 程序运行流程图第三题计算1到n的数值总和,用循环算法需要设计一层循环,将语句sum+=i;计算n次累加得出结果。但是循环算法相比在时间效率上不如递归算法。https://max.book118.com/html/2019/1020/6020102215002114.shtm
12.C#实现银行家算法C#教程3.银行家算法 1)设计思想 在系统中,进程发起一项资源分配请求,由系统检查是否可以满足该分配请求,若可以,应暂时满足该请求,并查看此时系统是否仍是安全状态。 2)程序流程图 可以分为三个功能模块,第一个模块检查需求是否可以被满足,第二个模块检查系统是否安全,第三个模块是主程序,通过调用前两个模块实现资源分配https://www.jb51.net/article/211733.htm
13.数据结构原理系统生命周期算法规范笔记Ⅱ. 算法规范 | Algorithm Specification 0x00 介绍 定义:算法是一组有限的指令,如果遵循这些指令,可以完成特定的任务。 所有算法都必须满足以下标准: (1)输入 (2)输出 (3)确定性 (4)有限性 (5)有效性 算法/ 程序(过程) 如何设计算法? 自然语言 → 流程图 → 程序语言 https://developer.aliyun.com/article/1369050
14.软考程序员知识点之算法设计概述程序员2.常用算法 (1)排序算法、查找算法、数值计算算法、字符串处理算法、递归算法、最小生成树、拓扑排序和单源点最短路径求解算法、图的相关算法。 (2)算法与数据结构的关系、算法效率、算法设计、算法描述(流程图、伪代码、决策表)、算法的复杂性。 算法设计概述 https://www.educity.cn/rk/1774548.html
15.北航软件学院招收2024年硕士研究生自命题考试大纲(991包括但不限于软件设计的概念和应用,主要内容有:软件设计的基本原则,概要设计(架构设计)和详细设计(构件设计)的基本过程;软件体系结构(架构)的基本概念和过程、典型架构模式(风格)、性能、安全、可靠性等关键质量属性设计;面向数据流设计的基本概念,流程图、判定表、判定树和过程设计语言等基本设计方法;数据库设计的基https://soft.buaa.edu.cn/news_nry.jsp?urltype=news.NewsContentUrl&wbtreeid=1325&wbnewsid=10683
16.全国江西科学技术版小学信息技术五年级下册第三单元第14课《跨学科主(三)递归算法在汉诺塔问题中的应用 1. 递归算法概念:简要介绍递归算法的基本概念,强调其在解决复杂问题中的优势。 2. 递归算法在汉诺塔中的应用分析:详细分析递归算法在汉诺塔问题中的应用过程,包括如何分解问题、如何递归调用自身等。 3. 递归算法的实现:引导学生使用伪代码或流程图等方式表示递归算法的实现过程,帮助https://www.zxxk.com/soft/45346342.html
17.算法与程序·程序框图6篇(全文)例 下列是为计算22+42+62+…+1002而绘制的算法流程图, 根据流程图回答: (1) 其中正确的流程图有哪几个?错误的流程图有哪几个?错误的要指出错在哪里. (2) 错误的流程图中, 按该流程图所蕴含的算法, 能执行到底吗?若能执行到底, 最后输出的结果是什么? https://www.99xueshu.com/w/ikeyuh2rnlqg.html