毕业论文
计算机论文
经济论文
生物论文
数学论文
物理论文
机械论文
新闻传播论文
音乐舞蹈论文
法学论文
文学论文
材料科学
英语论文
日语论文
化学论文
自动化
管理论文
艺术论文
会计论文
土木工程
电子通信
食品科学
教学论文
医学论文
体育论文
论文下载
研究现状
任务书
开题报告
外文文献翻译
文献综述
范文
基于哈夫曼编码的密码系统数据压缩与解压实现(2)
1.哈夫曼编码
1.1哈夫曼编码的简介
哈夫曼编码是一种编码方式,哈夫曼编码是可变字长编码的一种,在
计算机
信息处理中,哈夫曼编码是一种一致性编码法,即唯一可译码,又称熵编码法,它是由哈夫曼教授于20世纪50年代提出一种最有效的编码方法,该方法完全依据字符出现概率的大小来构造异字头的平均长度最短的码字,一般就叫作哈夫曼编码.哈夫曼编码是在哈夫曼树的基础上构造出来的一种编码方式,而哈夫曼树是根据数据结构中树形结构的方法构造出来的一种最优二叉树,即带权路径长度最小的二叉树.哈夫曼编码经常应用于数据压缩,目前数据压缩技术主要分为有损数据压缩与无损数据压缩两大类,而哈夫曼编码经常用于数据的无损耗压缩.被压缩后的文件所占内存空间减少,为大文件的存储和传输带来便利.
1.2二元哈夫曼编码的步骤[9]
这是霍夫曼于1952年提出的一种构造紧致码的方法.具体方法如下:
(1)将q个信源符号按概率大小递减排列
(2)用“0,1”码符号分别代表概率最小的两个信源符号,并将这两个概率最小的信源符号合并成一个,从而得到只包含q-1个符号的新信源 ,称为缩减信源 ;
(3)把缩减信源 的符号仍按概率大小递减次序排列,再将其最后两个概率最小的信源符号分别用“0”和“1”码符号表示,并且合并成一个符号,这样又形成了q-2个信源符号的缩减信源 ;
(4)依次继续下去,直至信源最后只剩下两个信源符号为止,将这最后两个信源符号分别用二元码符号“0”和“1”表示;
(5)然后从最后一级缩减信源开始,进行回溯,就得到各信源符号所对应的码符号序列,即相应的码字.
下面的举例说明二元哈夫曼编码的实现过程.
例1:设信源共有7个符号组成,分别是 其概率分别是[0.20,0.19,0.18,0.17,0.15,0.10,0.01],求其哈夫曼码.
哈夫曼编码的具体过程如下表1所示.
表1 哈夫曼编码的过程
信源符号 符号概率 编 码 过 程 码字 码长
从表1中编码过程可以看出,哈夫曼编码方法得到的码一定是即时码.因为这种编码方法不会使任一码字的前缀为码字.这一点在用码树形式来表示的时候,看得更清楚.下图1是用码树形式进行哈夫曼编码的过程.哈夫曼编码树
在图1中由于代表信源符号的节点都是终端节点,因此其编码不可能是其它终端节点对应的编码的前缀.另外,由于哈夫曼编码总是把概率大的符号安排在离根节点近的终端节点,所以其码长比较小,因此得到的编码整体平均码长就比较小.
定理1 [9] 哈夫曼编码是紧致码.
1.3多元哈夫曼编码[9]
二进制哈夫曼编码方法可以很容易推广到r进制的情况.只是编码过程中构成缩减信源时,每次都是将r个概率最小的符号合并,并分别用0,1,…,(r-1)码符号表示.
为了充分利用短码,使哈夫曼码的平均码长最短,必须使最后一个缩减信源有r个信源符号.因此,对于r元哈夫曼编码,信源S符号个数q必须满足
q=(r-1)θ+r (1)
式中, 表示信源缩减的次数.
共3页:
上一页
1
2
3
下一页
上一篇:
基于MATLAB的图像压缩
下一篇:
家用汽车的抽样调查影响购车因素
基于决策树算法的篮球联赛预测
基于t分布对还黄金期货的投资风险分析
基于长时间序列MODIS数据的...
基于小学生视角的数学作业批改现状的调查
基于高分影像的钱塘江主要污染区域遥感监测
基于鹰鸽博弈的动物行为博弈论模型
基于logit模型的大学生金融投资理财行为研究
C#学校科研管理系统的设计
10万元能开儿童乐园吗,我...
国内外图像分割技术研究现状
中国学术生态细节考察《...
神经外科重症监护病房患...
公寓空调设计任务书
医院财务风险因素分析及管理措施【2367字】
志愿者活动的调查问卷表
AT89C52单片机的超声波测距...
承德市事业单位档案管理...