《算法课件Lecture12章节》由会员分享，可在线阅读，更多相关《算法课件Lecture12章节（37页珍藏版）》请在金锄头文库上搜索。
1、 2004 SDU,Lecture 12 Huffman Codes Problem and Catalan Number,-ordered Tree Huffman Coding Problem Algorithm and correctness Catalan Number, 2004 SDU 2,-ordered trees,A -ordered tree is a tree-like graph satisfying There is a distinguished vertex called root Each internal vertex v has at most childr
2、en and each edge starting from v is labeled by a unique symbol in = 0, 1, , -1; The leaves (out-degree=0) have no children.,An example of 3-ordered tree,Each vertex v corresponds to a word: the sequence of symbols on the path from the root to the vertex. Example: 0, 01, 12, 2, 2004 SDU 3,-ordered tr
3、ees vs prefix codes,A code C is called prefix code if no codeword in C is a prefix of some other codewords. Clearly, the leaves of a -ordered tree correspond to a prefix code, and Each prefix code can be described by a -ordered tree,Prefix Code C = 00, 01, 12, 2, 2004 SDU 4,Huffman Codes,Huffman cod
4、e was proposed by David A. Huffman in 1952. A Huffman code is a prefix code, so is a uniquely decodable code The main application of Huffman codes is data compression, typically saving 20% to 90%. A Huffman code can be constructed from the frequencies of each source symbol., 2004 SDU 5,English Alpha
5、bet,Sym Prob Sym Prob Sym Prob Blk 0.1859 I 0.0575 R 0.0484 A 0.0642 J 0.0008 S 0.0514 B 0.0127 K 0.0049 T 0.0796 C 0.0128 L 0.0321 U 0.0228 D 0.0317 M 0.0194 V 0.0083 E 0.1031 N 0.0574 W 0.0175 F 0.0208 O 0.0632 X 0.0013 G 0.0152 P 0.0152 Y 0.0164 H 0.0467 Q 0.0008 Z 0.0005, 2004 SDU 6,The Huffman
6、Coding Problem,Input: A set S = s1, s2, , sn of n source symbols with independent probabilities p1, p2, , pn. Output: A prefix code C = C1, C2, ,Cn for S on alphabet = 0, 1, 2, , -1 with minimum average length where li is the length of Ci. Note: This is equivalent to minimize the length of the code
7、of the file given the source symbols. Given a file, does this method give a true shortest code?, 2004 SDU 7,Idea of Huffman Coding,Directly follow the proof of Property 2 of Kraft inequality: If a set of integers l1, l2, ., ln satisfies the Kraft inequality, then a prefix code C = C1, C2, , Cn can b
8、e found with codeword lengths l1, l2, ., ln. The Huffman algorithm first constructs l1, l2, ., ln by the probabilities, then constructs the codes., 2004 SDU 8,Huffman Coding Procedure,Sort the probabilities in non-increasing order Combine two rightmost probabilities and insert the sum properly by ke
9、eping the order. Repeat 2 until there is only one probability left Construct a 2-ordered tree (binary tree) according to the above procedure, 2004 SDU 9,An ExampleCombine Probabilites,Consider p = 0.6, 0.2, 0.05, 0.05, 0.03, 0.03, 0.03, 0.01 and = 0, 1.,0.6 0.2 0.05 0.05 0.03 0.03 0.03 0.01 0.6 0.2
10、0.05 0.05 0.04 0.03 0.03 0.6 0.2 0.06 0.05 0.05 0.04 0.6 0.2 0.09 0.06 0.05 0.6 0.2 0.11 0.09 0.6 0.2 0.2 0.6 0.4 1.0, 2004 SDU 10,An ExampleDetermine the Lengths,0.6(1) 0.2(2) 0.05(4) 0.05(4) 0.03(5) 0.03(5) 0.03(5) 0.01(5) 0.6(1) 0.2(2) 0.05(4) 0.05(4) 0.04(4) 0.03(5) 0.03(5) 0.6(1) 0.2(2) 0.06(4)
11、 0.05(4) 0.05(4) 0.04(4) 0.6(1) 0.2(2) 0.09(3) 0.06(4) 0.05(4) 0.6(1) 0.2(2) 0.11(3) 0.09(3) 0.6(1) 0.2(2) 0.2(2) 0.6(1) 0.4(1) 1.0(0),Verify Kraft Inequality: 2-1 + 2-2 + 2-4 + 2-4 + 2-5 + 2-5 + 2-5 + 2-5 = 1, 2004 SDU 11,An ExampleConstruct the Prefix Code (Proof of Property 2),Construct C1 = 0 Co
12、nstruct C2 = 0, 10 Construct C4 = 0, 10, 1101, 1110 Construct C5 = 0, 10, 1101, 1110, 11000, 11001, 11110, 11111, 2004 SDU 12,An ExampleConstruct the Binary Tree (Huffman),0.6(1) 0.2(2) 0.05(4) 0.05(4) 0.03(5) 0.03(5) 0.03(5) 0.01(5) 0.6(1) 0.2(2) 0.05(4) 0.05(4) 0.04(4) 0.03(5) 0.03(5) 0.6(1) 0.2(2
13、) 0.06(4) 0.05(4) 0.05(4) 0.04(4) 0.6(1) 0.2(2) 0.09(3) 0.06(4) 0.05(4) 0.6(1) 0.2(2) 0.11(3) 0.09(3) 0.6(1) 0.2(2) 0.2(2) 0.6(1) 0.4(1) 1.0(0), 2004 SDU 13,Huffman Algorithm for = 2,A Pseudo-code Huffman Algorithm for = 2,C corresponds to P in our case, 2004 SDU 14,Another Examplein non-decreasing
14、order, 2004 SDU 15,Extend the Huffman Algorithm for 2,In the combination of probabilities steps, when = 2, we combine the two least probabilities into one each time. How about when 2? combine probabilities each time? if so, in the last step, there may be less than probabilities. then, the root of the -ordered tree constructed may have less than children. Is the prefix code described by the leaves of the tree optimal? i.e, with minimal average code length?, 2004 SDU
