利用最优二叉树可求得最佳前缀码。 例863在某种通信中,使用八进制数字串。各个数字出现的频率如下 (1)求传输它们的最佳前缀码。(2)问传输10″个按上述比例出现的八进制数字需要多少 个二进制数字?(3)如果用等长码字(长为3)传输10″个按上述比例出现的八进制数字, 需要多少个二进制数字? 解:用100乘以各个数字出现的频率作为权,将权由小到大排列:w=5,w1=5,w2=10,w3=10, 4=10,ws=15,w6=20,w=25,(记住它们对应哪个数字)。用 Huffman算法求出最优2叉树 如下: 501100 no1 000onl cool 由此获得前缀码{01,1,001,100,101,0001,00000},且各码字对应传输数字为 01传0;11传1:001传2:100传3;101传4;0001传5:00000传6;00001传7。 由2叉树的最优性可知所得前缀码{01,11,001,100,101,0001,00000是最佳的。 用所得前缀码按题中给定频率发送100个八进制数字所用的二进制数字的个数为: 1005×5%5×5%+4x10%+3×15%+3×10%+3×10%2×25%+2×20%)=285 故传输10个按上述频率出现的八进制数字需要285×10=285×10-2个二进制数字。 若用等长码字{000,001,010,011,100,101,110,111}传输10″个按上述频率出现的八进 制数字需要3×10″个二进制数字。 注:(1)最优2叉树权的另一种计算方式W(T=10+20+35+20+60+40+100=285。 (2)最佳前缀码并不唯一。由于每一步选择两个最小权的选法不同,且两个权对应的顶 点所放左右位置不同,得到的最优树可能不同,由此可能得到不同的最佳前缀码, 例如,如下2叉树也是一棵最优树,权为10+20+20+35+40+60+100=285,由此最优树 给出的前缀码也是满足上例要求的最佳前缀码。 0000 00010000] oo114 利用最优二叉树可求得最佳前缀码。 例 8.6.3 在某种通信中，使用八进制数字串。各个数字出现的频率如下： 0：25%； 1：20%； 2：15%； 3：10%； 4：10%；5：10%； 6：5%； 7：5%。 （1）求传输它们的最佳前缀码。（2）问传输 10n 个按上述比例出现的八进制数字需要多少 个二进制数字？（3）如果用等长码字 （长为 3）传输 10n 个按上述比例出现的八进制数字， 需要多少个二进制数字？ 解：用 100 乘以各个数字出现的频率作为权，将权由小到大排列：w0=5, w1=5, w2=10, w3=10, w4=10, w5=15, w6=20, w7=25, （记住它们对应哪个数字）。用 Huffman 算法求出最优 2 叉树 如下： 由此获得前缀码{01, 11, 001, 100, 101, 0001, 00000, 00001}，且各码字对应传输数字为： 01 传 0；11 传 1；001 传 2；100 传 3；101 传 4；0001 传 5；00000 传 6；00001 传 7。 由 2 叉树的最优性可知所得前缀码{01, 11, 001, 100, 101, 0001, 00000, 00001}是最佳的。 用所得前缀码按题中给定频率发送 100 个八进制数字所用的二进制数字的个数为： 100(5×5%+5×5%+4×10%+3×15%+3×10%+3×10%+2×25%+2×20%)=285。 故传输 10n 个按上述频率出现的八进制数字需要 285×10n =2.85×10n −2 个二进制数字。 若用等长码字{000, 001, 010, 011, 100, 101, 110, 111}传输 10 n 个按上述频率出现的八进 制数字需要 3×10 n 个二进制数字。 注：（1）最优 2 叉树权的另一种计算方式 W(T)=10+20+35+20+60+40+100=285。 （2）最佳前缀码并不唯一。由于每一步选择两个最小权的选法不同，且两个权对应的顶 点所放左右位置不同，得到的最优树可能不同，由此可能得到不同的最佳前缀码。 例如，如下 2 叉树也是一棵最优树，权为 10+20+20+35+40+60+100=285，由此最优树 给出的前缀码也是满足上例要求的最佳前缀码。 0 0 1 0 1 1 1 0 0 01 00000 001 0001 1 0 1 0 1 100 60 40 25 20 20 35 15 10 10 20 10 10 5 5 00001 100 101 11 1 35 0 0 0 1 0 1 0 1 0 01 0000 0001 1000 1 0 1 1 100 40 60 20 25 20 20 15 10 10 5 5 10 10 001 1001 101 11