CS 590N - Lossless Data Compression This course covered the state-of-the-art techniques of lossless compression as well as an overview of the underlying theory. Besides the basic compression techniques and their variants, I learnt how to evaluate the comparative strengths and weaknesses of competing techniques for particular applications in particular computing environments. Issues such as time and space requirements for compression and decompression, compression ratio, and fault tolerance were emphasized throughout the discussion. Example applications discussed ranged from bit-level modem protocols to web search engines. Mathematical preliminaries Overview of information theory Stationary and ergodic sources Source coding (unique decodability, prefix codes, Kraft-McMillan inequality) Entropy coding techniques Huffman and arithmetic coding Context-sensitive and adaptive coding Real-time coding and error propagation considerations Applications (text and lossless bilevel image compression, the JBIG standard) Dictionary techniques Static versus adaptive dictionary models Lempel-Ziv algorithms and their variants Applications (Unix Compress, GIF, V.42 bis modem protocol) Predictive coding Prediction with partial match (ppm) and variants Burrows-Wheeler transform Dynamic Markov compression Applications (CALIC, JPEG-LS) Searchable compressed documents Coding with very large or infinite alphabets Canonical Huffman codes Unary, gamma, delta, and Golomb codes Index compression for very large databases Reference material: K. Sayood, Introduction to Data Compression, 2nd ed., Morgan-Kaufmann Pub., San Francisco, CA 2000. (Textbook) D. Hankersson, G.A. Harris, and P.D., Johnson, Jr., Introduction to Information Theory and Data Compression, CRC Press, Boca Raton, FL 1997. I.H. Witten, A. Moffat, and T.C. Bell, Managing Gigabytes : Compressing and Indexing Documents and Images, 2nd ed., Morgan-Kaufmann Pub., San Francisco, CA 1999. Selected original papers.   My Grade :    A-