#
5.2. Prefix Codes
In
- No codeword can be a prefix of any other code.
- Otherwise, decoding is impossible!
- Uniquely decodable!
- ☺ Example 1
- a = 00, b = 1110, c = 110, d = 01, e = 1111, f = 10
- Example 2
- a = 00, b = 1100, c = 110, d = 01, e = 1111, f = 10
- ☺ Example 1
- Binary trees corresponding to prefix codes
- The code of a character c is the label of the path from the root to c.
- Decoding of an encoded file is trivial.
- Problem
- Given a file F to be encoded with a character set V = \{v_1, v_2, ..., v_n \}, find an optimal prefix binary code with a corresponding binary tree T that minimizes the cost function
- bits(T) = \Sigma_{i=1}^n{freq(v_i) \cdot depth(v_i)}
- where
freq(v_i)is the number of times v_i occurs in F, and depth(v_i) is the depth v_i of in T.
- where
- A Greedy approach successfully finds an optimal code.
