香農-范諾編碼
維基百科,自由的 encyclopedia
在數據壓縮的領域裏,香農-范諾編碼(英語: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},香農-范諾算法就無法給出理想的編碼。出於這個原因,香農-范諾編碼幾乎從不被使用。[來源請求]