复盘:霍夫曼编码平均长度计算方式,信源符号a1-a6概率为:0.1,0.4,0.06,0.1,0.04,0.3,霍夫曼编码平均长度是

  • Post author:
  • Post category:其他




复盘:霍夫曼编码平均长度计算方式,信源符号a1-a6概率为:0.1,0.4,0.06,0.1,0.04,0.3,霍夫曼编码平均长度是


提示:系列被面试官问的问题,我自己当时不会,所以下来自己复盘一下,认真学习和总结,以应对未来更多的可能性

关于互联网大厂的笔试面试,都是需要细心准备的

(1)自己的科研经历,

科研内容

,学习的相关领域知识,要熟悉熟透了

(2)自己的实习经历,做了

什么内容

,学习的领域知识,要熟悉熟透了

(3)除了科研,实习之外,平时自己关注的

前沿知识

,也不要落下,仔细了解,面试官很在乎你是否喜欢追进新科技,跟进创新概念和技术

(4)准备

数据结构与算法

,有笔试的大厂,第一关就是手撕代码做算法题

面试中,实际上,你准备数据结构与算法时以备不时之需,有足够的信心面对面试官可能问的算法题,很多情况下你的科研经历和实习经历足够跟面试官聊了,就不需要考你算法了。但很多大厂就会面试问你算法题,因此不论

为了笔试面试

,数据结构与算法必须熟悉熟透了

秋招提前批好多大厂不考笔试,直接面试,能否免笔试去面试,那就看你

简历实力

有多强了。





信源符号a1-6,概率为:0.1,0.4,0.06,0.1,0.04,0.3,使用霍夫曼编码,这个编码的平均长度为?

多少比特/像素??

2.12,2.2,2.4,2.6?

霍夫曼编码是变长编码,思路:

对概率大的

编的码字短



概率小的编的码字长



这样一来所编的总码长就小,这样编码效率就高。

(0)准备一个堆heap,小根堆

(1)现将概率全部放入堆中,弹出俩小的,a4,a5,从小的开始迭代相加,c=a4+a5然后放回堆中:

(3)在逻辑上画一个分支图,将上分支编码为0,下分支编码为1,下图a4,a5那俩分支

(4)不断重复(1)直到最后heap剩下1个元素即可

在这里插入图片描述

每次上分支为0,下分支编码为1

这样最后发现

a1的概率最大,编码最短:0

往下分别编码为:10

110

111

1110

1111

这样长度分别是:1 2 3 3 4 4

平均长度就是(1+2+3+3+4+4)/6=17/6=2.8左右


这是错的计算方式!!!!!!!!!!!!!!!!



这是错的计算方式!!!!!!!!!!!!!!!!



这是错的计算方式!!!!!!!!!!!!!!!!

这就是哈夫曼编码的平均长度计算法方法

最主要就是编码过程自己要熟悉



咱来搞一下本题

信源符号a1-a6概率为:0.1,0.4,0.06,0.1,0.04,0.3,霍夫曼编码平均长度是

在这里插入图片描述

我怎么算都是

3.333


但是题目为啥就给了这点答案,我是不明白了………………

当时做这个题我就自闭了


不!!!!!!!!!!!!!

你刚刚那么算,是相当于等概率,大家的长度都一样长,除6是可以的,但是很显然概率不相等的话,你不能这么求,人家出现概率小的长度长,实际最后贡献还是小概率,就应该短点。

哈夫曼编码的平均长度好像是还需要乘概率,为啥呢??

因为你长度是那么多,但是出现的概率可能没那么大!!!

所以得用各自的概率再乘自己的长度


0.04

5+0.06

5+0.1

4+0.1

3+0.3

2+0.4

1=2.2

哎,我当时也没会啊!!!!

终于求对了呵呵哈哈哈

所以选了一个2.6

气炸,这次我知道了!!!!!




总结


提示:重要经验:

1)哈夫曼编码编码的平均长度,跟信源概率有很大关系,概率大的,编码短,概率小的编码长,这样加权平均之后,平均长度很短哦!!编码效率高

2)千万不能直接求和取平均,这是错误的,除非概率都是均等的!!!!!

3)笔试求AC,可以不考虑空间复杂度,但是面试既要考虑时间复杂度最优,也要考虑空间复杂度最优。



版权声明:本文为weixin_46838716原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。