Data Compression

Problem Statement

Data Compression Messages can be compressed with a prefix code : every character of the alphabet is given its own string of bits, and no character's bit string is a prefix of another character's. Because of that property the encoded characters can simply be run together — the decoder can always tell where one character ends and the next begins. JPEG, MP3 and DivX all rest on this idea. A prefix code is naturally described by a binary tree . Every leaf of the tree holds one character, and the code for that character is read off the path from the root down to its leaf: a 0 bit means "take the left branch", a 1 bit means "take the right branch". For example, in one particular tree the path to a is a single left branch, the path to ! is left-right-left, and the path to b is right-right-right. The complete code is character encoding a 0 ! 100 d 1010 c 1011 r 110 b 111 and the bit string 0111110010110101001111100100 therefore spells abracadabra! — the leading 0 is a , the next three 1 s are