rust-gd：广义去重的Rust实现

Rust实现的广义去重（GD），基于多种纠错码。

这是对一种新颖的数据去重方法（称为广义去重，GD）的实现（和一定程度的扩展）。GD的原概念是由丹麦奥尔胡斯大学的一个小组提出的，由D. E. Lucani教授领导。

• Vestergaard, Rasmus, Qi Zhang, and Daniel E. Lucani. "Generalized deduplication: bounds, convergence, and asymptotic properties." 2019 IEEE Global Communications Conference (GLOBECOM). IEEE, 2019.
• Vestergaard, Rasmus, Daniel E. Lucani, and Qi Zhang. "Generalized deduplication: Lossless compression for large amounts of small IoT data." European Wireless 2019; 25th European Wireless Conference. VDE, 2019.
• 等等。

使用方法

将以下内容添加到您的Cargo.toml中，直接从GitHub导入

[dependencies]
rust-gd = { git = "https://github.com/junkurihara/rust-gd.git" }

或从crates.io导入

[dependencies]
rust-gd = "*" // or appropriate version

然后，在您的.rs文件中添加use。

use rust_gd::*;

示例

注意：压缩率强烈依赖于数据对齐和数据结构。因此，您应根据给定数据的特性仔细选择参数。.

基于$\mathrm{GF}(2^8)$上的Reed-Solomon码的GD

use rust_gd::*;

let to_be_deduped: &[u8] =
    "寿限無(じゅげむ)寿限無(じゅげむ)五劫(ごこう)のすりきれ海砂利(かいじゃり)padpadpadpadpadpadpadpad".to_string().repeat(128).as_bytes()

let code_len = 128; // codeword length over GF(256), i.e., N in (N, K) RS code
let msg_len = 124;  // message length over GF(256), i.e., K in (N, K) RS code
let dict_size = 127; // max entry size of a dictionary used in GD process

// GD instance for deduplication (compress)
let mut gd_dedup = GD::ReedSolomon(code_len, msg_len).setup(dict_size).await.unwrap(); // Async API

// GD instance for duplication (decompress)
let mut gd_dup = GD::ReedSolomon(code_len, msg_len).setup(dict_size).await.unwrap(); // Async API

// struct Deduped = {pub data: Vec<u8>, pub last_chunk_pad_bytelen: usize}
let deduped: Deduped = gd_dedup.dedup(to_be_deduped).await.unwrap(); // Async API
println!("> Deduped data size is {} bytes", x.data.len());

let duped: Vec<u8> = gd_dup.dup(&deduped).await.unwrap(); // Async API.
println!("> Duped size {} bytes", y.len();

assert_eq!(duped, words);

在GD与RS码中，可以通过采用一种错误对齐的方法来使用。

// Linear transformation matrix used for error-alignment. This must be nonsinglar.
let trans: [&[u8; 4]; 4] = [
      &[1, 0, 0, 0],
      &[1, 1, 1, 4],
      &[1, 1, 3, 0],
      &[1, 2, 0, 0],
    ];

// Instantiation
let mut gd_dedup = GD::ReedSolomon(4, 3).setup(15).await.unwrap();
let mut gd_dup = GD::ReedSolomon(4, 3).setup(15).await.unwrap();

// Set error alignment
let res_dedup = gd_dedup.set_error_alignment(trans).await; // this simply returns Result<()>
let res_dup = gd_dup.set_error_alignment(trans).await;   // this simply returns Result<()>
assert!(res_dedup.is_ok());
assert!(res_dup.is_ok());

// then use gd instances to deduplicate/duplicate data as above.

有关基于RS码的实现详细设计和基本错误对齐思想的详细信息，请参阅DESIGN.md。

基于汉明码的GD

let hamming_deg = 4;         // Degree m of (2^m - 1, 2^m - m -1) Hamming code
let hamming_dict_size = 511; // max entry size of a dictionary used in GD process

let to_be_deduped: &[u8] =
    "寿限無(じゅげむ)寿限無(じゅげむ)五劫(ごこう)のすりきれ海砂利(かいじゃり)padpadpadpadpadpadpadpad".to_string().repeat(128).as_bytes()

// GD instance for deduplication (compress)
let mut gd_dedup = GD::Hamming(hamming_deg).setup(hamming_dict_size).await.unwrap(); // Async API

// GD instance for duplication (decompress)
let mut gd_dup = GD::Hamming(hamming_deg).setup(hamming_dict_size).await.unwrap(); // Async API

// struct Deduped = {pub data: Vec<u8>, pub last_chunk_pad_bytelen: usize}
let deduped: Deduped = gd_dedup.dedup(to_be_deduped).await.unwrap(); Async API
println!("> Deduped data size is {} bytes", x.data.len());

let duped: Vec<u8> = gd_dup.dup(&deduped).await.unwrap(); // Async API.
println!("> Duped size {} bytes", y.len();

我们的实现中的编码

目前，我们的GD实现仅基于汉明和Reed-Solomon（RS）码。基于RS码的GD将数据块作为字节流处理。另一方面，基于汉明的GD将数据块作为比特流服务。

对于使用汉明码实现的GD，库中的错误纠正码libecc使用汉明码，其码度为$m = 3$，即码长$n = 2^m - 1 = 7$。然而，$m = 3$的汉明码不能作为基于汉明的GD的基本线性码。这是因为码长，即$n=7$位，不足以去重基于“字节”的数据。为了合理地去重基于字节的数据，需要字节对齐。因此，我们省略了$m = 3$，并考虑参数$m \geq 4$。

字节对齐：我们的实现采用一种编码方法，将消息序列按字节为单位进行分块。例如，如果使用$(15, 11)$汉明码，2字节的消息将分为两个1字节（= 8位）序列，并对每个序列填充$15-8=7$个零，将其作为15位汉明码码字处理。

待办事项

以下内容应予以考虑以实现。

• 去重性能基准测试

• 数学运算优化

• 使用PRNG（Yggdrasil论文）进行删除和偏差

• Golomb-Rice码

注意事项

目前，此解决方案应考虑适用于研究和实验，在用于生产应用程序之前，需要进一步进行代码和安全审查。

许可证

在MIT许可证下授权，请参阅LICENSE文件。