Data Compression

Problem Statement

Data Compression Problem Description A prefix code assigns to every character of an alphabet a distinct string of bits, chosen so that no character's bit string is a prefix of another character's bit string. Because of that property a message can be compressed by simply concatenating the bit strings of its characters, and the result can still be read back unambiguously. Such codes are used by many compressed formats, including JPEG for images and MP3 for music. A prefix code is described by a binary tree. Every node of the tree is either an internal node with exactly two children, or an external node (a leaf) that carries one character. The bit string of a character is the sequence of branches taken on the path from the root down to the leaf holding that character: a 0 bit means "take the left branch" and a 1 bit means "take the right branch". A character sitting at depth d therefore has a bit string of length d . The tree itself is supplied as its preorde