Information Theory — Lossless Compression

You need to transmit messages that contain only the letters A and B. The wire only carries 0s and 1s.

You need to decide: what bit string does A become? What does B become?

Before you code:

• You have two symbols and two possible 1-bit strings: "0" and "1".
• Try: A → "0", B → "1".
• Encode "AABBA" by hand. What do you get?
• Now decode it back. Do you get the original?

Write a function encode_ab(message) that takes a string of As and Bs and returns a binary string.

Write a function decode_ab(bits) that takes a binary string and returns the original message.

encode_ab("AABBA")   # "00110"
encode_ab("BA")      # "10"
decode_ab("00110")   # "AABBA"
decode_ab("10")      # "BA"

Would any other encoding cause confusion?

Try: A → "0", B → "00".

• Encode "AB" → ?
• Encode "BA" → ?
• Are they the same bit string?

Key definition: A code is prefix-free if no codeword is the start (prefix) of another.

• A="0", B="00" is NOT prefix-free: "0" is a prefix of "00".
• A="0", B="1" IS prefix-free.

Write is_prefix_free(scheme) that checks whether a given dict {symbol: bits} is prefix-free.

is_prefix_free({"A": "0", "B": "1"})    # True
is_prefix_free({"A": "0", "B": "00"})   # False  ("0" is prefix of "00")
is_prefix_free({"A": "0", "B": "10"})   # True

Now messages contain A, B, and C. You still can only send 0s and 1s.

With 1 bit you can only represent 2 different things ("0" and "1"). You have 3 symbols — so at least one must get a longer code.

Option 1 — Fixed-width (2 bits each):

A → "00", B → "01", C → "10" (We skip "11" — it goes unused.)

Write encode_fixed(message) and decode_fixed(bits) using this fixed 2-bit scheme.

encode_fixed("ABC")    # "000110"
encode_fixed("CAB")    # "100001"
decode_fixed("000110") # "ABC"
decode_fixed("100001") # "CAB"

Option 2 — Variable length:

A → "0", B → "10", C → "11"

This uses only 1 bit for A, and 2 bits for B and C. Is it prefix-free?

• Is "0" a prefix of "10"? "10" starts with "1", not "0". ✓
• Is "0" a prefix of "11"? "11" starts with "1", not "0". ✓
• Is "10" a prefix of "11"? They share "1" but differ at position 2. ✓

How do you decode variable-length codes?

Walk through the bits one at a time, accumulating characters until the accumulated string matches a known codeword — then emit the symbol and reset.

Write encode_var(message) and decode_var(bits) using A="0", B="10", C="11".

encode_var("ABC")    # "01011"  (0 + 10 + 11)
encode_var("CAB")    # "11010"  (11 + 0 + 10)
decode_var("01011")  # "ABC"
decode_var("11010")  # "CAB"

For the message "AAABBC":

• Fixed scheme (2 bits/symbol): how many bits total?
• Variable scheme: how many bits total?
• Which is shorter?

Verify that the variable scheme {"A":"0","B":"10","C":"11"} is prefix-free.

is_prefix_free(VAR_SCHEME)  # True

In a prefix-free code, no codeword is a prefix of another. Why is this property essential for decoding?

A. It makes the codes shorter

B. Without it, the decoder can't tell where one codeword ends and the next begins — the bit stream becomes ambiguous

C. It ensures all codewords have the same length

D. It prevents errors during transmission

Now add a fourth symbol D. Suppose you know how often each symbol appears:

Question: Does the order in which you assign short vs. long codes matter? Let us find out.

Write avg_bits(scheme, frequencies) that computes the expected number of bits per symbol.

Think it through: In the fixed 2-bit scheme, every symbol costs 2 bits, so the average is obviously 2. But in a variable-length scheme, A costs 1 bit and appears 50% of the time, B costs 2 bits and appears 25% of the time, and so on. What operation combines "how often" with "how many bits" into an overall average?

Try by hand first: For scheme {A:"0", B:"01", C:"10", D:"11"} with frequencies A=50%, B=25%, C=20%, D=5%:

• A contributes 0.50 × 1 bit = ?
• B contributes 0.25 × 2 bits = ?
• C contributes 0.20 × 2 bits = ?
• D contributes 0.05 × 2 bits = ?
• Total = ?

Now generalize this into a function.

frequencies = {"A": 0.50, "B": 0.25, "C": 0.20, "D": 0.05}
scheme = {"A": "00", "B": "01", "C": "10", "D": "11"}
avg_bits(scheme, frequencies)  # 2.0

Compare these three prefix-free schemes on the same frequencies:

For each scheme:

1. Check it is prefix-free.
2. Compute the average bits per symbol.

Which scheme gives the shortest encoding?

Generate a random message of 1000 symbols according to the given frequencies, then measure how many bits each scheme actually produces.

Run the code above and observe which scheme produces the fewest bits on real data. Does it match the theoretical avg_bits you computed?

Scheme 2 was shorter than the fixed scheme. But is it the shortest possible?

Key insight: Give the shortest codes to the most frequent symbols. The rare symbols are used infrequently, so making their codes long barely hurts.

But how do you decide which symbols to group together? Think about it: if you had to start combining symbols into groups of two, which ones would you pair first? Why?

Once you pair two symbols, you can treat the pair as a single "super-symbol" whose frequency is the sum of its parts. Now you have a smaller problem — what do you do next?

Keep this idea in mind as you work through the exercises below.

You have four symbols with frequencies: A=50%, B=25%, C=20%, D=5%.

You want to build a binary tree where each leaf is a symbol, and you assign codes by tracing from root to leaf (0 for left, 1 for right). Symbols deeper in the tree get longer codes.

Your task: Trace the process by hand.

• Which two symbols would you combine first? Try different pairings — which gives the shortest codes?
• Now treat that pair as a single super-symbol and look at what remains. Pick two to combine again.
• Repeat until everything is merged into one tree.

Draw the tree you get. What code does each symbol end up with?

# A = ?   B = ?   C = ?   D = ?

Represent the tree using nested tuples:

• A leaf is just a string: "A", "B", etc.
• An internal node is a tuple of its two children: (left, right).

So the tree from the example is:

("A", ("B", ("D", "C")))

Translate the process you just did by hand into code. Start with (frequency, symbol) pairs and repeat the combining step until one tree remains.

build_huffman_tree({"A":0.50,"B":0.25,"C":0.20,"D":0.05})
# ("A", ("B", ("D", "C")))   (or equivalent — ties may be broken differently)

Now walk the tree recursively to assign binary codes.

Write assign_codes(tree, prefix="") that:

• If tree is a string (a leaf/symbol), return {tree: prefix}. Handle the edge case where prefix is empty (single-symbol alphabet) by returning {tree: "0"}.
• If tree is a tuple (left, right):
  • Recursively assign codes to left with prefix prefix + "0".
  • Recursively assign codes to right with prefix prefix + "1".
  • Merge and return the combined dict.

assign_codes(("A", ("B", ("D", "C"))))
# {"A": "0", "B": "10", "D": "110", "C": "111"}

Combine build_huffman_tree and assign_codes into one function.

Write huffman_scheme(frequencies) that returns the complete {symbol: bits} dict.

huffman_scheme({"A": 0.50, "B": 0.25, "C": 0.20, "D": 0.05})
# {"A": "0", "B": "10", ...}  (exact codes may vary if ties are broken differently)

Verify:

1. The scheme is prefix-free.
2. avg_bits is ≤ 2.0 (the fixed-width baseline).

Your Huffman code assigns A (50%) a 1-bit code, B (25%) a 2-bit code, D (5%) a 3-bit code. Do you see a pattern between frequency and code length?

Think about it:

• A appears 50% = 1/2 of the time and gets 1 bit. Notice: $\log_2(1/0.50) = \log_2(2) = 1$.
• B appears 25% = 1/4 of the time and gets 2 bits. Notice: $\log_2(1/0.25) = \log_2(4) = 2$.
• For a symbol with frequency $p$, the "ideal" code length is $\log_2(1/p)$.

Your challenge: If each symbol could have exactly its ideal code length $\log_2(1/p)$, what would the average bits per symbol be? Use the same weighted-average idea from avg_bits, but with the ideal lengths instead of actual code lengths.

Write entropy(frequencies) and compare it to your Huffman average. No lossless code can do better than this theoretical minimum.

entropy({"A": 0.50, "B": 0.25, "C": 0.20, "D": 0.05})
# ≈ 1.68 bits/symbol

Run the plotting helper below to compare fixed-width, Huffman, and entropy visually.

Huffman coding assigns shorter codes to more frequent symbols. Is this always the most efficient possible prefix-free encoding?

A. No — there are always better encodings that Huffman misses

B. Yes — Huffman is provably optimal among all prefix-free codes that assign a whole number of bits per symbol

C. Yes, but only for alphabets with exactly 4 symbols

D. No — fixed-length codes are always more efficient

Now put everything together into two clean functions.

Write encode(data, frequencies) that:

1. Builds the Huffman scheme from frequencies.
2. Encodes data (a string) using that scheme.
3. Returns (encoded_bits, scheme).

frequencies = {"A": 0.50, "B": 0.25, "C": 0.20, "D": 0.05}
bits, scheme = encode("AABCD", frequencies)
print(bits)    # e.g. "001010110111"  (depends on exact tree)
print(scheme)  # {"A": "0", "B": "10", ...}

Write decode(encoded_data, scheme) that:

1. Builds a reverse lookup: {bits: symbol}.
2. Walks through encoded_data one bit at a time.
3. When the accumulated bits match a codeword, emit the symbol and reset.
4. Returns the decoded string.

decode(bits, scheme) == "AABCD"   # True

Before you code: Why does the prefix-free property guarantee this works? Could two different symbols ever produce the same accumulated prefix at the same step?

Generate a 500-symbol message using the given frequencies and verify that decode(encode(message)) == message. Then measure the compression ratio.

Your encode and decode work on any alphabet and any frequencies. Try them on English-like letter frequencies.

Observe: the most frequent letters (e, t, a) get short codes (3-4 bits), while the rarest (q, z) get long codes (8+ bits). On average this saves many bits compared to fixed-width encoding.

The entropy of an alphabet with frequencies {A: 50%, B: 25%, C: 12.5%, D: 12.5%} is exactly 1.75 bits per symbol. Your Huffman code achieves exactly 1.75 bits per symbol. Is it always possible to match the entropy exactly?

A. Yes — Huffman always matches entropy exactly

B. No — this case works because the frequencies are all powers of 1/2, giving exact integer code lengths. For other frequency distributions, Huffman gets close but can't go below the entropy bound

C. No — entropy is a theoretical concept that can never be achieved

D. Yes, but only if you use more than 4 symbols

What you just invented

You just invented Huffman coding (1952), one of the most important algorithms in data compression. It is still used today inside ZIP files, JPEG images, and MP3 audio.

The key ideas you discovered:

Huffman coding is provably optimal among all codes that assign a fixed bit-string to each symbol.