前綴編碼

前綴編碼 是指對字元集進行編碼時，要求字元集中任一字元的編碼都不是其它字元的編碼的前綴，例如：設有abcd需要編碼表示（其中，a=0、b=10、c=110、d=11,則表示110的前綴可以是c或者da，不唯一）

前綴編碼構造方法

二叉樹：約定左分支表示字元‘0’，右分支表示字元‘1’，則可以用從根結點到葉子結點的路徑上的分支字元串作為該葉子結點字元的編碼。如此得到的編碼必是前綴編碼。

哈夫曼編碼

用構造哈夫曼樹的過程生成的二進制前綴編碼。哈夫曼樹是一類帶權路徑長度最短的樹。

特點：帶權路徑長度最短

套用（信息壓縮）

·ABFACGCAHGBBAACECDFGFAAEABBB

1.統計：A(8) B(6) C(4) D(1) E(2) F(3) G(3)H(1)

2.構造Huffman樹

3.得到Huffman編碼

A： 01

B： 11

C： 001

D：00000

E： 0001

F： 100

G： 101

H：00001

字元串新編碼長度：8*2+6*2+4*3+1*5+2*4+3*3+3*3+1*5=76