Data Compression - Notes
6.1. Need for data compression
Data compression is essential to reduce the size of data for efficient storage and transmission. It is used in
various applications such as file storage, multimedia processing, internet communication, and mobile
devices.
Benefits of Data Compression:
- Saves storage space.
- Reduces bandwidth usage.
- Enhances transmission speed.
- Reduces transmission cost.
- Allows efficient use of network and system resources.
6.2. Compression basics
Compression Basics involve reducing the number of bits required to represent data.
Two main types of compression:
1. **Lossless Compression** - No data is lost; original data can be recovered.
2. **Lossy Compression** - Some data is lost; original data cannot be fully recovered.
Basic components of compression:
- **Encoder**: Compresses the data.
- **Decoder**: Reconstructs the data.
Data Compression - Notes
Conceptual Diagram:
[Original Data] -> [Encoder] -> [Compressed Data] -> [Decoder] -> [Reconstructed Data]
6.3. Lossless compression
Lossless compression techniques ensure the exact original data can be recovered.
Types of Lossless Compression:
- **Run-Length Encoding (RLE)**: Compresses sequences of repeated characters.
Example: AAAAA -> A5
- **Huffman Coding**: Assigns shorter codes to more frequent characters.
Algorithm:
1. Calculate frequency of each character.
2. Build a priority queue (min-heap).
3. Combine two lowest frequency nodes until one node remains.
4. Assign binary codes based on the tree structure.
- **LZW (Lempel-Ziv-Welch)**: Uses a dictionary of strings encountered.
Widely used in GIF, TIFF formats.
6.4. Lossy compression
Lossy compression removes some data permanently, often with little impact on perceived quality.
Data Compression - Notes
Types of Lossy Compression:
- **JPEG**: Image compression using Discrete Cosine Transform (DCT).
- **MP3**: Audio compression removing inaudible frequencies.
- **MPEG**: Video compression using motion estimation.
Use Cases:
- Multimedia streaming.
- Online image storage.
- Voice over IP (VoIP).
6.5. LZW Compression
LZW Compression (Lempel-Ziv-Welch) is a dictionary-based lossless compression algorithm.
Algorithm Steps:
1. Initialize dictionary with all possible characters.
2. Read input characters to form strings.
3. If string exists in dictionary, continue building.
4. If not, add to dictionary and output code of previous string.
5. Repeat until end of data.
Example:
Input: ABABABA
Step-by-step dictionary build and output code will show how repeated patterns are encoded efficiently.
Data Compression - Notes
Advantages:
- No need to transmit dictionary.
- Fast and simple implementation.
Applications:
- Unix compress command
- GIF, TIFF image formats