在Rust中实现埃利亚斯-法诺

Rust中的埃利亚斯-法诺编码。

埃利亚斯-法诺编码方案是一种基于Bitset间隙压缩的单调整数准紧致压缩方法。它允许以O(1)时间复杂度在任何位置解压缩一个位。

由于它是准紧致的，因此它几乎与根据香农-哈特利定理确定的最佳理论压缩一样好。

此实现主要基于由Antonio Mallia编写的Go语言版本，可在其仓库amallia/go-ef中找到。

待办事项

• 测试
• 示例使用
• 基准测试，与其他实现比较

安装

将以下行添加到您的Cargo.toml文件中

[dependencies]
+ elias-fano = "1.1.0"

示例使用

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
}

许可证

MIT许可证，有关更多详细信息，请参阅LICENSE。