Huffman Coding as optimal

Question

In our lecture, the Huffman coding was described as optimal. Optimal with regard to the minimum information content. When asked, the professor explained to me that the length of a fixed code word should be minimal. I have now looked up on the internet what the common information is, this characterises the code as minimal with regard to the average codeword length. I therefore wanted to ask how one can imagine the connection between these two characterisations.

Answer 1

Given a probability distribution $\mu$ on a (usually) finite set $X$ and an alphabet $\Sigma$, a prefix code consists of an assignment of a word $c(x)$ over $\Sigma$ for each $x \in X$, such that no $c(x)$ is a prefix of $c(y)$ for $x \neq y$. The average codeword length is $$ \mathop{\mathbb{E}}\limits_{x \sim \mu} |c(x)|. $$ A minimum redundancy code is a code which minimizes the average codeword length.

Huffman's algorithm is a particular algorithm which is guaranteed to produce a minimum redundancy code. Huffman's algorithm makes some arbitrary choices along the way, and consequently there are many codes which it can produce (for example, we could change the meaning of $0$ and $1$). Each such code is called a Huffman code for $\mu$. Gallager showed in his classic paper Variations on a Theme by Huffman that not every minimum redundancy code is a Huffman code, since Huffman codes satisfy some additional properties which are not satisfied by all minimum redundancy codes.

Minimizing the length of a fixed codeword is easy — we can always find some code in which it has length 1. Similarly, minimizing the length of the longest codeword is easy — the answer is always $\lceil \log_{|\Sigma|} X \rceil$. Sometimes we are interesting in minimizing the average codeword length subject to the longest codeword being at most some length; this cannot be solved using Huffman's algorithm.

Answer 2

Huffman coding is optimal if you have a sequence of symbols, each appearing with a known probability, no correlation between the symbols, no limitation on the length of code words, and when you want each symbol to be translated to exactly one code word.

There is a variation of Huffman coding when symbol length is limited. (Limiting the code word length can make decoding faster, with very little increase of average codeword length). There is arithmetic coding which doesn't have a a fixed relation between code word and symbol and usually gives better correlation.

The most important technique is exploiting correlation between symbols. After you read "seq", what would you guess is the next letter? Most most likely a "q", most likely followed by another vowel. If you get probabilities for each letter, depending on the previous letter, and use a different Huffman code for each of these sets of probabilities, you can encode plain English text with three bits per letter. Of when you encode music, you can predict the next sample quite well from the previous ones, and only encode the difference between your prediction and the actual sample.