Algorithms, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2002–2012·April 17, 2012 3:49:50 AMAlgorithmsFOUR T H EDIT IONR O B E R T S EDG EWICK K EVIN W A Y N E5.5 DATA COMPRESSION‣basics‣run-length coding‣Huffman compression‣LZW compression2‣basics‣run-length coding‣Huffman compression‣LZW compression3Data compressionCompression reduces the size of a file:•To save space when storing it.•To save time when transmitting it.•Most files have lots of redundancy.Who needs compression?•Moore's law: # transistors on a chip doubles every 18-24 months.•Parkinson's law: data expands to fill space available. •Text, images, sound, video, …Basic concepts ancient (1950s), best technology recently developed.“ Everyday, we create 2.5 quintillion bytes of data—so much that 90% of the data in the world today has been created in the last two years alone. ” — IBM report on big data (2011)4ApplicationsGeneric file compression.•Files: GZIP, BZIP, 7z.•Archivers: PKZIP.•File systems: NTFS, HFS+, ZFS.Multimedia.•Images: GIF, JPEG. •Sound: MP3.•Video: MPEG, DivX™, HDTV.Communication.•ITU-T T4 Group 3 Fax.•V.42bis modem.•Skype.Databases. Google.Message. Binary data B we want to compress.Compress. Generates a "compressed" representation C (B).Expand. Reconstructs original bitstream B.Compression ratio. Bits in C (B) / bits in B.Ex. 50-75% or better compression ratio for natural language.5Lossless compression and expansionuses fewer bits (you hope)Basic model for data compressionCompress Expandbitstream B0110110101...original bitstream B0110110101...compressed version C(B)1101011111...6Food for thoughtData compression has been omnipresent since antiquity:•Number systems. •Natural languages. •Mathematical notation.has played a central role in communications technology,•Grade 2 Braille.•Morse code.•Telephone system. and is part of modern life.•MP3.•MPEG.Q. What role will it play in the future?1Xn=11n2=⇡26braillebut rather like like everya I7Data representation: genomic codeGenome. String over the alphabet { A, C, T, G }.Goal. Encode an N-character genome: ATAGATGCATAG...Standard ASCII encoding.•8 bits per char.•8 N bits.Amazing but true. Initial genomic databases in 1990s did not use such a code!Fixed-length code. k-bit code supports alphabet of size 2k.charhexbinaryA4101000001C4301000011T5401010100G4701000111charbinaryA00C01T10G11Two-bit encoding.•2 bits per char.•2 N bits.Binary standard input and standard output. Libraries to read and write bits from standard input and to standard output.8Reading and writing binary data664CHAPTER 6 StringsBinary input and output. Most systems nowadays, including Java, base their I/O on 8-bit bytestreams, so we might decide to read and write bytestreams to match I/O for-mats with the internal representations of primitive types, encoding an 8-bit char with 1 byte, a 16-bit short with 2 bytes, a 32-bit int with 4 bytes, and so forth. Since bit-streams are the primary abstraction for data compression, we go a bit further to allow clients to read and write individual bits, intermixed with data of various types (primi-tive types and String). The goal is to minimize the necessity for type conversion in client programs and also to take care of operating-system conventions for representing data.We use the following API for reading a bitstream from standard input: public class BinaryStdInboolean readBoolean()read 1 bit of data and return as a boolean valuechar readChar()read 8 bits of data and return as a char valuechar readChar(int r)read r bits of data and return as a char value[similar methods for byte (8 bits); short (16 bits); int (32 bits); long and double (64 bits)]booleanisEmpty()is the bitstream empty?voidclose()close the bitstreamAPI for static methods that read from a bitstream on standard inputA key feature of the abstraction is that, in marked constrast to StdIn, the data on stan-dard input is not necessarily aligned on byte boundaries. If the input stream is a single byte, a client could read it 1 bit at a time with 8 calls to readBoolean(). The close() method is not essential, but, for clean termination, clients should call close() to in-dicate that no more bits are to be read. As with StdIn/StdOut, we use the following complementary API for writing bitstreams to standard output: public class BinaryStdOutvoid write(boolean b)write the specified bitvoid write(char c)write the specified 8-bit charvoid write(char c, int r)write the r least significant bits of the specified char[similar methods for byte (8 bits); short (16 bits); int (32 bits); long and double (64 bits)]voidclose()close the bitstreamAPI for static methods that write to a bitstream on standard output664CHAPTER 6 StringsBinary input and output. Most systems nowadays, including Java, base their I/O on 8-bit bytestreams, so we might decide to read and write bytestreams to match I/O for-mats with the internal representations of primitive types, encoding an 8-bit char with 1 byte, a 16-bit short with 2 bytes, a 32-bit int with 4 bytes, and so forth. Since bit-streams are the primary abstraction for data compression, we go a bit further to allow clients to read and write individual bits, intermixed with data of various types (primi-tive types and String). The goal is to minimize the necessity for type conversion in client programs and also to take care of operating-system conventions for representing data.We use the following API for reading a bitstream from standard input: public class BinaryStdInboolean readBoolean()read 1 bit of data and return as a boolean valuechar readChar()read 8 bits of data and return as a char valuechar readChar(int r)read r bits of data and return as a char value[similar methods for byte (8 bits); short (16 bits); int (32 bits); long and double (64 bits)]booleanisEmpty()is the bitstream empty?voidclose()close the bitstreamAPI for static methods that read from a bitstream on standard inputA key feature of the abstraction is that, in marked constrast to StdIn, the data on stan-dard input is not necessarily aligned on byte boundaries. If the input stream is a single byte, a client could read it 1 bit at a time with 8 calls to readBoolean(). The close() method is not essential, but, for clean termination, clients should call close() to in-dicate that no more bits are to be read. As with StdIn/StdOut, we use the following complementary
View Full Document
Unlocking...