Stanford EE274: Data Compression I 2023 I Lecture 4 - Huffman Codes

Huffman Coding

• Huffman codes are prefix codes that will be discussed in the lecture.
• Huffman coding is a greedy algorithm for constructing a prefix code for a given set of probabilities.
• The algorithm works by repeatedly merging the two nodes with the smallest probabilities until only one node is left.
• The expected code length of a Huffman code is between the entropy of the source and the entropy plus 1.
• Huffman coding can be implemented efficiently using a heap or priority queue.
• Table-based decoding is a low-level technique used in compression algorithms, especially for large volumes of data such as videos and logs.

Entropy and Related Concepts

• Recap of previous lecture:
  • Kraft's inequality: A necessary and sufficient condition for a prefix code.
  • Entropy: A fundamental quantity for lossless compression, defined as the expected number of bits per symbol.
  • Joint entropy for IID variables: Can be calculated in two steps using independence and identical distribution.
  • K Divergence: A distance measure between two probability distributions, greater than or equal to zero with equality if and only if the distributions are equal.
  • Main theorem of compression: For any prefix code, the expected code length is lower bounded by the entropy.
  • Shannon codes: Not optimal, but can achieve entropy or get arbitrarily close to it when working with blocks.
• Quiz review:
  • Entropy of a Bernoulli random variable:
  • H(X) = -p log p - (1-p) log (1-p)
  • H(0) = H(1) = 0
  • H(1/2) = 1
  • K Divergence between two Bernoulli random variables:
  • D(p || q) = p log (p/q) + (1-p) log ((1-p)/(1-q))
• The maximum Kullback-Leibler (KL) Divergence between two probability distributions, (P) and (Q), can be infinite when (P=1) and (Q=0).
• Shannon codes are not optimal for highly skewed distributions, resulting in an expected code length that is much larger than the entropy.
• Block coding can improve the efficiency of Shannon codes by grouping symbols together and assigning shorter codewords to more probable pairs.
• The optimal prefix code for a given distribution can be found by satisfying two conditions:
  • Symbols with higher probabilities should have shorter or equal length codewords compared to symbols with lower probabilities.
  • The two longest codewords should have the same length.

Practical Considerations and Examples

• The Fibonacci sequence is an adverse serial case for Huffman coding, resulting in long code words and a maximum depth close to the number of symbols.
• A practical example of Huffman coding is shown using the frequency of letters on a keyboard, where commonly used letters have shorter code words.
• Huffman coding was used to compress various files, including a book, a Java library, and an encrypted file.
• The compression rate for the book was 44%, and for the Java library, it was also around 40%.
• The encrypted file, however, could not be compressed because encryption algorithms typically output uniformly distributed data, making it appear random to compressors.
• Compressing encrypted data is not effective as encryption destroys the data's structure, resulting in a compression rate of one (no compression).

Next Lecture

• The next lecture will cover theoretical concepts such as entropy and block coding, exploring their importance and interaction with probability and large laws of numbers.
• Professor Saki will lead the next lecture, followed by discussions on practical block and stream codes used in state-of-the-art compressors.