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 with lookup and lookup_next operations
• Serialization/deserialization support via serde
• No unsafe code

Usage

Add this to your Cargo.toml:

[dependencies]
ef_rs = "0.1.0"

Basic Usage

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));
assert_eq!(seq.get(4), None);  // Out of bounds

// Get sequence properties
assert_eq!(seq.size(), 4);
assert_eq!(seq.universe(), 10);  // max value + 1
assert!(!seq.is_empty());

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

Using the Builder Pattern

use ef_rs::elias_fano::EliasFanoBuilder;

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

// Add multiple values at once
let mut builder = EliasFanoBuilder::new(10, 4);
builder.add_all(&[2, 5, 5, 9]);
let seq = builder.finalize();

Iterator Operations

use ef_rs::elias_fano::EliasFano;

let values = vec![2, 5, 5, 9];
let seq = EliasFano::from(&values);
let mut iter = seq.iter();

// Basic iteration
assert_eq!(iter.next(), Some(2));
assert_eq!(iter.next(), Some(5));
assert_eq!(iter.next(), Some(5));
assert_eq!(iter.next(), Some(9));
assert_eq!(iter.next(), None);

// Lookup operations
let mut iter = seq.iter();
assert_eq!(iter.lookup(5), Some(1));  // Find first occurrence of 5
assert_eq!(iter.lookup(7), None);     // Value not found
assert_eq!(iter.index, 3);            // Iterator position updated

// Lookup next operations
let mut iter = seq.iter();
assert_eq!(iter.lookup_next(4), 1);   // Next value is 5 at index 1
assert_eq!(iter.lookup_next(6), 3);   // Next value is 9 at index 3
assert_eq!(iter.lookup_next(10), 3);  // Returns last index for values > universe

Different Input Types

use ef_rs::elias_fano::EliasFano;

// From Vec
let vec = vec![2, 5, 5, 9];
let seq1 = EliasFano::from(vec);

// From slice
let slice = &[2, 5, 5, 9];
let seq2 = EliasFano::from(slice);

// From array
let array = [2, 5, 5, 9];
let seq3 = EliasFano::from(&array);

// From different integer types
let u32_values = vec![2u32, 5, 5, 9];
let seq4 = EliasFano::from(&u32_values);

let i32_values = vec![2i32, 5, 5, 9];
let seq5 = EliasFano::from(&i32_values);

Serialization

use ef_rs::elias_fano::EliasFano;
use serde_json;

let values = vec![2, 5, 5, 9];
let seq = EliasFano::from(&values);

// Serialize to JSON
let json = serde_json::to_string(&seq).unwrap();

// Deserialize from JSON
let seq2: EliasFano = serde_json::from_str(&json).unwrap();
assert_eq!(seq, seq2);

Error Handling

use ef_rs::elias_fano::{EliasFano, EliasFanoBuilder};

// Input must be sorted
let unsorted = vec![5, 2, 7];
let result = std::panic::catch_unwind(|| {
    let _ = EliasFano::from(&unsorted);
});
assert!(result.is_err());

// Values must be within universe
let mut builder = EliasFanoBuilder::new(5, 2);
builder.add(2);
let result = std::panic::catch_unwind(|| {
    builder.add(6);  // 6 >= universe (5)
});
assert!(result.is_err());

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

Space Complexity

• For n elements with maximum value u:
  • Upper bits: n + u/2^l bits
  • Lower bits: n * l bits
  • Where l = log2(u/n)

Time Complexity

• Construction: O(n)
• Access: O(1)
• Lookup: O(log n) with binary search
• Iteration: O(1) per element

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 Apache 2.0 License - see the LICENSE file for details.