香農-法諾編碼

在數據壓縮的領域裏，香農-法諾編碼（英語：Shannon–Fano coding）是一種基於一組符號集及其出現的或然率（估量或測量所得）構建前綴碼的技術。其名稱來自於克勞德·香農和羅伯特·法諾。在編碼效率上，它並不能與霍夫曼編碼一樣實現編碼（code word）長度的最低期望；然而，與霍夫曼編碼不同的是，它確保了所有的編碼長度在一個理想的理論範圍 ${-\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}，香農-法諾算法就無法給出理想的編碼。出於這個原因，香農-法諾編碼幾乎從不被使用。^{[來源請求]}

香農-法諾算法

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的三位編碼長度，最終的平均碼字長度是

{\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提出了一個不同的算法，這個算法可以為任何的可能性提供出一個理想的樹。香農-法諾編碼是從樹的根節點到葉子節點所進行的的編碼，霍夫曼編碼算法卻是從相反的方向，暨從葉子節點到根節點的方向編碼的。

為每個符號建立一個葉子節點，並加上其相應的發生頻率
當有一個以上的節點存在時，進行下列循環：
1. 把這些節點作為帶權值的二叉樹的根節點，左右子樹為空
2. 選擇兩棵根結點權值最小的樹作為左右子樹構造一棵新的二叉樹，且至新的二叉樹的根結點的權值為其左右子樹上根結點的權值之和。
3. 把權值最小的兩個根節點移除
4. 將新的二叉樹加入隊列中。
最後剩下的節點暨為根節點，此時二叉樹已經完成。

示例

用以上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

結果是

{\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.

外部連結

[1] 法諾 1949

[1]