香農-法諾編碼
在數據壓縮的領域裡,香農-法諾編碼(英語:Shannon–Fano coding)是一種基於一組符號集及其出現的或然率(估量或測量所得)構建前綴碼的技術。其名稱來自於克勞德·香農和羅伯特·法諾。在編碼效率上,它並不能與霍夫曼編碼一樣實現編碼(code word)長度的最低期望;然而,與霍夫曼編碼不同的是,它確保了所有的編碼長度在一個理想的理論範圍之內。這項技術是香農於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的三位編碼長度,最終的平均碼字長度是
與霍夫曼算法的對比
編輯香農-法諾編碼算法並非總能得到最優編碼。1952年, David A. Huffman提出了一個不同的算法,這個算法可以為任何的可能性提供出一個理想的樹。香農-法諾編碼是從樹的根節點到葉子節點所進行的的編碼,霍夫曼編碼算法卻是從相反的方向,暨從葉子節點到根節點的方向編碼的。
- 為每個符號建立一個葉子節點,並加上其相應的發生頻率
- 當有一個以上的節點存在時,進行下列循環:
- 把這些節點作為帶權值的二元樹的根節點,左右子樹為空
- 選擇兩棵根結點權值最小的樹作為左右子樹構造一棵新的二元樹,且至新的二元樹的根結點的權值為其左右子樹上根結點的權值之和。
- 把權值最小的兩個根節點移除
- 將新的二元樹加入隊列中。
- 最後剩下的節點暨為根節點,此時二元樹已經完成。
示例
編輯用以上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
結果是