霍夫曼樹是壹種二叉樹,每個葉子結點代表壹個符號,它的權值是該符號在符號序列中出現的概率。每個非葉子結點的權值是它的左右兒子的權值之和。霍夫曼樹的構建方式是:對所有符號的權值進行排序,每次取出權值最小的兩個符號,把它們構成壹個新的結點,這個新結點的權值就是這兩個結點權值之和。然後再把這個新結點加入排序序列,直到只剩下壹個結點,這就是霍夫曼樹。
霍夫曼編碼就是利用這棵樹進行編碼的過程。對於每個符號,我們從根結點到葉子結點路徑上的每壹個結點的左右兒子都對應壹個二進制位,左兒子對應0,右兒子對應1。編碼就是按照這樣的方法得到的二進制序列,可以知道霍夫曼編碼的符號碼長都是不同的,且符號出現的概率越大,其編碼的碼長越短,這使得它有更高的壓縮率。
霍夫曼解碼就是根據霍夫曼樹,根據二進制碼找到對應的葉子結點並得到原符號的過程。
總之霍夫曼編碼是在編碼過程中基於符號出現的概率,將符號進行編碼,使得出現概率大的符號編碼長度短,出現概率小的符號編碼長度長。這樣就可以達到壓縮數據的目的。而霍夫曼解碼就是根據霍夫曼樹還原出編碼前的符號。