Ziplet++

Important

This library is made intentionally vulnerable for learning purposes. It is NOT to be used in production environments.

Ziplet is a lightweight ASCII compression library implemented in C. It utilizes the Canonical Huffman coding algorithm to compress data, making it suitable for educational purposes and understanding the basics of lossless data compression. It typically achieves a compression rate of around 40% on ASCII text.

Algorithm Overview

Ziplet implements the standard Huffman compression algorithm, which involves the following steps:

1. Frequency Analysis: The library first scans the input data to calculate the frequency of occurrence for each character (byte).
2. Min-Heap Construction: A Min-Heap priority queue is created containing a node for each character, prioritized by its frequency.
3. Huffman Tree Building:
   • The two nodes with the lowest frequencies are extracted from the heap.
   • A new internal node is created with these two nodes as children. The frequency of this new node is the sum of the children's frequencies.
   • This new node is inserted back into the Min-Heap.
   • This process repeats until only one node remains in the heap, which becomes the root of the Huffman Tree.
4. Code Generation: The tree is traversed to determine the bit length of the code for each character. These lengths are then used to generate Canonical Huffman codes. This property ensures that the codes can be reconstructed just from the lengths, simplifying the header.
5. Compression: The input data is encoded using the generated variable-length codes.

Usage

See ziplet.h for the API definitions.

#include "ziplet.h"

// ...

size_t compressed_size;
void* compressed_data = huffman_compress(input_data, input_len, &compressed_size);

// ...

size_t decompressed_size;
void* decompressed_data = huffman_decompress(compressed_data, compressed_size, &decompressed_size);