(a) Given the following alphabet = (a, g, h, i,l, m, o,r, t) and corresponding...

Transcribed Image Text:

(a) Given the following alphabet Σ = (a, g, h, i,l, m, o,r, t) and corresponding frequencies, use Huffman's algorithm to compute an optimal prefix-free code. Represent the prefix-free code as a binary tree, with either 0 or 1 on each edge. Letter a m 0 r t Frequency 0.14 0.06 0.10 0.17 0.07 0.11 0.10 0.08 0.17 (b) What is the expected encoding length (average number of bits per element) of this alpha- bet? Entropy is a mathematical formulation of the uncertainty and/or the amount of information in a data set. Consider a data set D consisting of n characters, each character independently chosen from a set C according to a specified probability distribution p. That is, for c E C and 0 ≤ i ≤n, the probability that the ith character of D is c is p(c). Note that Ecec P(c) = 1. The entropy of data set D is then defined to be np(c)log₂ (1/p(c)). cec Intuitively, the entropy measures the information-theoretic minimum number of bits needed to represent the data set. (c) Calculate the entropy of a corpus, which contains the letters in the same frequencies as (a). View the frequencies as probabilities for the entropy calculation. (Note that the frequencies sum up to 1.) Compare the entropy with the compression achieved by Huffman coding and indicate whether Huffman encoding yields the best possible compression. More generally, do you think entropy captures the limit of how much that corpus can be compressed? Explain briefly in words. (a) Given the following alphabet Σ = (a, g, h, i,l, m, o,r, t) and corresponding frequencies, use Huffman's algorithm to compute an optimal prefix-free code. Represent the prefix-free code as a binary tree, with either 0 or 1 on each edge. Letter a m 0 r t Frequency 0.14 0.06 0.10 0.17 0.07 0.11 0.10 0.08 0.17 (b) What is the expected encoding length (average number of bits per element) of this alpha- bet? Entropy is a mathematical formulation of the uncertainty and/or the amount of information in a data set. Consider a data set D consisting of n characters, each character independently chosen from a set C according to a specified probability distribution p. That is, for c E C and 0 ≤ i ≤n, the probability that the ith character of D is c is p(c). Note that Ecec P(c) = 1. The entropy of data set D is then defined to be np(c)log₂ (1/p(c)). cec Intuitively, the entropy measures the information-theoretic minimum number of bits needed to represent the data set. (c) Calculate the entropy of a corpus, which contains the letters in the same frequencies as (a). View the frequencies as probabilities for the entropy calculation. (Note that the frequencies sum up to 1.) Compare the entropy with the compression achieved by Huffman coding and indicate whether Huffman encoding yields the best possible compression. More generally, do you think entropy captures the limit of how much that corpus can be compressed? Explain briefly in words.

Answer rating: 100% (QA)

a To compute the optimal prefixfree code using Huffmans algorithm we start by building a binary tree ... View the full answer