21.5. Optimal Prefix Codes

In order to make a variable length code an unambiguous decodable, we need what is called a prefix code. When we read through a sequence of 0’s and 1’s, we should be ambiguously clear, whether we have read a letter or there is more to read. We should be like the earlier case, where we have read 0 and we do know, whether we stop at 0 and call it an e in the Morse code setting or we want to call it an a which is 0 1.

A prefix code is crucial for ensuring that variable length codes can be decoded without confusion. It means no encoded letter's representation is a prefix of another. For example, if you encounter the binary sequence '0', you should clearly define whether it corresponds to 'e' or another letter like 'a' which is represented by '01'. This clarity helps in correctly understanding the decoded message without ambiguity.

Think of a prefix code like a street address. Each street has a unique number. If you hear '123', you know you're looking for '123 Main Street' and not '123 Elm Street'. If '123' were a prefix for another house number, you'd be confused about which house to find, just like with encoded messages.

So, our goal is to find optimal prefix codes. So, we need to talk about what we mean by optimality. So, remember we said that our goal is to assign shorter codes to more frequent letters.

Optimality in prefix codes means efficiently using shorter codes for more frequently occurring letters. By analyzing a large body of text, we can calculate how often each letter appears (frequency). This frequency distribution enables us to assign codes so the most frequent letters have shorter encodings while less common letters are given longer codes.

Imagine you’re packing boxes for a move. You’d put your essentials (frequent items) in smaller boxes for easy access and the items you rarely use (infrequent items) in larger boxes. By doing this, you make your packing efficient, similar to how prefix codes assign shorter codes to common letters.

if I take n and I multiply by a fraction is say, if fix is say one third, then one third of n of these symbols will actually be the letter x and now, each of these x is going to be represented by it is encoding. So, supposing it is 0 1 0 then each x is going to represent by 3 bits, so then n into f x is the number of times f c x.

To calculate the average length of encoding, we determine how many times each letter appears in the text (frequency) and multiply that by the length of its encoding. This gives the total bits needed for that letter. By summing these over all letters, we can derive the expected length of the entire encoded message, providing insight into the efficiency of our encoding strategy.

Imagine you have a bag of fruits where apples are frequent and oranges are rare. If apples are small and easy to carry (short codes) and oranges take up more space (long codes), then you’ll have an efficient carrying strategy. Just like encoding, where you want to minimize the total 'weight' (bits) of the symbols you're packing.

So, every optimal tree is full, now is easy to see this, because the supposing the claim, we other optimal tree in which somewhere in between, we had a node which had only one child.

An optimal prefix code is structured as a full binary tree, meaning every node must either have no children (be a leaf) or have two children. This rule prevents ambiguity and allows for efficient encoding. If a node only has one child, the tree can be reconfigured to improve the encoding efficiency, thus demonstrating that all optimal trees must be full.

Think of this as organizing a family tree. If a family member only has one child, the tree looks incomplete, and the relationships aren't fully expressed. Similarly, a full binary tree captures all relationships (codes) effectively, ensuring clarity just like an unambiguous family lineage does.

In order to develop the solution, we will use recursion, so what we will do is, we will say, let us look in the overall table that we start with and pick two letters, which have the lowest frequency.

The recursive approach to building optimal prefix codes involves repeatedly selecting the two least frequent letters and combining them into a single node in a binary tree structure. This process is continued until all letters are represented. By assigning longer codes to less frequent letters and shorter codes to more frequent ones, we ensure optimal encoding.

This is like repeatedly finding the two smallest items in a box of toys, merging them into one larger one, and continuing until only one toy is left. Just as smaller toys get combined to make room, less frequent letters are grouped together in binary encoding, efficiently managing space and clarity.

--