转自：https://blog.csdn.net/liupeip_vipl/article/details/54762257
和 Huffman-Tree 一样，Shannon-Fano coding 也是用一棵二叉树对字符进行编码。但在实际操作中呢，Shannon-Fano 却没有大用处，这是由于它与 Huffman coding 相比，编码效率较低的结果（或者说香农-范诺算法的编码平均码字较大）。但是它的基本思路我们还是可以参考下的。
Shannon-Fano 的树是根据旨在定义一个有效的代码表的规范而建立的。实际的算法很简单：
- 对于一个给定的符号列表，制定了概率相应的列表或频率计数，使每个符号的相对发生频率是已知。
- 排序根据频率的符号列表，最常出现的符号在左边，最少出现的符号在右边。
- 清单分为两部分，使左边部分的总频率和尽可能接近右边部分的总频率和。
- 该列表的左半边分配二进制数字 0，右半边是分配的数字 1。这意味着，在第一半符号代都是将所有从 0 开始，第二半的代码都从 1 开始。
- 对左、右半部分递归应用步骤 3 和 4，细分群体，并添加位的代码，直到每个符号已成为一个相应的代码树的叶。