> shannon | fano | entropy <
// Shannon-Fano —— 用於資料壓縮的自頂向下熵編碼
[ENTROPY]
基於熵的編碼
運用資訊理論建立高效的可變長前綴碼。
[TOP-DOWN]
自頂向下演算法
遞迴將符號分成兩組，讓兩組總機率盡量接近。
[HISTORIC]
經典歷史演算法
對現代壓縮演算法（例如 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 等更佳方法取代。現今主要作為歷史與教學示例，用來說明熵編碼、前綴碼以及資料壓縮的基本概念。