香农-范诺编码

✍ dations ◷ 2025-09-18 09:49:42 #香农-范诺编码

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

结果是

相关

  • 磷脂双分子层磷脂双分子层(英语:lipid bilayer 或phospholipid bilayer)是由两层磷脂分子组成的薄膜。 几乎所有细胞生物的细胞膜和许多病毒的包膜都主要由磷脂双分子层构成,此外,核被膜和
  • 边界在字体排印学中,边界指的是某页文件中四周留白的部分,可方便辨认行的起点和终点。当文字是以左右对齐排列时,其会贴紧左侧和右侧的边界。在多数的文书处理软件中,边界的标准宽度
  • 自闭症谱系障碍自闭症谱系(英语:Autism spectrum)是一种心理状况的谱系障碍,亦称自闭症谱系障碍(英语:autism spectrum disorders,简写ASD;或autism spectrum conditions,简写ASC)或泛自闭症障碍,描述
  • 肯亚总统肯亚共和国总统 (斯瓦希里语:Rais wa Jamhuri ya Kenya)为肯尼亚的国家元首及政府首脑,总统为肯亚政府(英语:Government of Kenya)行政机构领导人及肯亚军事统帅,官邸为内罗毕的St
  • W-玻色子W-玻色子(W-boson)是种向量玻色子,分 W+、W- 两类,互为反粒子,是弱相互作用: f α
  • 水浒笑传1《水浒笑传》(英语:),1993年上映的剧情片和喜剧片,导演高志森,主演许冠英、许冠杰、毛舜筠、吴孟达、沈殿霞、黄霑、吴志雄、黄光亮、黄百鸣。改编自明朝施耐庵《水浒传》当中武松
  • 朱安㶠堵阳荣宪王朱安㶠(1479年-1534年),明朝周藩堵阳王府镇国将军,追封堵阳王,为堵阳安僖王朱同鉣的庶长子。成化二十一年(1485年)闰四月,获赐名安㶠。朱安㶠初封镇国将军,于弘治十一年(1498
  • 辛格尔顿界在 编码理论 中, 以 Singleton 命名的 Singleton 界 是一个关于分组码容量的粗略估计。下面约定分组码 C {\displaystyle C} 的 MDS 码
  • 拓凯实业拓凯实业股份有限公司是创立于1980年的台湾碳纤维复合材料制造商,创办人暨董事长为沈文振。产品包括网球拍、安全帽、自行车架和航太材料,其生产的网球拍、飞机椅背、自行车架
  • 杨巨源 (唐朝)杨巨源(?年-?年),字景山,后改名巨济。河中(治所在今山西省永济市)人,唐朝官员。贞元五年(789年)进士。早年担任张弘靖的从事,后来由秘书郎擢拔为太常博士,再迁虞部员外郎。出京担任凤翔少尹。长庆三年(823年)转为国子司业,隔年以国子祭酒致仕。大和七年(833年)尚在世。工于诗,与白居易、元稹、刘禹锡、王建等交好。有集一卷。《全唐诗》卷三百三十三录其诗。杨巨源的诗作在其生前享有盛名,且很早就流传至外国。当时,巨源被评为“诗名往日动长安,首首人家卷里看。”元稹称其“诗律铿金,词锋切玉”,元和年间敕撰《御