> shannon | fano | entropy <
// Shannon-Fano —— 用于数据压缩的自顶向下熵编码
基于熵的编码
使用信息论构造高效的可变长度前缀码。
自顶向下算法
递归地按概率将符号划分为两组，接近等概率。
经典历史算法
对现代压缩算法（如 Huffman）有重要启发作用。
>> 技术细节
Shannon-Fano 的工作原理:
Shannon-Fano 编码先根据频率对符号排序，然后将其递归地拆分为两组，使两组的总概率尽量接近。每一次拆分都会在码字后追加一位（左组为 0，右组为 1），最终得到一组前缀无歧义的可变长编码。
编码过程示例:
文本: "AAABBCD" 频率: A:3, B:2, C:1, D:1 拆分: [A] | [B,C,D] 码字: A: 0 B: 10 C: 110 D: 111 编码结果: 0 0 0 10 10 110 111
为什么使用 Shannon-Fano:
- >实现简单，适合教学与实验
- >具备不错的压缩率
- >有重要的历史与理论价值
- >帮助理解熵编码与前缀码
- >适合作为 Huffman 之前的过渡概念
>> 常见问题
什么是 Shannon-Fano 编码？
Shannon-Fano 编码是一种基于熵的编码技术，由 Claude Shannon 和 Robert Fano 在 20 世纪 40 年代提出。它是最早使用“按概率分配可变长码字”的算法之一。
Shannon-Fano 和 Huffman 有什么区别？
两者都生成可变长编码，但 Huffman 编码在平均码长上是最优的，而 Shannon-Fano 更简单，结构上接近直观的“按概率二分”。实践中通常采用 Huffman，但学习 Shannon-Fano 有助于理解 Huffman 的设计思想。
符号是如何被拆分的？
首先按频率对符号排序，然后按总概率将它们划分为两组，使两组概率尽量接近。之后对每一组重复该过程，直到每组只剩一个符号为止。
Shannon-Fano 现在还在用吗？
在实际工程中，Shannon-Fano 已几乎完全被 Huffman 编码等更优方法取代。现在它主要作为历史与教学示例，用来解释熵编码、前缀码和数据压缩的核心概念。
// 计算示例
| Symbol | Freq | Code | Bits |
|---|---|---|---|
| A | 15 | 00 | 2 |
| B | 7 | 01 | 2 |
| C | 6 | 10 | 2 |
| D | 6 | 110 | 3 |
| E | 5 | 111 | 3 |
// 代码示例
Frequencies A=15 B=7 C=6 D=6 E=5 (39 symbols)
1. Sort symbols by frequency (descending).
2. Split the list where the two halves' totals are closest:
{A,B}=22 | {C,D,E}=17 -> first bit 0 / 1
3. Recurse on each half until single symbols remain:
{A}|{B} -> 00, 01 {C}|{D,E} -> 10, 11.. then {D}|{E} -> 110, 111
Total 15*2 + 7*2 + 6*2 + 6*3 + 5*3 = 89 bits
Huffman on the same data: A=1 bit, others 3 bits -> 87 bits
>> 更多问题
问：Shannon-Fano 与哈夫曼编码有何不同？
答：Shannon-Fano 自上而下，把排序后的符号表分成频率总和尽量接近的两半；哈夫曼则自下而上，不断合并最稀有的符号。哈夫曼被证明是最优的，Shannon-Fano 则不一定。
问：Shannon-Fano 总是最优吗？
答：不是。示例中它需要 89 位，而哈夫曼只需 87 位。两者都产生前缀码，但 Shannon-Fano 的划分规则可能选出不利的切分。
问：Shannon-Fano 用在哪里？
答：主要作为历史与教学方法（Claude Shannon 与 Robert Fano，1948/49 年）。ZIP 的 IMPLODE 算法中有其变体；现代压缩器多用哈夫曼或算术编码。