作业帮哈夫曼树 3位固定长度编码是什么?
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/16 13:01:17
哈夫曼树 3位固定长度编码是什么?
哈夫曼树 3位固定长度编码是什么?
哈夫曼树 3位固定长度编码是什么?
主可以去看看最优二叉树的编码问题.
1、哈夫曼编码
在数据通信中,需要将传送的文字转换成二进制的字符串,用0,1码的不同排列来表示字符.例如,需传送的报文为“AFTER DATA EAR ARE ART AREA”,这里用到的字符集为“A,E,R,T,F,D”,各字母出现的次数为{8,4,5,3,1,1}.现要求为这些字母设计编码.要区别6个字母,最简单的二进制编码方式是等长编码,固定采用3位二进制,可分别用000、001、010、011、100、101对“A,E,R,T,F,D”进行编码发送,当对方接收报文时再按照三位一分进行译码.显然编码的长度取决报文中不同字符的个数.若报文中可能出现26个不同字符,则固定编码长度为5.然而,传送报文时总是希望总长度尽可能短.在实际应用中,各个字符的出现频度或使用次数是不相同的,如A、B、C的使用频率远远高于X、Y、Z,自然会想到设计编码时,让使用频率高的用短码,使用频率低的用长码,以优化整个报文编码.
为使不等长编码为前缀编码,可用字符集中的每个字符作为叶子结点生成一棵编码二叉树,为了获得传送报文的最短长度,可将每个字符的出现频率作为字符结点的权值赋予该结点上,求出此树的最小带权路径长度就等于求出了传送报文的最短长度.因此,求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点,由字符出现频率作为其权值所产生的哈夫曼树的问题.利用哈夫曼树来设计二进制的前缀编码,既满足前缀编码的条件,又保证报文编码总长最短.
哈夫曼静态编码：它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率,利用得到的频率值创建哈夫曼树,并必须把树的信息保存起来,即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来,（用4Bytes的长度存储频率值,频率值的表示范围为0--2^32-1,这已足够表示大文件中字符出现的频率了）以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码,并把编码后得到的码字存储起来.
哈夫曼动态编码：动态哈夫曼编码使用一棵动态变化的哈夫曼树,对第t 1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的,编码和解码使用相同的初始哈夫曼树,每处理完一个字符,编码和解码使用相同的方法修改哈夫曼树,所以没有必要为解码而保存哈夫曼树的信息.编码和解码一个字符所需的时间与该字符的编码长度成正比,所以动态哈夫曼编码可实时进行.[3]
2、哈夫曼译码
在通信中,若将字符用哈夫曼编码形式发送出去,对方接收到编码后,将编码还原成字符的过程,称为哈夫曼译码.[4]