> 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 演算法中有其變體；現代壓縮器多用霍夫曼或算術編碼。