01,10,000,0010,0011} 易见由一个正则2叉树只能产生唯一的二元前缀码 个二元前缀码中的码字有长有短,每个码字都可以代表某个符号,比如上述5个码字 可以分别代表字母A,B,C,D,E。当这些字母在文字中出现的频率不同时,用哪个码字代表 哪个字母,需要优化安排,因为不同的安排方案其效率是不同的(使用0,1符号的数量不同) 一个基本的想法是,尽可能用较短的码字代表使用频率较高的字母。这种使得0、1符号的 数量最为节省的二元前缀码安排称为最佳前缀码。最佳前缀码可通过最优2叉树得到 定义8.6.7设2叉树T有t片树叶v1,"2…,v,分别标有权W1,W2…,w,。称 为T的权,其中(v)是v的层数。在所有含t片叶子,带权W1,V2…,的2叉树中,权 最小的称为最优2叉树 例如,下图所示的3个树都是带权2,2,3,3,5的2叉树。它们的权分别为W(T1)=38 W(T2)=36,W(T3)=47 T 但这三棵2叉树都不是带权为2,2,3,3,5的最优二叉树。 求最优二叉树的算法- Huffman算法: 给定实数w1W2,…,w1,W1≤W2≤…≤w1 (1)连接权为w1,w2的两片树叶,得一个分支点(即非叶子顶点),其权为v1+w2 (2)在V1+W2,W3,…,w1中选出两个最小的权,连接它们对应的顶点,得到新的分支点及 其所带的权。 (3)重复(2),直到形成1-1个分支点,t片树叶为止。 例86.2求带权2,2,3,3,5的最优2叉树。 解:运用 Huffman算法,构造如下: 最终得到一棵最优2叉树,权为2×3+2×3+5×2+3×2+3×2=34。(注意权的一种简便计算方式 4+9+6+15=34)13 {01, 10, 000, 0010, 0011}。 易见由一个正则 2 叉树只能产生唯一的二元前缀码。 一个二元前缀码中的码字有长有短，每个码字都可以代表某个符号，比如上述 5 个码字 可以分别代表字母 A, B, C, D, E。当这些字母在文字中出现的频率不同时，用哪个码字代表 哪个字母，需要优化安排，因为不同的安排方案其效率是不同的(使用 0，1 符号的数量不同)。 一个基本的想法是，尽可能用较短的码字代表使用频率较高的字母。这种使得 0、1 符号的 数量最为节省的二元前缀码安排称为最佳前缀码。最佳前缀码可通过最优 2 叉树得到。 定义 8.6.7 设 2 叉树 T 有 t 片树叶 t v , v , , v 1 2 " ，分别标有权 w w wt , , , 1 2 " 。称 ∑= = t i i i W T w l v 1 ( ) ( ) 为 T 的权，其中 ( )i l v 是 i v 的层数。在所有含 t 片叶子，带权 w w wt , , , 1 2 " 的 2 叉树中，权 最小的称为最优 2 叉树。 例如，下图所示的 3 个树都是带权 2，2，3，3，5 的 2 叉树。它们的权分别为 W(T1)=38， W(T2)=36，W(T3)=47。 但这三棵 2 叉树都不是带权为 2，2，3，3，5 的最优二叉树。 z 求最优二叉树的算法－Huffman 算法： 给定实数 w w wt , , , 1 2 " ， w1 ≤ w2 ≤ " ≤ wt 。 (1) 连接权为 1 2 w ,w 的两片树叶，得一个分支点（即非叶子顶点），其权为 w1 + w2 ； (2) 在 w1 + w2 w wt , , , 3 " 中选出两个最小的权，连接它们对应的顶点，得到新的分支点及 其所带的权。 (3) 重复（2），直到形成 t－1 个分支点，t 片树叶为止。 例 8.6.2 求带权 2，2，3，3，5 的最优 2 叉树。 解：运用 Huffman 算法，构造如下： 最终得到一棵最优 2 叉树，权为 2×3+2×3+5×2+3×2+3×2=34。（注意权的一种简便计算方式： 4+9+6+15 = 34）。 2 2 4 2 2 4 3 3 6 2 2 4 3 3 6 5 9 2 2 4 3 3 6 5 9 15 5 2 3 3 2 3 3 5 2 2 T T3 T1 2 3 2 3 5 2