optimization • Expert

Lossless String Compression: RLE, Huffman & Burrows-Wheeler

Lossless compression algorithms reduce string storage: Run-Length Encoding (RLE) compresses contiguous repeats, Huffman Coding assigns variable-length prefix codes based on entropy, and BWT groups identical characters together.

Intuitive Mental Model

Morse Code: Common letters like 'E' get a short single dot (.), while rare letters like 'Q' get long dashes (--.-), minimizing the total telegraph wire time.

C / TypeScript ImplementationHardware & Algorithmic Standard

// Run-Length Encoding (RLE):
// Input:  "WWWWWWAAAAAABBB"
// Output: "6W6A3B" (15 chars compressed to 6 chars!)

// Huffman Optimal Prefix Code:
// Frequent char 'a' (50% freq) -> Code: "0" (1 bit)
// Rare char 'z' (1% freq) -> Code: "1101" (4 bits)

Key Architectural Takeaways

•Shannon Entropy Limit: Sets the theoretical minimum average bit length per symbol for lossless compression.
•Deflate (gzip/zlib): Combines LZ77 sliding window dictionary matching with Huffman coding.

Common Coding Mistake

Applying RLE to random uncompressed text without repeating runs, which doubles the file size.

Optimal Solution

Use BWT (Burrows-Wheeler Transform) to group identical characters before RLE.