Rust中的原始整数斐波那契编码

该软件包实现了斐波那契编码技术，用于以可变位长编码词存储整数。它实现了编码器，用于消费各种原始无符号整数类型（从 u8 到 u64）的迭代器，并实现了解码器以逆转该过程。

限制

由于编码方案的工作方式，数字 0 无法进行编码。

lib.rs:

用于使用斐波那契编码对正整数（切片）进行编码和解码的特性和函数。

斐波那契编码是一种使用可变数量的位表示连续（正）整数的方法，例如，存储两个 u32 单词时，这些单词将占用其斐波那契编码表示所需的任意数量的位。

斐波那契编码对于较小的数字比较大的数字有更好的结果：最大的32位单词可以占用多达47位，但要编码数字 1，您只需要2位。

斐波那契编码是自同步的：如果单个位被更改，一个数字可能被解码为两个（或两个数字解码为一个），但剩余的数字将被正确读取。

值范围

斐波那契编码可以表示任何可以用一个或多个斐波那契数之和表示的数字，因此可以表示任何大于1的整数，直到给定机器整数类型的范围。这意味着整数零无法进行编码。

如果您需要编码 0，建议编码加一的数字（通过升级到下一个最大的整数类型或通过不编码最大值来防止溢出），并在解码结果中减一。

示例

编码数字切片

use fibonacci_codec::Encode;

let numbers: Vec<u16> = vec![1, 50, 3003];
let encoded = &numbers.fib_encode().unwrap();
// code words: "11" (1), "001001011" (50), "000010010000100011" (3003)
// These encoded words take up 4 bytes instead of 6 (3*16 bits)!
assert_eq!(encoded.to_bytes(), [0b11001001, 0b01100001, 0b00100001, 0b00011000]);

编码零值

use fibonacci_codec::Encode;

let numbers: Vec<u16> = vec![0, 49, 3002];
let adjusted: Vec<u32> = numbers.iter().map(|n| *n as u32 + 1).collect();
let encoded = &adjusted.fib_encode().unwrap();
// code words: "11" (1), "001001011" (50), "000010010000100011" (3003)
// These encoded words take up 4 bytes instead of 6 (3*16 bits)!
assert_eq!(encoded.to_bytes(), [0b11001001, 0b01100001, 0b00100001, 0b00011000]);

参考资料

• 维基百科
• Fraenkel, Aviezri S.; Klein, Shmuel T. (1996). "鲁棒通用完备码用于传输和压缩"