Data Compression
by Shashank Gaurav
1. Introduction
1.1. If compression and decompression are done in I/O processor, less time is required to move data to or from storage subsystem, freeing I/O bus for other work
2. Entropy
2.1. Entropy is the measure of information content in a message. Messages with higher entropy carry more information than messages with lower entropy.
3. Methods
3.1. Data compression is about storing and sending a smaller number of bits. There’re two major categories for methods to compress data: lossless and lossy methods
4. Run-length encoding
4.1. Simplest method of compression. The method can be more efficient if the data uses only 2 symbols (0s and 1s) in bit patterns and 1 symbol is more frequent than another
5. Huffman Coding
5.1. Assign fewer bits to symbols that occur more frequently and more bits to symbols appear less often. There’s no unique Huffman code and every Huffman code has the same average code length.
6. Lempel Ziv Compression
6.1. Extract the smallest substring that cannot be found in the remaining uncompressed string. Store that substring in the dictionary as a new entry and assign it an index value Substring is replaced with the index found in the dictionary Insert the index and the last character of the substring into the compressed string
7. Lossy Compression Methods
7.1. Used for compressing images and video files (our eyes cannot distinguish subtle changes, so lossy data is acceptable). These methods are cheaper, less time and space.
