在数据压缩的领域里，香农-范诺编码（英語：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编码树是基于一个符号和对应频率的列表建立的。实际的算法很简单：
- 对于一个给定的符号列表，计算相应的概率或频率计数，用于判断每个符号的相对概率。
- 根据频率的符号列表排序，最常出现的符号在左边，最少出现的符号在右边。
- 将列表分为两部分，使左边部分的总频率和尽可能接近右边部分的总频率和。
- 该列表的左半边分配二进制数字0，右半边分配数字1。这意味着，在第一半符号编码都是将所有从0开始，第二半的编码都从1开始。
- 对左、右半部分递归应用步骤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提出了一个不同的算法，这个算法可以为任何的可能性提供出一个理想的树。香农-范诺编码是从树的根节点到叶子节点所进行的的编码，霍夫曼编码算法却是从相反的方向，暨从叶子节点到根节点的方向编码的。
- 为每个符号建立一个叶子节点，并加上其相应的发生频率
- 当有一个以上的节点存在时，进行下列循环：
- 把这些节点作为带权值的二叉树的根节点，左右子树为空
- 选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
- 把权值最小的两个根节点移除
- 将新的二叉树加入队列中。
- 最后剩下的节点暨为根节点，此时二叉树已经完成。
示例
用以上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.
外部链接 香农, 范诺编码, 在数据压缩的领域里, 英語, shannon, fano, coding, 是一种基于一组符号集及其出現的或然率, 估量或测量所得, 构建前缀码的技术, 其名稱来自于克劳德, 香农和罗伯特, 范诺, 在编码效率上, 它并不能与霍夫曼编码一样实现编码, code, word, 长度的最低期望, 然而, 与霍夫曼编码不同的是, 它确保了所有的编码长度在一个理想的理论范围, displaystyle, 之内, 这项技术是香农于1948年, 在他介绍信息理论的文章, 通信数学理论, 中提出的, 來源請求. 在数据压缩的领域里 香农 范诺编码 英語 Shannon Fano coding 是一种基于一组符号集及其出現的或然率 估量或测量所得 构建前缀码的技术 其名稱来自于克劳德 香农和罗伯特 范诺 在编码效率上 它并不能与霍夫曼编码一样实现编码 code word 长度的最低期望 然而 与霍夫曼编码不同的是 它确保了所有的编码长度在一个理想的理论范围 log P x displaystyle 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 香农 范诺算法就无法给出理想的编码 出于这个原因 香农 范诺编码几乎从不被使用 來源請求 目录 1 香农 范诺算法 1 1 示例 2 与霍夫曼算法的对比 2 1 示例 3 注释 4 参考 5 外部链接香农 范诺算法 编辑Shannon Fano编码树是基于一个符号和对应频率的列表建立的 实际的算法很简单 对于一个给定的符号列表 计算相应的概率或频率计数 用于判断每个符号的相对概率 根据频率的符号列表排序 最常出现的符号在左边 最少出现的符号在右边 将列表分为两部分 使左边部分的总频率和尽可能接近右边部分的总频率和 该列表的左半边分配二进制数字0 右半边分配数字1 这意味着 在第一半符号编码都是将所有从0开始 第二半的编码都从1开始 对左 右半部分递归应用步骤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的三位编码长度 最终的平均码字长度是 2 Bit 15 7 6 3 Bit 6 5 39 Symbol 2 28 Bits per Symbol displaystyle 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提出了一个不同的算法 这个算法可以为任何的可能性提供出一个理想的树 香农 范诺编码是从树的根节点到叶子节点所进行的的编码 霍夫曼编码算法却是从相反的方向 暨从叶子节点到根节点的方向编码的 为每个符号建立一个叶子节点 并加上其相应的发生频率 当有一个以上的节点存在时 进行下列循环 把这些节点作为带权值的二叉树的根节点 左右子树为空 选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树 且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和 把权值最小的两个根节点移除 将新的二叉树加入队列中 最后剩下的节点暨为根节点 此时二叉树已经完成 示例 编辑 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结果是 1 Bit 15 3 Bit 7 6 6 5 39 Symbol 2 23 Bits per Symbol displaystyle frac 1 text Bit cdot 15 3 text Bit cdot 7 6 6 5 39 text Symbol approx 2 23 text Bits per Symbol 注释 编辑 范诺 1949参考 编辑香农 克劳德 通信的数学理论 PDF 贝尔系统技术期刊 1948年7月 27 379 423 2011 11 20 原始内容存档 PDF 于1998 07 15 范诺 R M 信息传输 技术报告第65期 剑桥 马萨诸塞州 美国 麻省理工学院电子研究实验室 1949 外部链接 编辑香农 范诺二进制本质 香农 范诺的C算法 永久失效連結 取自 https zh wikipedia org w index php title 香农 范诺编码 amp oldid 66620903, 维基百科，wiki，书籍，书籍，图书馆，
文章
，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。