Problem C: Huffman Coding

CS F364 — Assignment 1

← Back to assignment

Problem

A prefix-free binary code assigns a unique binary string (code word) to each character such that no code word is a prefix of another. This guarantees unambiguous decoding. Given a set of characters with known frequencies, the goal is to construct an optimal prefix-free code that minimises the expected number of bits per character.

You are given \(n\) distinct characters and their frequencies, followed by a message string \(S\) composed of these characters. Your program must:

  1. Build the binary tree representing the optimal prefix-free code.
  2. Output the tree in preorder (internal nodes as *, leaf nodes as the character).
  3. Generate the code word for each character.
  4. Encode the message \(S\) into a bit-string.
  5. Compute the total expected encoding length in bits (sum of frequency \(\times\) code-word length over all characters).
Input Format
  • Line 1: integer \(n\) (number of distinct characters)
  • Lines 2 to \(n+1\): char freq — a lowercase letter and its integer frequency (\(\ge 1\))
  • Line \(n+2\): string \(S\) to encode (composed only of the \(n\) characters above)
Output Format
  • Line 1: tree in preorder (internal nodes as *, leaf nodes as the character, space-separated)
  • Next \(n\) lines: char code — the Huffman code for each character (sorted alphabetically by char)
  • Line \(n+2\): the encoded bit-string for \(S\)
  • Line \(n+3\): integer — total expected encoding length in bits (sum of freq \(\times\) code-word length)
Sample

Input

6
a 45
b 13
c 12
d 16
e 9
f 5
bad

Output

* a * d * b * * c * e f
a 0
b 101
c 100
d 111
e 1101
f 1100
1010111
224

Explanation: The tree preorder reads * for internal nodes and the letter for leaves. Code lengths: a=1, b=3, c=3, d=3, e=4, f=4. Total = \(45\times1 + 13\times3 + 12\times3 + 16\times3 + 9\times4 + 5\times4 = 224\).

Download sample input