回覆列表
-
1 # 屠蘇叔叔
-
2 # 資深老饕ysy
1.若要設計長短不等的編碼,則其中的任意一個字元的編碼都必須不是另一個字元的編碼的字首,這種編碼稱為字首編碼。
2.判斷一個編碼是不是字首編碼,可以根據定義,即看每個字元的編碼是不是和其他字元編碼的前邊的數字一樣。
3.我們要挨個判斷每個字元,從A開始。A的編碼為0,只有一個數字。那麼在B,C,D的編碼中從前往後看一個數字分為1,1,1。1不等於0。則A的編碼符合字首編碼要求。
4.然後判斷B的編碼是否是其他字母的編碼的字首。B的編碼10明顯不是C,D編碼的字首,所以B的編碼符合字首編碼要求。
5.接下來判斷C的編碼。C編碼為110,明顯不是一位編碼和兩位編碼的字首。對於D編碼111來說,從前到後並不包含110。所以C的編碼符合字首編碼要求。
6.最後判斷D的編碼。同理,C編碼從左數的頭三個數字都不等於111,那兩個連位數都不夠的編碼就更甭提了。所以D的編碼符合字首編碼要求。最終,這四個編碼屬於字首編碼。
字首編碼:是指對字符集進行編碼時,要求字符集中任一字元的編碼都不是其它字元的編碼的字首。
擴充套件資料字首編碼 是指對字符集進行編碼時,要求字符集中任一字元的編碼都不是其它字元的編碼的字首,例如:設有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