当前位置:首页 > 文化 > 正文内容

霍夫曼编码(哈夫曼编码的码字怎么看)

2021-08-28 17:10:05文化744

大家好,小活来为大家解答以上的问题。哈夫曼编码的码字怎么看,霍夫曼编码这个很多人还不知道,现在让我们一起来看看吧!

1、霍夫曼编码是一种被广泛应用而且非常有效的数据压缩技术,根据待压缩数据的特征,一个可压缩掉20%~90%。

霍夫曼编码(哈夫曼编码的码字怎么看)

2、这里考虑的数据指的是字符串序列。

3、要理解霍夫曼编码,先要理解霍夫曼树,即最优二叉树,是一类带权路径长度最短的树。

4、路径是指从树中一个结点到另一个结点之间的通路,路径上的分支数目称为路径长度。

5、树的路径长度是从树根到每一个叶子之间的路径长度之和。

6、结点的带权路径长度为从该结点到树根之间的路径长度与该结点权的乘积,树的带权路径长度为树中所有叶子结点的带权路径长度之和.霍夫曼树是指所有叶子结点的二叉树中带权路径长度最小的二叉树.当给定了n个叶子结点的权值后,构造出的最优二叉树的结点数目m就确定了,即m=2n-1,所以可用一维结构树组来存储最优二叉树#define MAXLEAFNUM 50 /*最优二叉树中最大叶子树目*/struct node{ char ch; /*当前结点表示的字符,对于非叶子结点,此域不用*/ int weight; /*当前结点的权值*/ int parent; /*当前结点的父结点的下标,为0时表示无父结点*/ int lchild,rchild; /*当前结点的左,右孩子结点的下标,为0时表示无孩子结点*/}HuffmanTree[2 * MAXLEAFNUM];typedef char *HuffmanCode[MAXLEAFNUM + 1];创建最优二叉树void createHTree(HuffmanTree HT, char *c, int *w, int n){ /*数组c[0..n-1]和w[0..n-1]存放了n个字符及其概率,构造霍夫树HT*/ int i, s1, s2; if (n <= 1) return;/*根据n个权值构造n棵只有根结点的二叉树*/ for (i=1; i<=n; i++) { HT[i].ch = c[i-1]; HT[i].weight = w[i-1]; HT[i].parent = HT[i].lchild = HT[i].rchild = 0; }for (; i<2*n; ++i) { HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0; }/*构造霍夫曼树*/ for (i=n+1; i<2*n; i++) { /*从HT[1..i-1]中选择parent为0且weight最小的两棵树,其序号为s1和s2*/ select(HT,i-1,s1,s2); HT[s1].parent = i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; }}应用霍夫曼编码假设有一个包含100 000个字符的数据文件要压缩存储。

7、各字符在该文件中的出现频度见表1。

8、仅有6种不同字符出现过,字符a出现了45000次。

9、 a b c d e f 频度(千字) 45 13 12 16 9 5固定代码字 000 001 010 011 100 101变长代码字 0 101 100 111 1101 1100表1 一个字符编码问题。

10、大小为100 000个字符的一个数据文件仅包含字符a~f,每个字符出现的频度如表中所示。

11、如果对每个字符赋予一个三位的编码,则该文件可被编码为300000位。

12、如果利用表中的可变长度编码,该文件可被编码为224000位。

13、可以用很多种方式来表示这样一个文件。

14、采用固定长度编码,则需要三位二进制数字来表示六个字符:a=000,b=001,…,f=101。

15、这种方法需要300 000来对整个原文件编码。

16、 而可变长度编码是对频度高的字符赋以短编码,而对频度低的字符赋以较长一些的编码。

17、表1显示了这种编码,其中一位串0表示a,四位串1100表示f。

18、这种编码方式需要 (45*1+13*3+12*3+16*3+9*4+5*4)*1000 = 224 000 位来表示整个文件,即可压缩掉约25%。

19、这其实就是最优字符编码(霍夫曼编码)前缀编码我们这里考虑的编码方案中,没有一个编码是另一个编码的前缀。

20、这样的编码称为前缀编码(或许“无前缀编码“是个更好的名字,但是前缀编码是标准的书面语)。

21、 对任何一种二进制字符编码来说编码总是简单的,这只要将文件中表示每个字符的编码并置起来即可。

22、利用表1的可变长度编码,把包含三个字符的文件abc编成0 . 101 . 100 = 0 101 100,其中“.“表示并置。

23、 在前缀编码中解码也是很方便的。

24、因为没有一个码是其他码的前缀,故被编码文件的开始处的编码是确定的。

25、我们只要识别出第一个编码,将它翻译成原文字符,再对余下的编码文件重复这个解码过程即可。

26、在我们的例子中,可将串001 011 101唯一地分析为0.0.101.1101,因此可解码为aabe。

27、 解码过程需要有一种关于前缀编码的方便表示,使得初始编码可以很容易地被识别出来。

28、有一种表示方法就是叶子为给定字符的二叉树。

29、在这种树中,我们将一个字符的编码解释为从根至该字符的路径,其中0表示“转向左子结点”,1表示“转向右子结点“。

30、如下给出最优二叉树,如图1。

31、图1以下给出查找最优二叉树叶子结点编码的算法typedef char *HuffmanCode[MAXLEAFNUM + 1];(本文开头也有说明)void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int n){ /* n个叶子结点在霍夫曼树HT中的下标为1~n,*/ /*第i(1<= i <= n)个叶子的编码存放HC[i]中*/ char *cd; int i,start,c,f; if (n<=1) return;/*分配n个字节的内存,用来存放当前得到的编码*/ /*n个叶子结点最大的编码长度为n所以分配n个字节*/ cd = (char*)malloc(n) cd[n-1] = ‘/0’;for (i=1; i<=n; i++) { start = n -1; for (c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent) /*从叶子结点开始查找编码*/ /*叶子结点的父结点的左子树为叶子结点,则编码为0*/ /*否则就为父结点的右子树,则编码为1*/ if (HT[f].lchild = = c) cd[--start] = ‘0’; else cd[--start] = ‘1’; /*分配内存,分配内存的字节数为当前得到的字符编码数*/ HC[i] = (char*)malloc(n-start); strcpy(HC[i], &cd[start]);}free(cd);}译码算法为:从根结点出发,按二进制位串中的0和1确定是进入左分支还是右分支,当到达叶子结点时译出该叶子对应的字符。

32、数据文件(包含编码)未结束,则回到根结点继续进行上述过程。

33、给出如下函数:void Decoding(HuffmanTree HT, int n, char *buff){ /*利用具有n个叶子结点的最优二叉树(存储在数组HT中)进行译码,叶子的下标*//*为1~n,buff指向数据文件的编码序列*/int p = 2*n -1; /*指向根结点*/while (*buff){ if ((*buff) = = ‘0’) p = HT[p].lchild; /*进入左分支*/ else p = HT[p].rchild; /*进入右分支*//*到达一个叶子结点*/ if(HT[p].lchild = = 0 && HT[p].rchild = = 0) { printf(“%c”, HT[p].ch); p = 2*n – 1; /*回到根结点*/ }buff++;}}。

本文到此分享完毕,希望能帮助到大家。

扫描二维码推送至手机访问。

版权声明:文章内容摘自网络,如果无意之中侵犯了您的版权,请联系本站,本站将在3个工作日内删除。谢谢!

本文链接:http://xixia168.cn/n/wh/127133.html

标签: 码字怎么看
分享给朋友:

“霍夫曼编码(哈夫曼编码的码字怎么看)” 的相关文章

关于广东专业技术人员继续教育信息管理系统的介绍(广东专业技术人员继续教育信息管理系统)

关于广东专业技术人员继续教育信息管理系统的介绍(广东专业技术人员继续教育信息管理系统)

大家好,小编猫猫来为大家解答这个问题。广东专业技术人员继续教育信息管理系统,关于广东专业技术人员继续教育信息管理系统的介绍很多人还不知道,现在让我们一起来看看吧!1、ee专业技术人员远程教育网是助力计划·广东教育实施机构,由广东省人力资源和社会保障厅审核备案并授牌确认,依托国内顶尖的远程教育公共服务...

关于瑞雪兆丰年的前一句的介绍(瑞雪兆丰年的前一句)

关于瑞雪兆丰年的前一句的介绍(瑞雪兆丰年的前一句)

大家好,小编毛毛来为大家解答这个问题。瑞雪兆丰年的前一句,关于瑞雪兆丰年的前一句的介绍很多人还不知道,现在让我们一起来看看吧!1、春雨贵如油,释义:春天的细雨像油一样可贵,形容春雨宝贵难得。2、出自宋·释道原《景德传灯录》、明·解缙《春雨》。这篇文章到此就结束,希望能帮助到大家。...

关于安顺事件的描述(安顺事件)

关于安顺事件的描述(安顺事件)

今天来聊聊关于安顺事件,关于安顺事件的描述的文章,现在就为大家来简单介绍下安顺事件,关于安顺事件的描述,希望对各位小伙伴们有所帮助。1、2014年9月5日凌晨,贵州安顺市七眼桥镇发生一起警民冲突事件,打斗中该镇派出所两名协警死亡、两名协警受伤。2、该镇派出所工作人员在9月8日向记者确认了这一事实,死...

关于小庠岛的介绍(小庠岛)

关于小庠岛的介绍(小庠岛)

大家好,小编毛毛来为大家解答这个问题。小庠岛,关于小庠岛的介绍很多人还不知道,现在让我们一起来看看吧!1、福建省平潭综合实验区为福建省辖行政管理区。2、位于福建省东部,与台湾岛隔海相望,是中国大陆距离台湾最近的地方。3、平潭综合实验区有中国的“马尔代夫”之称,同时也是著名的渔业基地。4、平潭综合实验...

火焰之王的精华(火焰之王的精华任务是什么)

火焰之王的精华(火焰之王的精华任务是什么)

大家好,小活来为大家解答以上的问题。火焰之王的精华任务是什么,火焰之王的精华这个很多人还不知道,现在让我们一起来看看吧!1、不是 那个是橙色东西。2、是英文的翻译过来是火焰之王的精华。3、是任务物品 上面写着需要100级。4、好象是橙色锤子还是那把单手剑的。5、 到Live天空之城!网站查...

关于乐比悠悠动画片全集的介绍(乐比悠悠动画片全集)

关于乐比悠悠动画片全集的介绍(乐比悠悠动画片全集)

大家好,小编大牛来为大家解答这个问题。乐比悠悠动画片全集,关于乐比悠悠动画片全集的介绍很多人还不知道,现在让我们一起来看看吧!1、乐比,3D动画片《乐比悠悠》主角。2、《乐比悠悠》是中国内地在2000年上映,一部针对0-5岁儿童的低幼类儿童系列片。3、故事中以乐比和悠悠为中心点,讲述了乐比悠悠在生活...