21.10. Properties of Optimal Trees

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. So, somehow we have to determine, what are more frequent and less frequent letters?

In order to create optimal prefix codes, we need to understand the concept of frequency in letters. The aim is to assign shorter binary codes (sequences of 0s and 1s) to letters that appear more frequently in text. This means we must analyze a piece of text to figure out how often each letter occurs. The letters that appear more often in the text will get shorter codes, meaning they take up less space during encoding.

Think about how you might pack for a flight. If you know you'll use your lightweight, frequently worn clothes more often than heavier winter clothes (which you wear less frequently), you'd pack those lighter clothes on top for easy access, representing the idea of being 'shorter' or more 'accessible.'

So, people have measure the frequency of the occurrence of each letter and different languages, so this is a very language specific thing.

To optimize our encoding, we analyze a large body of text to determine how often each letter appears. We can collect statistics to find out what fraction of the total letters are each specific letter. This analysis can vary greatly between languages; for example, 'e' might be the most common letter in English, while the most common letter in another language might be different.

Picture a bakery that sells various types of pastries. If the sales data shows that chocolate croissants sell twice as much as apple tarts, the bakery begins to optimize its inventory by making more chocolate croissants available, just as we adjust our letter codes based on their usage frequency.

If I just look at the total weighted average of two links of the encodings, then this is if you study probability theory, what is called the expected length of the encoding.

The expected length of the encoding refers to the average number of bits required to encode letters based on their frequency. Each letter's contribution to the total bit length is calculated by multiplying the frequency of the letter by the length of its code. Summing these for all letters gives us an idea of how efficient our encoding system is. An efficient system will have a lower expected length because it uses fewer bits per letter.

Imagine you're organizing a group of students for a project. If you know some students excel at certain tasks, you assign them those tasks to maximize efficiency. Similarly, in encoding, we assign shorter codes to letters that appear frequently, which minimizes the overall 'work' of encoding.

To get to this, it is useful to think of these encodings has binary trees, so in a binary tree I can interpret directions as 0 and 1.

Encoding letters can be visualized using binary trees, where each letter is represented at the leaves of the tree. The path you take to reach a leaf determines the binary code for that letter: moving left might represent a '0' and moving right a '1'. Because of this tree structure, we can exploit the properties of trees to ensure there’s a unique path to each letter, maintaining our prefix code property.

Think of finding your friend's house using a map. Each turn (left or right) represents a decision point. By faithfully following those decisions (or in our case, binary steps), you’ll reach your friend's house without getting lost, much like how a binary tree guides you to the specific letter/code.

So, the first thing is that in such a tree, if it is optimal, every node will either have no children will we a leaf or it will have two children.

An optimal tree must be full, meaning each node must either have two children or be a leaf node itself. This is because if a node only has one child, we could adjust the structure of our tree to create a more efficient representation of the encoding. Thus, fully populated nodes allow the tree to convey information more efficiently.

Consider a well-planned city where every block is fully developed with homes. If some blocks were empty (only one home), it would indicate wasted space and potential for more development, just like a tree lacking full nodes represents inefficiency.

The next property is exactly what we saw the earlier thing, which is that, if I have two nodes x and y, such that, x is higher than y, so x is at some level and y is different level.

The depth of a node in an optimal tree corresponds to its frequency, where higher frequency letters are at greater depths and thus represented with shorter codes. If we were to find a letter with a higher frequency below a letter with a lower frequency in terms of tree depth, it would mean we could switch their positions to create a better encoding scheme. Therefore, the tree structure effectively maintains this relationship.

Imagine a concert lineup, where the most popular bands (higher frequency) play earlier (higher up in the schedule) to a larger audience. If a lesser-known band played in the popular band’s slot, it would reduce overall satisfaction, reflecting how tree positions dictate encoding efficiency.

if I have a maximum depth leaf in my optimal tree, then we need occur is a pair with another maximum depth leaf.

In an optimal tree, if a leaf is at maximum depth, it must occur in pairs with another leaf of equal depth. This is because having a leaf alone at a deeper end would violate the tree's balance: each maximum depth represents the least frequently encoded letters and should thus be grouped together to optimize space and clarity.

Think of a pair of 3D glasses: both lenses must work together for you to see the full picture. If one lens is missing or mismatched, the result is ineffective. Similarly, leaves at maximum depth provide encoding clarity only when paired appropriately.

--