哈夫曼編碼

原理

設某信源産生有五種符号u1、u2、u3、u4和u5，對應概率P1=0．4，P2=0．1，P3=P4=0．2，P5=0．1。首先，将符号按照概率由大到小排隊，如圖所示。編碼時，從最小概率的兩個符号開始，可選其中一個支路為0，另一支路為1。這裡，我們選上支路為0，下支路為1。再将已編碼的兩支路的概率合并，并重新排隊。多次重複使用上述方法直至合并概率歸一時為止。

背景

哈夫曼壓縮是個無損的壓縮算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長度算法一族。意思是個體符号（例如，文本文件中的字符）用一個特定長度的位序列替代。因此，在文件中出現頻率高的符号，使用短的位序列，而那些很少出現的符号，則用較長的位序列。