#encoding #fano #algorithm #bit #position #elias

elias-fano

An implementation of Elias-Fano encoding in Rust

11 releases (3 stable)

Uses old Rust 2015

1.1.0 Jun 5, 2019
1.0.1 Jun 5, 2019
0.2.6 Jul 18, 2018
0.1.0 Jul 15, 2018

#380 in Compression

MIT license

9KB
206 lines

Elias-Fano, in Rust

Build Status Rust Docs

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:

  • Tests
  • Example usage
  • Benchmarks, comparison with other implementations

Installation

Add the following line to your Cargo.toml:

[dependencies]
+ elias-fano = "1.1.0"

Example Usage

extern crate elias_fano;

use elias_fano::EliasFano;

fn main() {
    let sorted_array = [0, 3, 40, 1000];
    let size = sorted_array.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.

Dependencies

~84KB