21.2. Variable Length Encoding

So, this brings us to the idea of having a variable length encoding, where we use different strings of different length for different letters in the alphabet.

Variable length encoding is a method of representing characters where different letters are encoded with strings of varying lengths instead of using a fixed-length representation. This means that more frequently used characters can have shorter representations while less common characters can have longer representations, potentially reducing the amount of data that needs to be transmitted.

Think of coding as a form of shorthand. For instance, if 'e' is the most common letter, instead of writing it out fully every time, we might assign it a simple symbol, like a dot. On the other hand, a rarer letter like 'z' might be represented by a longer sequence. It’s similar to how people often use abbreviations in texting; instead of writing ‘laugh out loud,’ you can just type ‘LOL.’

So, one of the most famous examples of the variable length encoding is the classical Morse code.

Morse code is a form of variable length encoding developed by Samuel Morse. It uses dots and dashes to represent letters, where shorter codes are assigned to more common letters. For instance, 'e' is represented as a dot (0) and 't' as a dash (1). However, one challenge with Morse code is its ambiguity during decoding, as sequences can be interpreted in multiple ways.

Imagine you are playing a game of charades while being blindfolded. If one player uses a quick, short gesture like a wave, it might be easily understood as 'hi.' But if another person uses a longer and more complex set of gestures, the meaning could be confusing if you aren't sure where one action ends and another begins—similar to how Morse code sequences can be misinterpreted.

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

A prefix code is a type of encoding where no codeword in the set is a prefix of another codeword. This property ensures that when decoding a message, it's clear where one letter ends, and another begins, eliminating any uncertainty. For example, if we have the codes for 'a' as '0' and 'a' as '01,' interpreting '01' could be confusing, which is avoided by proper prefix coding.

Consider trying to read a sentence where each meaning of a word can start with the same letters—like 'bear' and 'bare.' If only the starting letters are provided without more context, the meaning becomes unclear. A prefix code acts like making sure each word is complete before moving on to the next; it gives clarity in communication.

So, our goal is to find optimal prefix codes.

Finding an optimal prefix code involves assigning shorter codes to more frequent letters while ensuring that the coding scheme remains unambiguous. To achieve this, statistical analysis of letter frequency in the target language is typically conducted and an encoding scheme will be developed depending on this analysis.

Think about packing for a trip. If you know you are going to need a lot of T-shirts and only a few pairs of shoes, you might pack T-shirts in a smaller pouch that’s easier to access and bulkier items separately. The goal here would be maximizing the efficiency of how much you can carry and access things you need frequently.

So, let us work out how this, so suppose we take our earlier example of 5 letters, now we insert some fictitious information about frequencies.

To determine how many bits are required to encode a message with a specific set of letters, you need to consider the frequency of those letters and the lengths of their corresponding codes. By calculating a weighted average based on the frequency of each letter and the length of their encoding, we can work out an expected number of bits per letter and therefore the total size of the encoded message.

Imagine baking cookies where different ingredients represent letters. If you know chocolate chips (very popular) need fewer as the main ingredient and flour (less used) needs more, you can plan the recipe more efficiently. In the same way, using letter frequencies allows for efficient planning of how to encode messages.

Of course, I do not use 2.25 bits per letter, but what it says this for instance, if I have 100 letters, I would expect to see 225 bits in the output encoding.

In contrast to variable length encoding, fixed length coding uses the same number of bits for every letter. While this method simplifies encoding and decoding because each letter can be assigned a specific location in the bit stream, it is usually less efficient than variable length encoding, especially when there are varying frequencies among letters.

Think of fixed-length encoding like having a huge suitcase where every item you pack has to fit in a specific, individually-sealed compartment, irrespective of its size. While organized, it can lead to wasted space (wasting bits) since you may need larger compartments for smaller items.

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

When visualizing variable length encoding, one effective method is to use a binary tree structure. In this tree, each path represents a sequence of 0s and 1s that correspond to a letter. Implementing each letter into the tree according to its frequency allows for efficient retrieval and ensures that the codes remain unambiguous due to the prefix code properties.

Think of a family tree where each branch represents a different family member. If you start at the base and move up the branches, each decision point (left or right) leads you to more specific individuals in the family. Similarly, tracing the paths in a binary tree for encoding leads to unique letter representations based on organized routes.

So here is the conclusion in that leaves of maximum depth occurred in pairs.

An optimal binary tree for encoding messages possesses certain properties, such as having full nodes (each node either has two children or none), where only leaf nodes serve as the endpoints for letters. Moreover, in an optimal configuration, the least frequent letters occupy the deepest levels of the tree, ensuring a logical structure that adheres to the properties of prefix codes.

Consider a team of builders constructing a layered cake. The heavier (or more frequently used) ingredients need to be lower in the structure to avoid toppling over lighter ones. Just as builders strategically place heavier materials for stability, optimal tree structures arrange letters so that those needed more frequently are more accessible at higher levels.

--