Data Compression
Introduction, Encoder, Decoder, Example
Introduction: Encoding the neatness of zeroes and ones, "In 1951, David A. Huffman and his classmate in an electrical engineering graduate course on information theory were given the choice of a term paper or a final exam. For the term paper, Huffman's professor, Robert M. Fano, had assigned what at first appeared to be a simple problem. Students were asked to find the most efficient method of representing numbers, letters of other symbols using a binary code", From ASCII coding to Huffman coding, Using a code tree, Prefix and Huffman codes, Example, Why is Huffman coding greedy?, Header field; alternatives for storing the tree, Pseudo eof character, Adaptive Huffman coding, Adaptive Huffman - Vitter's algorithm update process; example: "abbca", FGK algorithm, Example: "eeaedeeabeeaedcf", Sibling property of a huffman tree, Flowchart for the FGK algorithm; example.
Introduction to Lempel-Ziv-Welch algorithm, Compression Algorithm and example, Decompression algorithm and example, Modified LZW depcompression algorithm, Implementation issues, Tree implementation for LZW.
Basics of Arithmetic Coding, Example: How to encode 'xyxxy'.