Unit 9: Huffman Coding and Data Compression - Practice Quiz

1 What is the main purpose of Huffman coding?

2 Which type of algorithm is used to construct a Huffman tree?

3 Which symbols are combined first while constructing a Huffman tree?

4 In a Huffman tree, where are the original symbols normally stored?

5 What determines the length of a symbol's Huffman code?

6 Which symbols generally receive shorter Huffman codes?

7 What does it mean that Huffman codes are prefix-free?

8 Which data structure is commonly used to select the two least frequent nodes in Huffman coding?

9 When two Huffman nodes with frequencies and are merged, what is the new node's frequency?

10 What values are typically assigned to the two branches of a binary Huffman tree?

11 How is a Huffman-encoded symbol normally decoded?

12 What kind of code length does Huffman coding use for different symbols?

13 What is the general goal of data compression?

14 Which type of compression allows the original data to be reconstructed exactly?

15 Which type of compression may permanently discard some information?

16 Which type of compression is generally required for executable program files?

17 An original file has size bytes and its compressed form has size bytes. How many bytes are saved?

18 What is redundancy in the context of data compression?

19 Which simple compression method replaces consecutive repeated values with a value and its count?

20 What is decompression?

21 A source has symbol frequencies , , , , , and . What is the average code length of an optimal binary Huffman code?

22 For symbol frequencies , , , and , which sequence of combined weights is produced by Huffman's algorithm?

23 Given the prefix codes , , , and , what does the bit string decode to?

24 Which set of binary codewords satisfies the prefix-free property required for Huffman decoding?

25 A canonical Huffman code assigns lengths to symbols in that order. If , what is the canonical code for ?

26 A binary source has probabilities , , , and . A Huffman code gives corresponding lengths , , , and . What is its expected code length?

27 Symbols occur times, respectively. How many bits are needed to encode all symbols using an optimal binary Huffman code?

28 Eight symbols have equal nonzero frequencies. What codeword length will each symbol have in an optimal binary Huffman code?

29 A symbol with probability has code length , while a symbol with probability has code length . By how much does their combined expected contribution decrease if their codewords are swapped?

30 A file contains symbols drawn from six symbols with frequencies . Its Huffman payload uses bits, and storing the tree requires bits. Compared with a fixed-length code, how many bits are saved overall?

31 Using compression ratio defined as original size divided by compressed size, what is the ratio when a KB file is compressed to KB?

32 A MB file is reduced to MB. What percentage of the original storage space is saved?

33 What is the Shannon entropy of a source with symbol probabilities , , , and ?

34 The string AAAAABBBCCCCCCCC is stored using bits per character. Run-length encoding stores each run as an -bit character and an -bit count. How many bits are saved?

35 A compressor reduces a -byte file payload to bytes but adds bytes of metadata. What is the overall percentage reduction?

36 A source uses an alphabet of eight symbols. Fixed-length coding requires bits per symbol, while a variable-length code averages bits. How many bits are saved over symbols?

37 A file contains both long repeated substrings and uneven token frequencies. Which compression pipeline most directly exploits both properties?

38 An -megabit file is sent over a Mbps link. Compression has a ratio of and adds seconds of total processing time. How much time is saved compared with sending the original file?

39 A source has entropy bits per symbol, while a lossless code uses an average of bits per symbol. What is the code's redundancy above the entropy?

40 A run-length encoder represents each run using an -bit symbol and an -bit count. The uncompressed representation uses bits per symbol. What is the minimum run length that produces a strict size reduction?

41 A source has symbol frequencies . What weighted external path length and average codeword length result from binary Huffman coding?

42 Equal weights can allow several choices during Huffman construction. Which property is guaranteed across all valid tie-breaking choices?

43 A full -ary Huffman code must be constructed for positive-frequency symbols. How many zero-frequency dummy symbols must be added before repeatedly merging four nodes?

44 A canonical binary Huffman code uses symbol order and codeword lengths , respectively. If the first codeword is the lexicographically smallest possible one, what is the codeword for ?

45 A length-limited binary prefix code is required for symbols, with every codeword having length at most . Which conclusion is correct regardless of the symbol probabilities?

46 For a binary source with probabilities , what are the entropy and optimal Huffman average length?

47 An -byte file is originally stored using bits. Huffman compression averages bits per byte, but its frequency-table header costs bits. What is the smallest integer for which the compressed representation is strictly smaller?

48 A source has probabilities , and all five symbols must receive distinct finite binary prefix codewords. What is the minimum expected codeword length?

49 Which statement correctly expresses the sibling property used in the proof of binary Huffman coding optimality?

50 A single bit is deleted from a stream encoded with an arbitrary binary Huffman code. What recovery property follows solely from the prefix-free condition?

51 Two blocks each contain symbols. The first has counts , and the second has counts . Ignoring headers, compare separate binary Huffman coding of the blocks with one global Huffman code.

52 A memoryless binary source has probabilities . Why can arithmetic coding of a long sequence substantially outperform symbol-by-symbol binary Huffman coding?

53 Binary Huffman coding is applied to frequencies . Which symbols receive the maximum codeword length, and what is that length?

54 Can a binary prefix code have codeword lengths ?

55 For positive-frequency symbols, what is the largest possible depth of a leaf in a binary Huffman tree, considering all possible frequency distributions?

56 Consider frequency sequences and , whose symbols have the same initial frequency ordering. Which conclusion is correct?

57 An unconstrained Huffman tree violates a required maximum codeword length . Which method correctly obtains an optimal binary length-limited prefix code?

58 Why can no lossless compressor map every -bit input to a distinct binary output shorter than bits?

59 An i.i.d. source has entropy bits per symbol. Binary Huffman coding is applied to length- source blocks. Which bound holds for the average encoded length per source symbol?

60 Let be an equiprobable binary variable and let , where is independent with . If both encoder and decoder know , what asymptotic lossless compression rate is achievable for ?