新闻中心

EEPW首页 > 手机与无线通信 > 设计应用 > 网络高效安全数据传输方法设计

网络高效安全数据传输方法设计

作者:时间:2015-04-12来源:网络收藏

  2介绍

本文引用地址:http://www.eepw.com.cn/article/272396.htm

  是20世纪50年代由哈夫曼教授研制开发的,它借助了数据结构当中的树型结构,在哈夫曼算法的支持下构造出一棵最优二叉树,把这类树命名为哈夫曼树。因此,准确地说,是在哈夫曼树的基础之上构造出来的一种编码形式,它的本身有着非常广泛的应用。

  2.1基本原理

  数据能够被压缩的理论依据如下:

  定义1对于给定的信源和码符号集,若有一个惟一可译码,其平均码长L小于所有其他惟一可译码,则称这种码为紧致码或最佳码。

  定理1哈夫曼编码是紧致码。

  计算机文件是以字节为单位组成的,每个字节的取值为O~255.每个字节都看成字符,共256种字符。因此,每个字节都是以8个二进制位的定长编码表示的。由于这种定长码也是惟一可译码,根据定理1有L≤8.

  设某个文件有N个字节组成,则该文件总长度为8N比特。如果对该文件进行哈夫曼编码,则该文件总长度为LN比特。由于L≤8,所以LN≤8。所以,只要文件满足L<8,用哈夫曼编码总可以对其压缩。

  哈夫曼编码是一种变长编码,即通过使用较短的码字来给出现概率较高的信源符号编码,而出现概率较小的信源符号用较长的码字来编码,从而使平均码长最短,达到最佳编码的目的。由于哈夫曼编码只能对概率已知的信源符号编码,因此是一种统计编码。

  2.2 构造哈夫曼编码表

  获得一个文件的哈夫曼编码表是该文件获得压缩与解压的关键。设某个文件中含有q种字符S1,S2,…,Sq,并且统计出每种字符在文件中出现的概率分别为p(S1),p(S2),…,p(Sq),则编码的具体方法如下:

  (1)将q个信源符号按概率大小递减排列p(S1)≥p(S2)≥…≥p(Sq);

  (2)用字符‘O’和‘1’分别代表概率最小的2个信源符号,并将这2个概率最小的信源符号合并成1个信源符号,从而得到只包含q-1个符号的新信源,称为缩减信源S1;

  (3)把缩减信源S1的符号仍按概率大小递减次序排列,再将其最后两个概率最小的信源符号分别用字符‘O’和‘1’表示,并且合并成一个符号,这样又形成了q-2个信源符号的缩减信源S2;

  (4)依次继续下去,直至信源最后只剩下两个信源符号为止,将这最后两个信源符号分别用字符‘O’和‘1’表示;

  (5)然后从最后一级缩减信源开始,进行回推就得到每种字符所对应的由字符‘O’和‘1’组成的字符串序列,不妨将其称为伪码字。

  这样,就为需要压缩的文件建立了一个一一映射f:Si→ci=1,2,…,q。式中:Si代表不同的字符,ci代表对应字符Si的伪码字。

  为了将伪码字变成真正的码字,又必须建立一个映射g:ci→ω,i=1,2,…,q。式中:ci代表不同的字符,(ωi代表对应字符ci的码字。该映射g 的功能是将由字符串组成的伪码字变成二进制数,比如g(010110)=(010110)2=(22)10。从而g[f(Si)],i=1,2,…,q,就是构造的哈夫曼编码表。

  2.3 文件压缩过程

  每从文件中读出一个字符char,用查哈夫曼编码表的方式得到对应的码字,然后用这个码字替换相应的字符g[f(char)]。当文件中的所有字符都经过了码字替换,则得到一个比原文件要小的压缩文件。文件之所以能够被压缩,是因为每个字符都占8个二进制位的空间。然而,通过码字替换相应的字符后,有的码字比相应的字符的码长要短,有的码字比相应的字符的码长要长,但文件在被压缩后总的长度比原来要短。

  2.4 文件解压过程

  文件的解压过程是文件的压缩过程的逆过程,即将一个压缩文件还原成它的本来面目。因为一个压缩文件是不能够直接使用的,只有被解压后才能使用。一个被压缩的文件如果不能被解压,则这种压缩是毫无意义的。

  哈夫曼编码是即时码,只要得到码字c,则经查哈夫曼编码表得到相应字符f-1(g-1(c)),用这个字符替换相应的码字就是还原的过程。因此,每从压缩文件中读出一个码字,就从哈夫曼编码表查得相应的字符替换,当文件中所有的码字被替换掉,这个解压过程也就完成了。



关键词: 哈夫曼编码

评论


技术专区

关闭