复盘:霍夫曼编码平均长度计算方式,信源符号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,可以不考虑空间复杂度,但是面试既要考虑时间复杂度最优,也要考虑空间复杂度最优。