Compression: Prefix CodesGreg PlaxtonTheory in Programming Practice, Spring 2005Department of Computer ScienceUniversity of Texas at Austin(Binary, Static) Code• Maps each symbol a of a given finite alphabet A to a codeword w(a)in {0, 1}∗(i.e., a binary codeword)– The mapping is static, i.e., a is always encoded as w(a), regardlessof the surrounding context– So the mapping determines the encoder– But decoding can be problematic (why?)Theory in Programming Practice, Plaxton, Spring 2005Uniquely Decodable Code• A code is uniquely decodable if the associated encoder maps distinctinput strings to distinct encoded strings– Necessary and sufficient for lossless decoding– Example of a code that is uniquely decodable? One that is not?• Let `(a) denote the length of w(a)Theory in Programming Practice, Plaxton, Spring 2005Optimal Code• Suppose we are given a frequency f(a) for each symbol a in A– Let p(a) denotef(a)Pb∈Af(b)– Note that p(a) may be viewed as a probability• We define the weight of a code asPa∈Ap(a) · `(a)• A code is optimal (for a given alphabet and associated probabilitydistribution) if it has minimum weight over all uniquely decodablecodes– Remark: Keep in mind that we are only talking about optimalitywith respect to the set of binary static codes; we will revisit thisissue laterTheory in Programming Practice, Plaxton, Spring 2005An Entropy-Based Lower Bound on Code Weight• Let H denote the entropy of the probability distribution associated withalphabet A, i.e.,H = −Xa∈Ap(a) log p(a)• Theorem: The weight of any uniquely decodable code for A is at leastH• We will prove the preceding theorem using the two inequalities givenon the next slide and the fact that the logarithm function is concaveover the positive realsTheory in Programming Practice, Plaxton, Spring 2005Two Inequalities• McMillan: Any uniquely decodable code satisfiesXa∈A2−`(a)≤ 1• Jensen: If λ1, . . . , λnare nonnegative reals summing to 1 and f is aconcave function over an interval containing the reals x1, . . . , xnthenXiλi· f(xi) ≤ fÃXiλi· xi!Theory in Programming Practice, Plaxton, Spring 2005Proof that Entropy ≤ WeightXa∈Ap(a) log1p(a)−Xa∈Ap(a) · `(a) =Xa∈Ap(a) log1p(a)2`(a)≤ logÃXa∈A2−`(a)!≤ log 1= 0Theory in Programming Practice, Plaxton, Spring 2005Prefix Code• A prefix code is a code in which no codeword is the prefix of another– Uniquely decodable– Easy to decode• Exercise: Give an example of a code that is uniquely decodable but isnot a prefix codeTheory in Programming Practice, Plaxton, Spring 2005Kraft-McMillan Inequality• Kraft: For any sequence of integers `1, . . . , `|A|such thatP1≤i≤|A|2−`i≤ 1, there is a prefix code for A with codeword lengths`1, . . . , `|A|• Since every uniquely decodable code satisfies McMillan’s inequality, wecan restrict our attention to prefix codes in searching for an optimalcode• McMillan’s inequality and the above result are often stated together(in two parts) and referred to as the Kraft-McMillan inequalityTheory in Programming Practice, Plaxton, Spring 2005An Entropy-Based Upper Bound on the Weight of anOptimal Code• Theorem: There is an optimal (prefix) code for A with weight less thanH + 1• Hint: First use the Kraft-McMillan inequality to establish the existenceof a prefix code for which `(a) = dlog1p(a)e for all a in ATheory in Programming Practice, Plaxton, Spring 2005Summary and Discussion of Entropy-Based Bounds• The weight of an optimal prefix code lies in the interval [H, H + 1)• If H is high, then an optimal prefix code is guaranteed to achieveclose to the best possible compression ratio achievable with any codingtechnique (static or not)– Here we are appealing to Shannon’s entropy bound• If H is close to zero, then an optimal prefix code might achieve acompression ratio that is dramatically worse than the best possible– Example?– Other compression techniques may be applied in such situations inorder to achieve near-optimal performance (e.g., arithmetic codingor run-length coding)Theory in Programming Practice, Plaxton, Spring 2005Computing an Optimal Prefix Code• Huffman’s algorithm will be presented in the next lectureTheory in Programming Practice, Plaxton, Spring
View Full Document
Unlocking...