High-Performance Algorithmic Compressor

A modular C++17 data compression engine and interactive Terminal User Interface (TUI) utilizing a bzip2-style transformation pipeline (Burrows-Wheeler Transform, Move-To-Front, Run-Length Encoding, and Canonical Huffman Coding).

---

📌 Performance Benchmark

Tested on a 100 KB structured test file using the built-in FTXUI pipeline monitor:

Metric	Value
Original Input Size	102,400 Bytes (~100 KB)
Compressed Output Size	651 Bytes
Space Savings	99.36%
Execution Time	14.11 ms
Decompression Speed	~7.25 MB/s

---

🏗️ Algorithmic Architecture

The compressor transforms raw byte streams across 5 sequential stages to maximize information density before writing bit-aligned streams:

               [ Raw File Input ]
                        │
                        ▼
         ┌──────────────┴──────────────┐
         │    BWT (Burrows-Wheeler)    │  ──> Reorders characters to cluster identical bytes
         └──────────────┬──────────────┘
                        │
                        ▼
         ┌──────────────┴──────────────┐
         │     MTF (Move-To-Front)     │  ──> Converts byte clusters into zero-heavy small integer indices
         └──────────────┬──────────────┘
                        │
                        ▼
         ┌──────────────┴──────────────┐
         │      RLE (Run-Length)       │  ──> Collapses sequential index repetitions (runs of 0s)
         └──────────────┬──────────────┘
                        │
                        ▼
         ┌──────────────┴──────────────┐
         │      Canonical Huffman      │  ──> Generates optimal variable-length prefix bit-codes
         └──────────────┬──────────────┘
                        │
                        ▼
         ┌──────────────┴──────────────┐
         │      BitIO Serializer       │  ──> Writes bit-packed output header & payload (Magic: 0x31435048)
         └─────────────────────────────┘

1. Burrows-Wheeler Transform (BWT): Lexicographically sorts all cyclic rotations of the input to move identical symbols adjacent to one another without losing original positional context.
2. Move-To-Front (MTF) Transform: Exploits localized character clusters generated by BWT by replacing symbols with their current index in a dynamically updated 256-byte alphabet array.
3. Run-Length Encoding (RLE): Compacts long runs of repeated indices—particularly the long sequences of zeroes produced by MTF—into byte-count pairs.
4. Canonical Huffman Coding: Computes entropy bit lengths based on symbol frequencies and constructs prefix-free canonical trees for minimal header overhead.
5. Custom BitIO: Handles unaligned bit-level read and write operations using BitWriter and BitReader abstractions.

---

📊 Optimal File Type Suitability

The effectiveness of BWT-based pipelines depends heavily on pattern repetition and byte locality:

🟢 Best Performing File Types

• Log Files & System Dumps (.log, .txt): Highly repetitive timestamps, IP addresses, and log levels compress exceptionally well (>90% savings).
• Structured Data Formats (.json, .xml, .csv, .html): Repeated key names, syntax tags, and whitespace collapse significantly after BWT sorting.
• Uncompiled Source Code (.cpp, .py, .js): Language keywords and repeated function identifiers yield high compression ratios.

🟡 Moderately Compressed File Types

• Prose & Plain Text (.md, .doc): Natural language exhibits standard character frequencies, achieving ~50%–70% savings.
• Uncompressed Audio/Bitmaps (.bmp, .wav): High spatial locality yields decent ratios, though dedicated audio/image codecs are superior.

🔴 Unsuitable File Types

• Pre-Compressed Archives (.zip, .gz, .7z, .tar.xz): Already near maximum Shannon entropy ($H \approx 8$ bits/byte); further transformation can slightly increase file size due to header overhead.
• Encrypted Files & Media (.mp4, .mp3, .png, .jpg): Pseudo-random bit distributions eliminate repeating sequences required by BWT.

---

⚔️ Comparison with Industry-Standard Compressors

Compressor	Pipeline / Algorithm	Compression Ratio	Compression Speed	Memory Footprint	Primary Use Case
This Engine (HPC)	BWT + MTF + RLE + Canonical Huffman	Very High (on text/logs)	Moderate	Low ($\mathcal{O}(N)$ RAM)	Academic baseline, modular pipeline demo
bzip2	BWT + MTF + RLE + Huffman	Very High	Slow	Moderate	Maximum ratio for text & software tarballs
gzip	LZ77 + Huffman (DEFLATE)	Moderate–High	Fast	Very Low	HTTP streaming & general archive storage
zstd (Zstandard)	Finite State Entropy (FSE) + LZ77	High	Extremely Fast	Configurable	Modern web assets, database storage
LZ4	LZ77 variant	Low–Moderate	Blazing Fast (>1 GB/s)	Minimal	Real-time memory/packet compression

---

🛠️ Build & Installation

Prerequisites

• Compiler: GCC ($\ge$ 8.0) or Clang ($\ge$ 7.0) with C++17 support
• Build System: CMake ($\ge$ 3.15)
• OS: Linux / macOS / WSL

Compilation Steps

# 1. Clone repository
git clone https://github.com/YOUR_USERNAME/compressor.git
cd compressor

# 2. Configure build directory (fetches FTXUI automatically via CMake FetchContent)
cmake -B build

# 3. Build executable
cmake --build build

# 4. Launch interactive terminal interface
./build/compressor