前綴碼、Huffman編碼算法：
前綴碼：給定一個序列的集合，若不存在一個序列是另一個序列的前綴，則該序列集合稱為前綴碼。
哈夫曼（Huffman）算法可用來設(shè)計前綴編碼，用該算法構(gòu)造一棵有n個葉子（每個葉子具有一個權(quán)值）的二叉樹的過程如下：
（1）根據(jù)n個權(quán)值{w1，w2，…，wn}構(gòu)成n棵二叉樹的集合F={T1，T2，…，Tn}，其中每棵二叉樹Ti中只有一個帶權(quán)為wi的根結(jié)點，其左右子樹均為空。
（2）在F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹來構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹結(jié)點的根結(jié)點的權(quán)值之和。
（3）在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中。
（4）重復(fù)（2）和（3），直到F中只含一棵樹時為止。稱這棵樹為最優(yōu)二叉樹（或哈夫曼樹）。
如果約定將每個結(jié)點的左分支表示字符“0”，右分支表示字符“1”，則可以把從根結(jié)點到某葉子結(jié)點的路徑上分支字符組成的字符串作為該葉子結(jié)點的編碼。
對于所有可能傳輸?shù)淖址蠲總€字符對應(yīng)一個葉結(jié)點，權(quán)值為其出現(xiàn)的頻率，那么根據(jù)哈夫曼算法構(gòu)造出二叉樹后，就得到了每個字符的二進(jìn)制編碼。
根據(jù)構(gòu)造過程可知，這種編碼方案得到的字符的編碼長度的數(shù)學(xué)期望值為最小，因此這種編碼方案是一個最優(yōu)前綴碼。在構(gòu)造過程中，每次都是選取兩棵最小權(quán)值的二叉樹進(jìn)行合并，作出的是貪心選擇。