复旦大学：《离散数学》PPT教学课件（赵一鸣）17/28

5.6 Prefix codes and optimal tree Definition 31: Codes with this property which the bit string for a letter never occurs as the first part of the bit string for another letter are called prefix codes. Theorem 5.21: We can construct a prefix code from any binary tree, and we can construct a binary tree from the prefix codes. Proof: (1)We can construct a prefix code from any binary tree where the left edge at each internal vertex is la beled by o and the right edge by a l and where the leaves are labeled by characters (2)We can construct a binary tree from the prefix codes

5.6 Prefix codes and optimal tree Definition 31: Codes with this property which the bit string for a letter never occurs as the first part of the bit string for another letter are called prefix codes. Theorem 5.21: We can construct a prefix code from any binary tree, and we can construct a binary tree from the prefix codes. Proof: (1) We can construct a prefix code from any binary tree where the left edge at each internal vertex is labeled by 0 and the right edge by a 1 and where the leaves are labeled by characters (2)We can construct a binary tree from the prefix codes

字母 频率003560.0139002790.03780.13040.02890.01990.05280.06270.00130.0420.03900249 字母 频率00070.07970.01994000200670.06070.1050.02490.00210.01490007001990.008

字 母 a b c d e f g h i j k l m 频 率 0.0356 0.0139 0.0279 0.0378 0.1304 0.0289 0.0199 0.0528 0.0627 0.0013 0.042 0.0339 0.0249 字 母 n o p q r s t u V w x y z 频 率 0.0707 0.0797 0.0199 0.0012 0.0677 0.0607 0.1045 0.0249 0.0092 0.0149 0.0017 0.0199 0.0008

Definition 32: Let t be a tree with weigths wi sw2s.wl, where li is the path length from the root to vertex i. Say that a binary tree t is optimal if w(T) has its minimum value over all possible trees with the same set of leaf nodes

Definition 32: Let T be a tree with weigths w1w2...wn at its leaf nodes. The weighted leaf path length w(T) of T is W(T)=  = n i i i w l 1 , where li is the path length from the root to vertex i. Say that a binary tree T is optimal if w(T) has its minimum value over all possible trees with the same set of leaf nodes

Example: Let t be a binary tree with weigths 3, 5, 7, 9 a)∑l=48 b)∑w1=47

Example: Let T be a binary tree with weigths 3, 5, 7, 9 a ) = 48, i i w l b)  = 47, i i w l

Huffman algorithm Let aj,a2,..., an be n vertex with weight W1, W2,..., wn and w1≤W2S.W F: -forest of n rooted tree each consisting of the single vertex a i with weight w, for i=1, 2,.n. While f is not a tree Begin Replace the rooted trees t and t'of least weights from F with w(T)2 wT)with a tree having a new root that has tas its left subtree and t'as its right subtree Assign w(t)+wt as the weight of the new tree. en d w1+w2 2

▪ Huffman algorithm: ▪ Let a1 ,a2 ,,an be n vertex with weight w1 ,w2 ,,wn and w1w2wn。 ▪ F:=forest of n rooted tree each consisting of the single vertex ai with weight wi for i=1,2,...n. ▪ While F is not a tree ▪ Begin ▪ Replace the rooted trees T and T’ of least weights from F with w(T)≥ w(T’) with a tree having a new root that has T as its left subtree and T’ as its right subtree. Assign w(T)+w(T’) as the weight of the new tree. ▪ end

w(T)=2÷4+424+7÷3+ 122+8÷2+10*2=105 22s 7 28 22 20 10 4

w(T)=2*4+4*4+7*3+ 12*2+8*2+10*2=105

Theorem 5.22 Let t be built according to Huffman algorithm and leaves of T with weight W1,W2,.,w Then T is an optimal tree(Where w,sw2<w3 s. <wk). Proof: Let us apply induction on the number n of vertices The results holds Suppose that result holds for n=k-1 For n=k, By the inductive hypothesis Suppose that nodes in an optimal tree T have weights W1+W2, W3,..., WK. Then This is an optimal tree with weight W1,W2, W3,.,Wk ifTs leaf with weight w1+W2 is replaced by subtree w1+w2

▪ Theorem 5.22: Let T be built according to Huffman algorithm and leaves of T with weight w1 ,w2 ,,wn . Then T is an optimal tree (Where w1w2w3 wk ). ▪ Proof: Let us apply induction on the number n of vertices. ▪ n=2, The results holds Suppose that result holds for n=k-1 For n=k， By the inductive hypothesis, Suppose that nodes in an optimal tree T have weights w1+w2 ,w3 ,,wk . Then This is an optimal tree with weight w1 ,w2 ,w3 ,,wk if T’s leaf with weight w1+w2 is replaced by subtree

Lemma 5.1 Let T be an optimal tree with weights W1≤w,≤W2≤.≤ W. Then there is an optimal tree t, so that T2s two vertices with weights w, and w2 are brother nodes. Proof: Let T be an optimal tree with weights W1≤W≤W2≤.≤W The two weights wa Wb are on lowest level and they are brothers. We denoted by v. and vh. let vo be the father of 2b Wa≥W1,Wb2W2 Let la be the length of the path from root to va, and lb be the length of the path from root to vh b We obtain a new tree T2 by exchanging from leaf v, to v and from leafy, to v w(T1)-w(T2)=(WaW1)(2-1)+(Wb-W2)(l2-l2)20

▪ Lemma 5.1 Let T1 be an optimal tree with weights w1w2w3 wk . Then there is an optimal tree T2 so that T2 ’s two vertices with weights w1 and w2 are brother nodes. ▪ Proof: Let T1 be an optimal tree with weights w1w2w3wk ▪ The two weights wa ,wb are on lowest level and they are brothers. We denoted by va and vb . Let v0 be the father of va , vb . ▪ waw1 , wbw2 . ▪ Let l a be the length of the path from root to va , and lb be the length of the path from root to vb . ▪ l a =lb ▪ We obtain a new tree T2 by exchanging from leaf v1 to va and from leaf v2 to vb . ▪ w(T1 )-w(T2 )=(wa -w1 )(l a -l 1 )+ (wb -w2 )(l a -l 2 )0

Lemma 5.2: Suppose that nodes of an optimal tree T have weights W1+W2, W3,... , Wk. Then this is an optimal tree with weight W1, W2, W3,..., Wk if T*'s leaf with weight Wi+W2 is replaced by subtree x ∧ Proof: By the Lemma 5.1, there is an optimal tree T2 with weight W1,W2, W3,..., Wk so that T2s two vertices with weights w, and ware brother nodes Let l, be the length of the path from root to v, with weight Wr. Let T2" be a same tree as T2 without leaf with weight w, and leaf with weight W2, but with a having leaf of weight w,+W2. w(T2)=w(T2)-W141-W2l1+(W1+w2)(1-1) Thus w(T2)=W(T2 ) +w+W, Let t* be a same tree as t without leaf with w +w but with subtree w1+w2 Suppose that T* is not an optimal tree

▪ Lemma 5.2: Suppose that nodes of an optimal tree T have weights w1+w2 ,w3 ,,wk . Then this is an optimal tree with weight w1 ,w2 ,w3 ,,wk if T*’s leaf with weight w1+w2 is replaced by subtree Proof: By the Lemma 5.1,there is an optimal tree T2 with weight w1 ,w2 ,w3 ,,wk so that T2 ’s two vertices with weights w1 and w2 are brother nodes. Let l 1 be the length of the path from root to v1 with weight w1 . Let T2 * be a same tree as T2 without leaf with weight w1 and leaf with weight w2 , but with a having leaf of weight w1+w2 . w(T2 *)=w(T2 )-w1 l 1 - w2 l 1 +(w1+w2 )(l 1 -1) Thus w(T2 )=w(T2 *)+w1+w2 Let T* be a same tree as T without leaf with w1+w2 but with subtree Suppose that T* is not an optimal tree

Theorem 5.22: Proof: Let us apply induction on the number n of vertices The results holds Suppose that result holds for n=k-1 For n=k, by the inductive hypothesis, the tree with weight W1+W2, W3,..., Wk by according to Huffman algorithm is an optimal tree By lemma 5.2, this is an optimal tree with weight w1w2,w3y…, W if t’ s leaf with weight w1+w2is replaced by subtree

▪ Theorem 5.22:Proof: Let us apply induction on the number n of vertices. ▪ n=2, The results holds Suppose that result holds for n=k-1 For n=k，By the inductive hypothesis, the tree with weight w1+w2 ,w3 ,,wk by according to Huffman algorithm is an optimal tree . By lemma 5.2, this is an optimal tree with weight w1 ,w2 ,w3 ,,wk if T’s leaf with weight w1+w2 is replaced by subtree