香农-范诺编码

✍ dations ◷ 2025-07-11 21:50:15 #香农-范诺编码

在数据压缩的领域里,香农-范诺编码(英语: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比特。

结果是

相关

  • 投敌叛变罪投敌叛变罪是指机构、组织或个人资助境内组织或者个人实施危害国家安全罪。对直接责任人员,处三年以上十年以下有期徒刑;情节严重或者带领武装部队人员、人民警察、民兵投敌
  • 乙酸镁乙酸镁,化学式(CH3COO)2Mg。无色易潮解结晶,溶于水和醇。由氧化镁与乙酸反应而得。用于制备乙酸铀酰镁,后者是测定钠的试剂。
  • 罗琳斯公共卫生学院罗琳斯公共卫生学院(Rollins School of Public Health)为埃默里大学下属九所学院之一。此学院建立于1990年,素为公卫领域之领导人,与哈佛,约翰·霍普金斯大学共享盛名。目前总计
  • 鲁门·赫里斯托夫 (政治人物)鲁门·季米特洛夫·赫里斯托夫(保加利亚语:Румен Димитров Христов;1955年12月27日-),是一名保加利亚政治人物,民主力量联盟党员。2016年12月,赫里斯托夫宣称所
  • 马莱尔科特拉马莱尔科特拉(Malerkotla),是印度旁遮普邦Sangrur县的一个城镇。总人口106802(2001年)。该地2001年总人口106802人,其中男性56872人,女性49930人;0—6岁人口14332人,其中男7669人,女66
  • Ubuntu (字体)Ubuntu字体家族是一个OpenType字体,被设计为现代的人文主义体字体,由Canonical公司委托Dalton Maag所设计。这个字体历经约九个月的开发,其中只有发布过一次测试版,直到2010年9
  • 布德特峰坐标:76°50′S 126°2′W / 76.833°S 126.033°W / -76.833; -126.033布德特峰(英语:Boudette Peaks)是南极洲的山峰,位于玛丽伯德地,处于拉夫里斯峰西南面2公里,属于执委山脉的
  • 1908年6月28日日食1908年6月28日日食是一次日环食,发生于1908年6月28日。新月当天(即朔日),地球上观测到月球和太阳的角距离极小,此时月球如果恰好在月球交点附近,穿过太阳和地球之间,与地球、太阳接
  • 1992年尼加拉瓜地震1992年尼加拉瓜地震是一场发生于1992年9月2日下午6时16分的地震,震中位于尼加拉瓜的近海区域,哥斯达黎加也有受到一定程度的破坏。地震造成至少116人遇难,另外还有多人受伤。本次地震发生在应力和变形的活跃区域,考虑到其实际面波震级和里氏震级,地震产生的海啸威力极大。本场地震是宽频地震台网捕捉到的首场海啸地震(英语:tsunami earthquake)。初次面波震级估计为7.2级。这是发生在科科斯板块和加勒比板块之间俯冲界面的一次缓慢的盲断层地震,该处是应力和变形的活跃区域。由于尼加拉瓜近海海底缺少
  • 施士洁施士洁(1853年-1922年),又名施士浩、原名龙文,字沄舫,号芸况,又号喆园,福建台湾人,与其父施琼芳为清代台湾仅有的父子进士。光绪二年(1876年)登丙子科进士,任内阁中书,后历任台湾彰化白沙书院、台湾府城(今台南)崇文书院、海东书院之山长:1。台湾割让给日本后内渡回西岑,后来于宣统三年(1911年)出任同安县马巷厅厅长,民国六年(1917年)至福州“闽省修志局”,民国十一年(1922年)于鼓浪屿去世:2。