Elias-Fano Encoding in Rust

A Rust implementation of the Elias-Fano encoding scheme for storing monotonic sequences of integers efficiently.

Features

• Efficient storage of monotonic sequences
• O(1) access to elements
• Support for duplicate values
• Builder pattern for incremental construction
• Iterator support
• Serialization/deserialization support via serde
• No unsafe code

Usage

Add this to your Cargo.toml:

[dependencies]
ef_rs = "0.1.0"

Basic example:

use ef_rs::elias_fano::EliasFano;

// Create from a sorted sequence
let values = vec![2, 5, 5, 9];
let seq = EliasFano::from(&values);

// Access elements
assert_eq!(seq.get(0), Some(2));
assert_eq!(seq.get(1), Some(5));
assert_eq!(seq.get(2), Some(5));
assert_eq!(seq.get(3), Some(9));

// Iterate over values
let collected: Vec<_> = seq.iter().collect();
assert_eq!(collected, values);

Using the builder pattern:

use ef_rs::elias_fano::EliasFanoBuilder;

let mut builder = EliasFanoBuilder::new(10, 4);  // universe=10, count=4
builder.add(2);
builder.add(5);
builder.add(5);
builder.add(9);
let seq = builder.finalize();

assert_eq!(seq.get(0), Some(2));
assert_eq!(seq.get(1), Some(5));
assert_eq!(seq.get(2), Some(5));
assert_eq!(seq.get(3), Some(9));

Performance

The structure provides O(1) access to elements while using approximately 2n + log(u/n) bits of space, where n is the number of elements and u is the universe size (maximum value + 1).

Documentation

For detailed documentation, visit docs.rs.

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

License

This project is licensed under the MIT License - see the LICENSE file for details.