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
9KB
206 lines
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:
- 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