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).

C++17 Build UI License

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

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.

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

• 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.

• 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.

• 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.

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

# 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