Data compression anhtt-fit@mail.hut.edu.vn dungct@it-hut.edu.vn Data Compression Data in memory have used fixed length for representation For data transfer (in particular), this method is inefficient. For speed and storage efficiencies, data symbols should use the minimum number of bits possible for representation. Methods Used For Compression: Encode high probability symbols with fewer bits Shannon-Fano, Huffman, UNIX compact Encode sequences of symbols with location of sequence in a dictionary PKZIP, ARC, GIF, UNIX compress, V.42bis Lossy compression JPEG and MPEG Variable Length Bit Codings Suppose ‘A’ appears 50 times in text, but ‘B’ appears only 10 times ASCII coding assigns 8 bits per character, so total bits for ‘A’ and ‘B’ is 60 * 8 = 480 If ‘A’ gets a 4-bit code and ‘B’ gets a 12-bit code, total is 50 * 4 + 10 * 12 = 320 Compression rules: Use minimum number of bits No code is the prefix of another code Enables left-to-right, unambiguous decoding Variable Length Bit Codings No code is a prefix of another For example, can’t have ‘A’ map to 10 and ‘B’ map to 100, because 10 is a prefix (the start of) 100. Enables left-to-right, unambiguous decoding That is, if you see 10, you know it’s ‘A’, not the start of another character. Variable-length encoding Use different number of bits to encode different characters. Ex. Morse code. Issue: ambiguity. SOS ? IAMIE ? EEWNI ? V7O ? Huffman code Constructed by using a code tree, but starting at the leave