21.4. Prefix Codes

For the last example of a greedy algorithm in this course, we will look at a problem in communication theory, we will look at the problem of 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 are using computers, for example, to transmit our data, we know that they must send this information in binary strings...

In this section, we learn about the necessity of encoding information for computer-based communication. Whenever we communicate, especially through computers, the data needs to be transmitted in a format they can understand, which is binary code—combinations of 0s and 1s. Each letter or symbol in our language needs to be converted into these binary strings so that computers can process them successfully.

Think about sending a message via email. The words you type are transformed into binary codes that represent each character, allowing the computer to understand and transmit your message accurately over the internet.

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

This chunk introduces the concept of variable length encoding, which allows us to assign short binary codes to frequently used letters and longer codes to less frequently used letters. It contrasts with fixed length codes, where every letter uses the same number of bits, and discusses Morse code as an early example of this idea. Morse code uses dots and dashes to represent letters, making it a variable-length encoding system.

Imagine a chatting app using emojis. Some emojis, like a smiley face, may be represented by 1 or 2 bits because they are used often. Meanwhile, a less popular emoji might take 5 bits. This way, frequent expressions can be sent more quickly, saving time and data!

Now, the problem with Morse’s encoding is that it is ambiguous. When you come to decoding, we should be unambiguously clear whether we have read a letter or there is more to read...

This section delves into the risk of ambiguity with Morse code, where certain patterns could represent different letters depending on how they're read. The issue is that if the code for one letter could be the beginning of another’s, it creates confusion when decoding messages.

Imagine if you received a text that said 'u r?' without any spaces or punctuation. Depending on how you interpret it, it could mean 'You are?' or 'You are reading?'. Just like that, a wrongly decoded message could lead to misunderstandings.

In order to make a variable length code unambiguous to decode, we need what is called a prefix code...

Prefix codes ensure that no code in the system is a prefix of any other. This means that once we see a specific code sequence, we know it corresponds to a single letter, preventing any possible confusion in decoding the data.

Consider how a road sign might read 'STOP'—it clearly defines an action without confusion. No other sign starts with 'ST', so you instantly know what to do when you see it. Similarly, prefix codes make decoding easy as each sequence leads to a specific letter, preventing ambiguity.

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

This chunk discusses how we can optimize encoding by using the frequency of letters to assign shorter codes to those that appear more often, thus minimizing the average length of code used. It brings in the idea of calculating frequencies of letters in a given language to approach optimal encoding effectively.

If you think about it like a library of books; if the most popular authors have shorter titles or codes, you can find their works quickly. If an author has fewer books or they’re read less often, they can afford longer titles. Thus, optimizing saves time just as efficient coding saves bits in encoding.

To get to this, it is useful to think of these encodings as binary trees...

This part explains how encoding can be visualized as binary trees, where paths lead to letters. By traversing the tree in a certain way (left for 0 and right for 1), we can assign binary sequences to letters based on their position within the tree. The properties of these trees ensure that the encoding remains efficient and unique.

Imagine navigating through a decision tree, like when you’re solving a mystery. Each question leads to a path until you reach the answer. Similarly, each path in the binary tree leads to a specific letter, allowing efficient encoding as you follow the branches down to the leaves.

Having encoded look at our encoding the binary tree, we will now make a couple of observations that will be useful to develop an optimal algorithm...

Several properties of an optimal prefix code tree are outlined, such as every optimal tree must have either zero or two children for each node. This implies that we can build a more efficient encoding strategy by ensuring each node's child nodes are uniform, which strengthens the structure and decreases average encoding lengths.

Think of a well-organized family tree where every parent (node) has either no children or two children at each level. This organized approach allows clear lineage and relationships to be established, similar to how a binary tree structure helps clarify which codes correspond to which letters in encoding.

--