Statistical compressors: Huffman coding

In this appendix, we describe the Huffman coding. The Huffman coding is a code that can be uniquely decodable code with a prefix and an optimum. This means that no codeword is prefixed by another codeword, and the decoding process is univocal. We will come back to the optimality of the code later. It is worth returning to it after a detailed algorithm analysis. Unambiguous decodability is a prerequisite for any code. In contrast, the fact that it is a prefix code is very convenient because, during the decoding phase, it allows us to avoid wasting time. Let us suppose that we have a code that cannot be univocally decoded in which there are the two words |$10$| and |$100$|⁠; when the decoder has read the first two digits, it has to wait to see the third one to know which one it is since |$10$| is a prefix of |$100$|⁠. This waiting time for the decoder is called the decoding delay, and it occurs when it is impossible to identify the codeword after reading its last letter immediately. The only way to avoid decoding delays is to adopt a prefix code. Encoders based on the Huffman coding belong to the class of so-called entropy coders.