基于哈夫曼编码的密码系统数据压缩与解压实现(2)
时间:2019-08-23 12:56 来源:毕业论文 作者:毕业论文 点击:次
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) 式中, 表示信源缩减的次数． (责任编辑：qin) |