香农-范诺编码

✍ dations ◷ 2025-09-11 04:34:18 #香农-范诺编码

在数据压缩的领域里,香农-范诺编码(英语:Shannon–Fano coding)是一种基于一组符号集及其出现的或然率(估量或测量所得)构建前缀码的技术。其名称来自于克劳德·香农和罗伯特·范诺。在编码效率上,它并不能与霍夫曼编码一样实现编码(code word)长度的最低期望;然而,与霍夫曼编码不同的是,它确保了所有的编码长度在一个理想的理论范围 log P ( x ) {displaystyle {-log }P(x)} 之内。这项技术是香农于1948年,在他介绍信息理论的文章“通信数学理论”中提出的。范诺则在不久以后独立地以技术报告形式将其发布。 香农-范诺编码不应该与香农编码混淆,后者的编码方法用于证明Shannon's noiseless coding theorem,或与Shannon–Fano–Elias coding(又被称作Elias coding)一起,被看做算术编码的先驱。

香农-范诺编码将符号从最大可能性到最少可能性排序,并将排列好的信源符号分为两大组,使两组的概率和接近,并各赋予一个二进制符号“0”和“1”。只要有符号剩余,就以同样的过程重复这些步骤以此确定这些代码的连续编码数字。依次下去,直至每一组的只剩下一个信源符号为止。当一组已经仅剩余一个符号,显然,这意味着这一符号的编码是完整的,也不会成为任何其他符号的代码前缀。

香农-范诺编码能够产生相对高效的可变长度编码;对于每一个比特位而言,当两个较小的集合具有恰好相等的概率时,这一方法就能最有效地利用这一位编码的信息。然而,香农-范诺并不总是产生最优的前缀码:例如对概率{0.35,0.17,0.17,0.16,0.15},香农-范诺算法就无法给出理想的编码。出于这个原因,香农-范诺编码几乎从不被使用。

Shannon-Fano编码树是基于一个符号和对应频率的列表建立的。实际的算法很简单:

这个例子展示了一组字母的香农编码结构(如图a所示)这五个可被编码的字母有如下出现次数:

从左到右,所有的符号以它们出现的次数划分。在字母B与C之间划定分割线,得到了左右两组,总次数分别为22、17,这样就把两组的差别降到最小。通过这样的分割,A与B同时拥有了一个以0为开头的编码,C、D、E的前缀则为1,如图b所示。随后,在树的左半边,于A、B间建立新的分割线,这样A就成为了编码为00的叶子节点,B的编码为01。经过四次分割,得到了一个树形编码。如下表所示,在最终得到的树中,拥有最大频率的符号被两位编码,其他两个频率较低的符号被三位编码。

根据A,B,C两位编码长度,D,E的三位编码长度,最终的平均码字长度是

香农-范诺编码算法并非总能得到最优编码。1952年, David A. Huffman提出了一个不同的算法,这个算法可以为任何的可能性提供出一个理想的树。香农-范诺编码是从树的根节点到叶子节点所进行的的编码,霍夫曼编码算法却是从相反的方向,暨从叶子节点到根节点的方向编码的。

用以上Shannon - Fano例子所使用的分析,即:

首先将D、E合并,它们频率和为11(图a至图b)。接下来概率最低的一组是B(7)和C(6),所以将他们作为左右子树组成新的根结点BC。在剩下的三个节点中,BC(13)和DE(11)的频率和最低,因此组成新的二叉树BE。最后将仅剩的两个节点合并,并分别为它们分配前缀0和1。这样所有的节点都成为了唯一一个编码树的叶节点。

这个例子中,A的编码长度是1比特,其余字符是3比特。

结果是

相关

  • 爱德华三世爱德华三世(英语:Edward III,1312年11月13日-1377年6月21日),英格兰国王,1327年到1377年在位。爱德华三世是被谋杀的爱德华二世的儿子,生于伯克郡温莎。其母法兰西的伊莎贝拉与马奇
  • 勋爵勋爵是一种敬称,主要用于翻译英语中对有爵位的贵族的泛称(英语:Lord),也是对此类男性贵族的称呼,和对某些封爵的儿子,及一些拥有相应身份但没有爵位的人士的尊称。此外也可用来翻译
  • 体验业体验业是中国大陆学者振中(原名谢域培)先生在《体验业,改变未来》中提出来的新概念,该书在2013年1月正式出版。根据振中著作的理论,体验是指人们由于好奇心的驱使,出于满足好奇心
  • 全日本CM放送联盟社团法人全日本CM放送联盟(日语:一般社団法人全日本シーエム放送連盟,英语:All Japan Radio & Television Commercial Confederation,通称ACC),是由日本广告主协会(Japan Advertiser
  • 镁害镁害是一种在生产食盐时产生的副产品对环境造成的祸害。当生产商从海水或含盐分的盐水湖湖水中提取食盐时,由于盐液中除了含有食盐的主要成分氯化钠以外,还含有相对分量带苦味
  • 范文树范文树(越南语:Phạm Văn Thụ/.mw-parser-output .han-nom{font-family:"Nom Na Tong","Han-Nom Gothic","Han-Nom Ming","HAN NOM A","HAN NOM B","Ming-Lt-HKSCS-UNI-H","M
  • 月事革命《月事革命》(英语:Period. End Of Sentence.)是Rayka Zehtabchi于 2018年所执导的纪录短片。片中纪录了一场由印度妇女所领导的安静的性革命。影片纪录了印度哈普尔的一群当地
  • 萨萨里语萨萨里语(Sassaresu)是意大利-达尔马提亚语支下属的一种语言,在传统上位于科西嘉语和撒丁语之间。尽管受到了很强的撒丁语影响(特别是词汇和发
  • 石泰石泰(1022年-1158年),宋代常州人。字得之,号杏林,道号翠玄子。为道教金丹派尊奉的五位重要人物(南五祖)之一。金丹派道教大师张伯端曾得罪凤州太守,被坐黥窜,途中于酒肆遇石泰,由于石泰为张讲情,终得赦免。张伯端后授石泰道教丹法的道术。作有《还源篇》等。
  • 汉城国立大学附属医院屠杀事件汉城国立大学附属医院屠杀事件(朝鲜语:서울대학교 부속병원 학살 사건/서울大學校附屬病院虐殺事件)发生于朝鲜战争爆发3日之后、1950年6月28日的第一次汉城战役期间,汉城大学附属医院(现首尔大学医院(英语:Seoul National University Hospital))内的医生、护士、住院平民及伤兵在此事件中遭到朝鲜人民军陆军集体虐杀,共700人至900人遇害。在当日,进攻的朝鲜士兵,歼灭了一整个排的医院守军,之后医院内的军人、平民多人遭到射杀,甚至活埋。根据韩国国防部的统计,遇害者中有100