查看“︁香农-法诺编码”︁的源代码

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

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

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

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

#对于一个给定的符号列表，计算相应的[[概率]]或频率计数，用于判断每个符号的相对概率。
#根据频率的符号列表排序，最常出现的符号在左边，最少出现的符号在右边。
#将列表分为两部分，使左边部分的总频率和尽可能接近右边部分的总频率和。
#该列表的左半边分配二进制数字0，右半边分配数字1。这意味着，在第一半符号编码都是将所有从0开始，第二半的编码都从1开始。
#对左、右半部分递归应用步骤3和4，并添加编码的位数，直到每个符号都成为一个相应的编码树的叶节点。

===示例===
[[File:ShannonCodeAlg.svg|thumb|300px|香农-法诺编码算法]]
这个例子展示了一组字母的香农编码结构（如图a所示）这五个可被编码的字母有如下出现次数：
:{| class="wikitable" 
! 符号
! 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。经过四次分割，得到了一个树形编码。如下表所示，在最终得到的树中，拥有最大频率的符号被两位编码，其他两个频率较低的符号被三位编码。

:{| class="wikitable"
! 符号
! A 
! B 
! C 
! D 
! E
|- 
| 编码
| 00 
| 01 
| 10 
| 110 
| 111
|}

根据A，B，C两位编码长度，D，E的三位编码长度，最终的平均码字长度是
:<math>\frac{2\,\text{Bit}\cdot(15+7+6) + 3\,\text{Bit} \cdot(6+5)}{39\, \text{Symbol}} \approx 

2.28\,\text{Bits per Symbol.}</math>

==与霍夫曼算法的对比==
<!-- 是否应该删除这一整段？ -->香农-法诺编码算法并非总能得到最优编码。1952年, David A. Huffman提出了一个不同的算法，这个算法可以为任何的可能性提供出一个理想的树。香农-法诺编码是从树的根节点到叶子节点所进行的的编码，霍夫曼编码算法却是从相反的方向，暨从叶子节点到根节点的方向编码的。 
# 为每个符号建立一个叶子节点，并加上其相应的发生频率
# 当有一个以上的节点存在时，进行下列循环：
## 把这些节点作为带权值的二叉树的根节点，左右子树为空
## 选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
## 把权值最小的两个根节点移除
## 将新的二叉树加入队列中。
# 最后剩下的节点暨为根节点，此时二叉树已经完成。

===示例===
[[File:HuffmanCodeAlg.png|thumb|300px|Huffman Algorithm]]

用以上Shannon - Fano例子所使用的分析，即：
:{| class="wikitable" 
! 符号
! 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比特。
:{| class="wikitable"
! 字符
! A 
! B 
! C 
! D 
! E
|- 
| 代码
| 0
| 100 
| 101 
| 110 
| 111
|}

结果是

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

2.23\,\text{Bits per Symbol.}</math>

==注释==
{{reflist}}

==参考==
* {{cite journal | first = 克劳德 | last = 香农 | url = http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf | title = 通信的数学理论 | journal = 贝尔系统技术期刊 | volume = 27 | pages = 379–423 | date = 1948年7月 | access-date = 2011-11-20 | archive-date = 1998-07-15 | archive-url = https://web.archive.org/web/19980715013250/http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf | dead-url = no }} {{Wayback|url=http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf |date=19980715013250 }}
* {{cite journal | first = R.M. | last = 法诺 | title = 信息传输 | work = 技术报告第65期 | year = 1949
|publisher = 麻省理工学院电子研究实验室 | location =剑桥（马萨诸塞州），美国 | ref =harv}}

==外部链接==
*[https://web.archive.org/web/20070821221604/http://www.binaryessence.com/dct/en000041.htm 香农-法诺二进制本质]
*[https://github.com/Ignotus/shannon-fano 香农-法诺的C算法]{{dead link|date=2018年5月 |bot=InternetArchiveBot |fix-attempted=yes }}

{{压缩方法}}

[[Category:无损压缩算法|X]]