Data Compression Algorithms

This repository contains implementations of various data compression algorithms developed as course assignments. The projects cover both lossless and lossy compression techniques.

Authors

• Mennat-Allah Abdallah Helmi (ID: 20231178)
• Roaa Mohamed Sayed (ID: 20230142)
• Olaa Ghoniem (ID: 20231232)

Assignments Overview

1. LZ77 Compression

Directory: 01-LZ77/

Implementation of the LZ77 (Lempel-Ziv 77) sliding window compression algorithm.

• Type: Lossless compression
• Technique: Dictionary-based compression using sliding window
• Features:
  • Configurable window size and lookahead buffer
  • Both compression and decompression functionality
  • Interactive command-line interface

Usage:

python LZ77-20231232-20231178-20230142.py

---

2. Huffman Coding

Directory: 02-Huffman/

Implementation of Huffman coding algorithm for optimal prefix-free encoding.

• Type: Lossless compression
• Technique: Statistical/Entropy-based compression
• Features:
  • Automatic frequency analysis
  • Entropy calculation
  • Binary file output
  • Verification of compression/decompression

Usage:

python Huffman-20231232-20231178-20230142.py

Input: Place your text in input.txt
Output: compressed.bin and decompressed.txt

---

3. Predictive Coding (PC)

Directory: 03-Predictive-Coding/

Implementation of predictive coding for image compression using adaptive 2D prediction.

• Type: Lossy compression
• Technique: Predictive coding with quantization
• Features:
  • Adaptive 2D pixel prediction
  • Configurable quantization levels
  • Support for grayscale and RGB images
  • Compression ratio calculation
  • MSE and PSNR metrics

Usage:

python PC-20231232-20231178-20230142.py

Supported formats: JPG, PNG, WEBP

---

4. Vector Quantization (VQ)

Directory: 04-Vector-Quantization/

Implementation of Vector Quantization using the LBG (Linde-Buzo-Gray) algorithm.

• Type: Lossy compression
• Technique: Vector quantization with k-means clustering
• Features:
  • LBG algorithm for codebook generation
  • GUI interface for easy usage
  • Configurable block size and codebook size
  • Visual comparison of original and compressed images
  • MSE calculation

Usage:

# Command-line version
python vectormain.py

# GUI version
python gui.py

---

Installation

Requirements

pip install numpy pillow matplotlib opencv-python

Or use the provided requirements file:

pip install -r requirements.txt

---

Repository Structure

data-compression-algorithms/
├── README.md
├── requirements.txt
├── 01-LZ77/
│   ├── README.md
│   └── LZ77-20231232-20231178-20230142.py
├── 02-Huffman/
│   ├── README.md
│   ├── Huffman-20231232-20231178-20230142.py
│   └── input.txt (sample)
├── 03-Predictive-Coding/
│   ├── README.md
│   ├── PC-20231232-20231178-20230142.py
│   └── sample-images/
│       ├── RGB.webp
│       ├── RGB2.jpg
│       └── greyScale.jpg
└── 04-Vector-Quantization/
    ├── README.md
    ├── vectormain.py
    ├── gui.py
    └── app.py

---

Compression Techniques Comparison

Algorithm	Type	Best For	Compression Ratio	Quality Loss
LZ77	Lossless	Text, repetitive data	Medium	None
Huffman	Lossless	Any data with variable frequency	Medium-High	None
Predictive Coding	Lossy	Images	High	Configurable
Vector Quantization	Lossy	Images	Very High	Moderate

---

Learning Outcomes

Through these assignments, we implemented and analyzed:

• Dictionary-based compression (LZ77)
• Statistical compression (Huffman)
• Predictive techniques for image compression
• Clustering-based vector quantization
• Trade-offs between compression ratio and quality
• Performance metrics (MSE, PSNR, compression ratio)

---

License

This project was developed for educational purposes as part of a Data Compression course.

---

Contributing

This repository contains completed course assignments. If you're working on similar assignments, please use this as a reference only and develop your own solutions.