勵志

勵志人生知識庫

霍曼夫編碼

霍夫曼編碼(Huffman Coding),又譯為哈夫曼編碼或赫夫曼編碼,是一種用於無損數據壓縮的熵編碼算法,由大衛·霍夫曼在1952年發明。這種編碼方法利用了變長編碼表對源符號(如檔案中的一個字母)進行編碼,其中變長編碼表是通過評估來源符號出現機率的方法得到的,出現機率高的字母使用較短的編碼,反之出現機率低的則使用較長的編碼,從而使編碼之後的字元串的平均長度、期望值降低,達到無損壓縮數據的目的。

霍夫曼編碼的核心思想是構建一棵霍夫曼樹,首先統計待壓縮的數據中每個字元出現的頻率,然後根據頻率構建霍夫曼樹,其中頻率較高的字元位於較短的路徑上,頻率較低的字元位於較長的路徑上,最後根據霍夫曼樹生成每個字元對應的編碼。

霍夫曼樹是一種帶權路徑長度最短的二叉樹,其帶權路徑長度是樹中所有葉結點的權值乘上其到根結點的路徑長度之和,霍夫曼編碼的壓縮率通常在20%至90%之間。