跳转到内容

香农-法诺编码

维基百科,自由的百科全书

数据压缩的领域里,香农-法诺编码(英語:Shannon–Fano coding)是一种基于一组符号集及其出現的或然率(估量或测量所得)构建前缀码的技术。其名稱来自于克劳德·香农羅伯特·法諾。在编码效率上,它并不能与霍夫曼编码一样实现编码(code word)长度的最低期望;然而,与霍夫曼编码不同的是,它确保了所有的编码长度在一个理想的理论范围之内。这项技术是香农于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编码树是基于一个符号和对应频率的列表建立的。实际的算法很简单:

  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的三位编码长度,最终的平均码字长度是

与霍夫曼算法的对比

[编辑]

香农-法诺编码算法并非总能得到最优编码。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合并,它们频率和为11(图a至图b)。接下来概率最低的一组是B(7)和C(6),所以将他们作为左右子树组成新的根结点BC。在剩下的三个节点中,BC(13)和DE(11)的频率和最低,因此组成新的二叉树BE。最后将仅剩的两个节点合并,并分别为它们分配前缀0和1。这样所有的节点都成为了唯一一个编码树的叶节点。

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

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

结果是

注释

[编辑]

参考

[编辑]
  • 香农, 克劳德. 通信的数学理论 (PDF). 贝尔系统技术期刊. 1948年7月, 27: 379–423 [2011-11-20]. (原始内容存档 (PDF)于1998-07-15). 页面存档备份,存于互联网档案馆
  • 法诺, R.M. 信息传输. 技术报告第65期 (剑桥(马萨诸塞州),美国: 麻省理工学院电子研究实验室). 1949. 

外部链接

[编辑]