Elias-Fano, in Rust

Elias-Fano encoding in Rust.

The Elias-Fano encoding scheme is a quasi-succinct compression method for monotonic integers using gap compression on a Bitset. It allows for decompression of a bit at any position in O(1) time complexity.

Being quasi-succinct, it is therefore almost as good as the best theoretical possible compression as determined by the Shannon-Hartley theorem.

This implementation is based largely on one written in Go by Antonio Mallia, which can be found at his repository amallia/go-ef.

Todo:

• [x] Tests
• [x] Example usage
• [ ] Benchmarks, comparison with other implementations

Installation

Add the following line to your Cargo.toml: diff [dependencies] + elias-fano = "1.0.1"

Example Usage

```rust extern crate elias_fano;

use elias_fano::EliasFano;

fn main() { let sortedarray = [0, 3, 40, 1000]; let size = sortedarray.len();

let mut ef = EliasFano::new(sorted_array[size - 1], size as u64);

ef.compress(sorted_array.iter());

println!("{}", ef.value()); // 1

match ef.next() {
    Ok(val) => println!("Retrieved value: {}", val), // 3
    Err(error) => println!("Err: {}", error),        // Out of bounds
}

let _ = ef.next();
println!("{}", ef.value()); // 40

ef.reset();
println!("{}", ef.value()); // 0

let _ = ef.visit(3);
println!("{}", ef.value()); // 1000

} ```

License

MIT licensed, see LICENSE for more details.