21.1. Introduction to Huffman Codes

So, when we communicate, we have to transmit information from one place to another place. So, we might be working in some language like English, Hindi or whatever, but if we were using computers for example, to transmit our data, we know that they must send this information in binary strings. So, our typical goal is to take an alphabet, and then encoded it over strings of 0 and 1, so that at the other end, we can decoded and recover the message.

When we want to share information using computers, we must convert our spoken or written language into binary form, which consists only of 0s and 1s. This binary encoding is crucial because computers work with binary data. The process of encoding involves taking symbols (like letters) from a language and converting them into binary strings that can be transmitted and later decoded back into readable text.

Think of it like sending a secret message with a special code. You create a coding system where each letter corresponds to a specific sequence of clicks (for example, one click might mean 'a', two clicks might mean 'b'). In this case, instead of clicks, we’re using 0s and 1s, which are the language of computers.

So, this brings us to the idea having a variable length encoding, where we use different strings of different lengths for different letters in the alphabet. So, one of the most famous examples of the variable length encoding is the classical Morse code.

In variable length encoding, we use different lengths of binary strings for different letters based on how frequently they occur. The more common a letter is, the shorter its binary representation can be. Morse code is an early example of this, where some letters are represented by shorter sequences (like 'e' with a single dot) and others with longer sequences (like 'q' with a dash-dot-dash).

Imagine you have a list of guests for a party. If some guests (like your best friends) you want to invite frequently, you might use a short form like 'A' for them. For less frequent guests, you might write their full names. This way, you save space on your invitation list, similar to how variable length encoding works.

Now, the problem with Morse’s encoding is that it is ambiguous, when you come to decoding.

Morse code can lead to confusion when decoding because some sequences can represent multiple letters. For example, the sequence '01' could mean 'e' and 't' if read one way or 'a' if read as a two-letter code. This ambiguity causes issues as it can lead to different interpretations of the same sequence of codes.

Consider a puzzle where some pieces fit together in more than one way. If you try to put together a jigsaw puzzle and find that a piece could fit in multiple places, it would be confusing and frustrating. This is akin to how ambiguous codes can lead to miscommunication in encoding data.

So, in order to make a variable length code an unambiguous decodable, we need what is called a prefix quantity.

A prefix code is designed such that no code in the set is a prefix of any other code. This means that once you have read a complete code, you can be sure that it stands for one letter and there’s no ambiguity about it. For example, if '0' is a code for 'a' and '01' is a code for 'b', reading '01' distinctly shows it is 'b', eliminating any confusion.

A good analogy is a stop sign at an intersection. Once you see the stop sign, you know you must stop. There’s no need for further signals or interpretations. Just like the stop sign communicates unambiguously, a prefix code clarifies what each string means without confusion.

Our goal is to find optimal prefix codes. So, we need to talk about what we mean by optimality.

Optimal prefix codes are designed to minimize the average length of encoded messages. This involves analyzing the frequency of letter usage within a language. More frequent letters are assigned shorter codes, which reduces the overall length of data transmitted. However, optimality can vary between languages, as different languages have different frequency patterns of letters.

Imagine you’re packing for a move. You want to make sure that the most frequently used items are easily accessible and take up the least amount of space in your moving boxes. Just as packing considers frequency of use to maximize efficiency, coding does the same by allocating shorter codes for commonly used letters to save space.

--