登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

天道酬勤 玩物丧志

用勇气去改变可以改变的事情,用胸怀去包容无法改变的事情,用智慧去判断两者的区别

 
 
 

日志

 
 

熵编码  

2011-04-01 13:00:31|  分类: 信息论 编码 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
定义:编码过程中按熵原理不丢失任何信息的编码。

        熵编码即编码过程中按熵原理不丢失任何信息的编码。信息熵为信源的平均信息量(不确定性的度量)。常见的熵编码有:行程编码(RLE)、LZW编码、香农(Shannon)编码、哈夫曼(Huffman)编码和算术编码(arithmetic coding)。在视频编码中,熵编码把一系列用来表示视频序列的元素符号转变为一个用来传输或是存储的压缩码流.输入的符号可能包括量化的变换系数(像上面所说的运行级或零树),运动向量(对于每个运动补偿块的向量值x和y),标记(在序列中用来表示重同步位的点),头(宏块头,图象头,序列的头等)以及附加信息(对于正确解码来说不重要的信息).

简介  数据压缩技术的理论基础就是信息论。信息论中的信源编码理论解决的主要问题:(1)数据压缩的理论极限(2)数据压缩的基本途径。根据信息论的原理,可以找到最佳数据压缩编码的方法,数据压缩的理论极限是信息熵。如果要求编码过程中不丢失信息量,即要求保存信息熵,这种信息保持编码叫熵编码,是根据消息出现概率的分布特性而进行的,是无损数据压缩编码。

熵编码编码

  使用长度不同的比特串对字母进行编码有一定的困难。尤其是,几乎所有几率的熵都是一个有理数。

使用整数位元( bit)

  ?哈夫曼编码建议了一种将位元进位成整数的算法,但这个算法在特定情况下无法达到最佳结果。为此有人加以改进,提供最佳整数位元数。这个算法使用二叉树来设立一个编码。这个二叉树的终端节点代表被编码的字母,根节点代表使用的位元。

  除这个对每个要编码的数据产生一个特别的表格的方法外还有使用固定的编码表的方法。比如加入要编码的数据中符号出现的机率符合一定的规则的话就可以使用特别的变长编码表。这样的编码表具有一定的系数来使得它适应实际的字母出现机率。

熵编码模型

  要确定每个字母的比特数算法需要尽可能精确地知道每个字母的出现机率。模型的任务是提供这个数据。模型的预言越好压缩的结果就越好。此外模型必须在压缩和恢复时提出同样的数据。在历史上有许多不同的模型。

静态模型

  静态模型在压缩前对整个文字进行分析计算每个字母的机率。这个计算结果用于整个文字上。

  优点:

  编码表只需计算一次,因此编码速度高

  除在解码时所需要的机率值外结果肯定不比原文长

  缺点:

  计算的机率必须附加在编码后的文字上,这使得整个结果加长

  计算的机率是整个文字的机率,因此无法对部分地区的有序数列进行优化

动态模型

  ?在这个模型里机率随编码过程而不断变化。多种算法可以达到这个目的:

  前向动态:机率按照已经被编码的字母来计算,每次一个字母被编码后它的机率就增高

  反向动态:在编码前计算每个字母在剩下的还未编码的部分的机率。随着编码的进行最后越来越多的字母不再出现,它们的机率成为0,而剩下的字母的机率升高,为它们编码的比特数降低。压缩率不端增高,以至于最后一个字母只需要0比特来编码

  优点:

  模型按照不同部位的特殊性优化

  在前向模型中机率数据不需要输送

  缺点:

  每个字母被处理后机率要重算,因此比较慢

  计算出来的机率与实际的机率不一样,在最坏状态下压缩的数据比实际原文还要长。

  一般在动态模型中不使用机率,而使用每个字母出现的次数。除上述的前向和反向模型外还有其它的动态模型计算方法。比如在前向模型中可以不时减半出现过的字母的次数来降低一开始的字母的影响力。对于尚未出现过的字母的处理方法也有许多不同的手段:比如假设每个字母正好出现一次,这样所有的字母均可被编码。

模型度

  ?模型度说明模型顾及历史上多少个字母。比如模型度0说明模型顾及整个原文。模型度1说明模型顾及原文中的上一个字母并不断改变其机率。模型度可以无限高,但是对于大的原文来说模型度越高其需要的计算内存也越多。

 

 

  评论这张
 
阅读(821)| 评论(0)

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018