香农-范诺编码

维基百科,自由的百科全书
跳转至: 导航搜索

数据压缩的领域里,以克劳德·香农范诺-罗伯特命名的 香农-范诺编码是一种基于一组符号集及其或然率(估量或测量所得),从而构建前缀码的技术。在理想意义上, 它与哈夫曼编码一样,并未实现码词(code word)长度的最低预期;然而,与哈夫曼编码不同的是,它确保了所有的码词长度在一个理想的理论范围{-\log}  P(x)之内。这项技术是香农于1948年,在他介绍信息理论的文章“通信数学理论”中被提出的。这个方法归功于范诺,他在不久以后以技术报告发布了它。[1] 香农-范诺编码不应该与香农编码混淆,后者的编码方法用于证明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的编码的一个例子。

出于这个原因,香农 - 范诺几乎从不使用; 哈夫曼编码几乎是计算简单,生产总是达到预期最低的码字长度的制约下,每个符号是由一个整数组成一个代码代表的前缀码。这往往是不必要的,因为代码将装在首尾相连的长序列的里。如果我们认为一次的代码组,象征符号的哈夫曼编码是唯一的最佳符号的概率统计独立|独立和一些半功率,即,为\textstyle \frac{1}{2^n}。在大多数情况下,[算术编码]可以产生比哈夫曼或的香农-范诺更大的整体压缩,因为它可以在小数位编码,这更接近实际的符号信息内容。然而,算术编码并没有取代像霍夫曼取代的香农-范诺一样取代哈夫曼,一方面是因为算术编码的计算成本的方式,因为它是由多个专利覆盖。香农:范诺编码 被用在爆聚压缩方法.[2]

香农-范诺 算法[编辑]

Shannon-Fano的树是根据旨在定义一个有效的代码表的规范而建立的。实际的算法很简单:

  1. 对于一个给定的符号列表,制定了概率相应的列表或频率计数,使每个符号的相对发生频率是已知。
  2. 排序根据频率的符号列表,最常出现的符号在左边,最少出现的符号在右边。
  3. 清单分为两部分,使左边部分的总频率和尽可能接近右边部分的总频率和。
  4. 该列表的左半边分配二进制数字0,右半边是分配的数字1。这意味着,在第一半符号代都是将所有从0开始,第二半的代码都从1开始。
  5. 对左、右半部分递归应用步骤3和4,细分群体,并添加位的代码,直到每个符号已成为一个相应的代码树的叶。

示例[编辑]

香农-范诺编码算法

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

符号 A B C D E
计数 15 7 6 6 5
概率 0.38461538 0.17948718 0.15384615 0.15384615 0.12820513

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

符号 A B C D E
编码 00 01 10 110 111

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

\frac{2\,\text{Bit}\cdot(15+7+6) + 3\,\text{Bit} \cdot (6+5)}{39\, \text{Symbol}} \approx 

2.28\,\text{Bits per Symbol.}

哈夫曼算法[编辑]

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

  1. 为每个符号建立一个叶子节点,并加上其相应的发生频率
  2. 当有一个以上的节点存在时,进行下列循环:
    1. 把这些节点作为带权值的二叉树的根节点,左右子树为空
    2. 选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
    3. 把权值最小的两个根节点移除
    4. 将新的二叉树加入队列中.
  3. 最后剩下的节点暨为根节点,此时二叉树已经完成。

示例[编辑]

Huffman Algorithm

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

符号 A B C D E
计数 15 7 6 6 5
概率 0.38461538 0.17948718 0.15384615 0.15384615 0.12820513

在这种情况下,D,E的最低频率和分配分别为0和1,分组结合概率的0.28205128。现在最低的一双是B和C,所以他们就分配0和1组合结合概率的0.33333333在一起。这使得BC和DE所以0和1的前面加上他们的代码和它们结合的概率最低。然后离开只是一个和BCDE,其中有前缀分别为0和1,然后结合。这使我们与一个单一的节点,我们的算法是完整的。

这次A代码的代码长度是1比特,其余字符是3比特。

字符 A B C D E
代码 0 100 101 110 111

结果是

\frac{1\,\text{Bit}\cdot 15 + 3\,\text{Bit} \cdot (7+6+6+5)}{39\, \text{Symbol}} \approx 

2.23\,\text{Bits per Symbol.}

注释[编辑]

  1. ^ 范诺 1949
  2. ^ APPNOTE.TXT - .压缩文件格式说明. PKWARE股份有限公司. 2007-09-28 [2008-01-06]. "爆聚算法实际上是两个不同的算法相结合。第一种算法压缩重复使用的字节序列 滑动字典。第二种算法是用来压缩的滑动字典输出的编码,使用多个的Shannon - Fano的树木。" 

参考[编辑]

  • 香农, 克劳德. 通信的数学理论. 贝尔系统技术期刊. 1948, 27: 379–423.  已忽略文本“ month 7月” (帮助)
  • 范诺, R.M. 信息传输. 技术报告第65期 (剑桥(马萨诸塞州),美国: 麻省理工学院电子研究实验室). 1949. 

外部链接[编辑]