Algorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2009·January 26, 2010 8:42:01 AM5.5 Data Compression‣basics‣run-length encoding‣Huffman compression‣LZW compression2Data 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.“ All of the books in the world contain no more information than is broadcast as video in a single large American city in a single year. Not all bits have equal value. ” — Carl Sagan3ApplicationsGeneric file compression.•Files: GZIP, BZIP, BOA.•Archivers: PKZIP.•File systems: NTFS.Multimedia.•Images: GIF, JPEG. •Sound: MP3.•Video: MPEG, DivX™, HDTV.Communication.•ITU-T T4 Group 3 Fax.•V.42bis modem.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.4Lossless compression and expansionuses fewer bits (you hope)Basic model for data compressionCompress Expandbitstream B0110110101...original bitstream B0110110101...compressed version C(B)1101011111...5Food for thoughtData compression has been omnipresent since antiquity:•Number systems. •Natural languages. •Mathematical notation.has played a central role in communications technology,•Braille.•Morse code.•Telephone system. and is part of modern life.•MP3.•MPEG.Q. What role will it play in the future?6‣binary I/O‣genomic encoding‣run-length encoding‣Huffman compression‣LZW compressionBinary standard input and standard output. Libraries to read and write bits from standard input and to standard output.7Reading and writing binary data664CHAPTER 6 Q 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 Q 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 output8Writing binary dataDate representation. Different ways to represent 12/31/1999.Four ways to put a date onto standard
View Full Document
Unlocking...