deepmesa-encoding

High-performance encoding algorithms for Rust, providing efficient implementations of various prefix and variable-length encoding schemes.

Overview

deepmesa-encoding offers a comprehensive collection of encoding algorithms optimized for performance and designed for use in data compression, information theory, and storage systems. All encoders and decoders work with the BitVector data structure from deepmesa-collections and provide consistent APIs with built-in performance metrics.

Features

• High Performance: Hand-crafted implementations optimized for speed
• Consistent API: Uniform interface across all encoding algorithms
• Memory Efficient: Uses BitVector for compact bit storage
• Comprehensive: Supports both encoding and decoding operations
• Iterator Support: All decoders implement Rust's Iterator trait
• Performance Metrics: Built-in compression ratio and statistics tracking

Supported Encoding Algorithms

Unary Encoding

Simple entropy encoding where a natural number n is represented as n ones followed by a zero.

Examples:

• 2 → 110
• 5 → 111110

Gamma Encoding

Universal coding developed by Peter Elias. Each value is encoded in two parts: a length (in unary) and an offset (binary with leading 1 removed).

Examples:

• 2 → 10_0
• 13 → 1110_101

Delta Encoding

Extended gamma coding where the length is encoded using gamma encoding instead of unary.

Examples:

• 2 → 100_0
• 13 → 10_1_101

Golomb Encoding

Parametric coding optimal for geometric distributions. Uses a tunable parameter to encode values as quotient (unary) and remainder (truncated binary).

Variable Byte Encoding

Encodes unsigned values in 8-byte chunks where the MSB indicates continuation (0) or termination (1).

Examples:

• 2 → 10000010
• 255 → 00000001_11111111

Usage

Add this to your Cargo.toml:

[dependencies]
deepmesa-encoding = "0.11.0"

Basic Encoding/Decoding Example

use deepmesa_encoding::prefix::{UnaryEncoder, UnaryDecoder};

// Create encoder and encode some values
let mut encoder = UnaryEncoder::new();
encoder.encode(2);
encoder.encode(5);
encoder.encode(1);

// Get encoding statistics
println!("Encoded {} elements", encoder.elements());
println!("Used {} bits", encoder.encoded_len());
println!("Compression ratio: {:.2}", encoder.comp_ratio());

// Create decoder and decode values
let mut decoder = UnaryDecoder::new(encoder.encoded());
assert_eq!(decoder.decode(), Some(2));
assert_eq!(decoder.decode(), Some(5));
assert_eq!(decoder.decode(), Some(1));
assert_eq!(decoder.decode(), None);

Gamma Encoding Example

use deepmesa_encoding::prefix::{GammaEncoder, GammaDecoder};

let mut encoder = GammaEncoder::new();
encoder.encode(13);
encoder.encode(8);

let mut decoder = GammaDecoder::new(encoder.encoded());
assert_eq!(decoder.decode(), Some(13));
assert_eq!(decoder.decode(), Some(8));

Delta Encoding Example

use deepmesa_encoding::prefix::{DeltaEncoder, DeltaDecoder};

let mut encoder = DeltaEncoder::new();
encoder.encode(2);
encoder.encode(13);

// Decode using iterator
let decoder = DeltaDecoder::new(encoder.encoded());
let values: Vec<u128> = decoder.collect();
assert_eq!(values, vec![2, 13]);

Golomb Encoding Example

use deepmesa_encoding::prefix::{GolombEncoder, GolombDecoder};

let param = 6; // Golomb parameter
let mut encoder = GolombEncoder::new(param);
encoder.encode(9);
encoder.encode(13);

let mut decoder = GolombDecoder::new(encoder.encoded(), param);
assert_eq!(decoder.decode(), Some(9));
assert_eq!(decoder.decode(), Some(13));

Variable Byte Encoding Example

use deepmesa_encoding::prefix::{VarByteEncoder, VarByteDecoder};

let mut encoder = VarByteEncoder::new();
encoder.encode(255);
encoder.encode(2);

// Decode multiple values at once
let decoder = VarByteDecoder::new(encoder.encoded());
let values = decoder.decode_many(2);
assert_eq!(values, vec![255, 2]);

Iterator Usage

All decoders implement Rust's Iterator trait:

use deepmesa_encoding::prefix::{GammaEncoder, GammaDecoder};

let mut encoder = GammaEncoder::new();
encoder.encode(1);
encoder.encode(4);
encoder.encode(7);

let decoder = GammaDecoder::new(encoder.encoded());
for value in decoder {
    println!("Decoded: {}", value);
}

Performance Monitoring

All encoders provide built-in performance metrics:

use deepmesa_encoding::prefix::UnaryEncoder;

let mut encoder = UnaryEncoder::new();
encoder.encode(10);
encoder.encode(5);

println!("Elements encoded: {}", encoder.elements());
println!("Total bits used: {}", encoder.encoded_len());
println!("Average bits per element: {:.2}", encoder.comp_ratio());

API Reference

Encoder Methods

All encoders provide these methods:

• new() - Create with default capacity (1024 bits)
• with_capacity(bits) - Create with specified capacity
• encode(value) - Encode a u128 value
• encoded() - Get reference to underlying BitVector
• encoded_len() - Get length in bits
• elements() - Get count of encoded elements
• comp_ratio() - Get compression ratio (bits per element)

Decoder Methods

All decoders provide these methods:

• new(bitvec) - Create decoder from BitVector
• decode() - Decode next value (mutable)
• decode_many(n) - Decode up to n values
• iter() - Get iterator for decoding

Special Cases

• GolombEncoder/GolombDecoder: Require parameter in constructor
• All values are u128 for maximum range support
• Decoders return Option<u128> (None when no more data)

Performance Characteristics

License

Dual Licensed under the MIT LICENSE or the Apache-2 LICENSE:

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT License

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Contact: rsingh@arrsingh.com Website: https://www.arrsingh.com/deepmesa-collections