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.<wn at its leaf nodes. The weighted leaf path length w(t)of T is W(t)=>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 w1w2...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 w1w2wn。 ▪ 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