FastFibonacci

Rust 库，实现了 FastFibonacci 整数压缩/解压缩算法。此外，该 crate 还提供了常规的 Fibonacci 压缩/解压缩。

简介

Fibonacci 编码 是一种整数变量长度编码，具有特殊性质：任何整数的编码都以 1（二进制）结束，并且没有编码包含 11。因此，可以在 Fibonacci 编码整数的流中使用 11 作为分隔符。

常规 Fibonacci 编码/解码按位解码，可能相当慢。FastFibonacci 编码 和 解码 一次查看 n 位，通过单个操作解码此块，可能更快。

性能

常规 Fibonacci 编码与其他 Rust 实现（例如，我从其中获取了一些代码的 fibonnaci_codec crate）的速度相当。

• Fibonacci 编码
  • 此 crate：75ms/ 1M 个整数
  • fibonnaci_codec：88ms / 1M 个整数

常规 fibonacci 解码（基于迭代器的）与其他的 fibonnaci_codec crate 的速度相当。 FastFibonacci 解码函数大约快 2 倍，但有一些固定开销（即仅在解码 许多 整数时才有效）。

• Fibonacci 解码
  • 常规解码：92ms/ 1M 个整数
  • fibonnaci_codec：108ms / 1M 个整数
  • 快速解码（u8 区段）：40ms / 1M 个整数
  • 快速解码（u16 区段）：30ms / 1M 个整数
  • 快速解码（使用迭代器）：54ms / 1M 个整数

示例

常规编码和解码

use fastfibonacci::fibonacci::{encode, decode, FibonacciDecoder};
let encoded = encode(&vec![34, 12]) ;

// Decoding
let decoded = decode(&encoded, false); // 2nd argument: shift all values by -1 (in case we wanted to encode 0 in the fibonacci encoding)
assert_eq!(decoded, vec![34,12]);

// Alternatively, we can also create an iterator (yields one decoded int at a time)
let f = FibonacciDecoder::new(&encoded, false);
assert_eq!(f.collect::<Vec<_>>(), vec![34,12])

快速解码

use fastfibonacci::fast::{fast_decode, LookupU8Vec, LookupU16Vec,get_u8_decoder };
use bitvec::prelude as bv;
let bits = bv::bits![u8, bv::Msb0; 
    1,0,1,1,0,1,0,1,
    1,0,1,0,0,1,0,1,
    0,1,1,1,0,0,1,0].to_bitvec();
// using a u8 lookup table
let table: LookupVec<u8> = LookupVec::new();
let r = fast_decode(&bits, &table);
assert_eq!(r, vec![4,7, 86]);

// using a u16 table
let table: LookupVec<u16> = LookupVec::new();
let r = fast_decode(&bits, &table);
assert_eq!(r, vec![4,7, 86]);

// using an iterator
let dec8 = get_u8_decoder(&bits, false);
assert_eq!(dec8.collect::<Vec<_>>(), vec![4,7, 86]);