Prefix Codes: Tree Construction, Decoding, and Analysis

Problem Statement

Prefix Codes: Tree Construction, Decoding, and Analysis A prefix code assigns every character of an alphabet a distinct string of bits, chosen so that no character's code is a prefix of another's. Such codes are the heart of most compression schemes — JPEG for images, MP3 for music, DivX for video — because frequent characters can be given short codes and rare ones long codes. A prefix code is naturally described by a binary tree. Every external node (leaf) holds one character; every internal node holds no character and has exactly two children. The code for a character is the sequence of branches taken on the path from the root down to its leaf: a 0 bit means go left , a 1 bit means go right . For example, this encoding tree *a**!*dc*rb gives the code table character bits encoding a 1 0 ! 3 100 d 4 1010 c 4 1011 r 3 110 b 3 111 Because no code is a prefix of another, codes can simply be run together. The bit string 0111110010110101001111100100 splits uniquely as 0 111 110 0 1011 0 101