算法课件Lecture12章节.pptVIP

Lecture 12Huffman Codes Problemand Catalan Number ?-ordered Tree Huffman Coding Problem Algorithm and correctness Catalan Number ?-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 ? children and each edge starting from v is labeled by a unique symbol in ? = {0, 1, …, ?-1}; The leaves (out-degree=0) have no children. ?-ordered trees 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 Huffman Codes Huffman code 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. English Alphabet The Huffman 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 of the file given the source symbols. Given a file, does this method give a true shortest code? 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 be found with codeword lengths {l1, l2, ..., ln}. The Huffman algorithm first constructs {l1, l2, ..., ln} by the probabilities, then constructs the codes. Huffman Coding Procedure Sort the probabilities in non-increasing order Combine two rightmost probabilities and insert the sum properly by keeping the order. Repeat 2 until there is only one probability left Construct a 2-or