tsz :: 紧凑整数时间序列压缩

适用于在空间受限系统上进行位打包的嵌入式系统时间序列整数数据的可移植实现。

灵感来源于Delta编码、IC FIFO压缩和Gorilla时间戳压缩。 https://www.vldb.org/pvldb/vol8/p1816-teller.pdf

优缺点

✅ tsz 被设计为重度依赖Delta和Delta-delta压缩。正如Gorilla在实践中所展示的，以相同方式改变的数据点可以很好地压缩（96%的时间戳可以在Gorilla块中用1位表示）。变化率低的周期性积分数据，如嵌入式传感器数据，通常会遵循与由均匀时钟间隔生成的时间戳相同的压缩模式。

✅ tsz 被设计为利用IC产生的积分数据模式，这些IC在一段时间内以相似的变化幅度生成一致的位宽整数数据。

✅ tsz 被设计为在32位Cortex-M上压缩并生成帧包，这在嵌入式生态系统之外会被认为是非常小的。它与（并且在64位上更快）兼容，并限制了压缩数据的大小。

✅ tsz 被设计为生成半字节对齐的词，这些词可以与LZ4或ZSTD等二次压缩算法一起工作。

❌ tsz 并未设计为最佳处理振荡变化或不规则事件时间流，但它可以编码这些信息，效果与未压缩数据相当。

❌ tsz 并未设计为处理浮点数或定点数。定点数的使用是功能的但不是最佳的，浮点数不受支持。

❌ tsz 并未设计为优化完美可预测的数据。现实生活中的仪器有一些非零噪声，这通常阻止完美的线性。

❌ tsz 并未设计为优先考虑（解）压缩速度，而不是内存使用或压缩率。

接口

tsz 接口设计得尽可能简单，以实现尽可能多的内联和静态分发。它使用过程宏来生成必要的特性和结构体，将行主序数据压缩成列主序字节，并将列主序字节解压缩成列主序或行主序数据。

// Use a procedural macro to generate a compressor and decompressor for a row struct
mod abcd {
    use tsz_compress::prelude::*;
    #[derive(Copy, Clone, CompressV2, DecompressV2)]
    pub struct AbcdRow {
        pub ts: i64,
        pub a: i8,
        pub b: i16,
        pub c: i32,
        pub d: i64,
    }

    pub use compress::AbcdRowCompressorImpl;
    pub use decompress::AbcdRowDecompressorImpl;
}

// Expose the structs you want to use
use abcd::AbcdRow;
use abcd::compress::AbcdRowCompressorImpl;
use abcd::decompress::AbcdRowDecompressorImpl;


// Initialize a compressor with preallocated space, using alloc::vec::Vec internally
let mut compressor = TestRowCompressorImpl::new(32);

// Compress all the rows you want
compressor.compress(TestRow { ts: 0, a: 1, b: 2, c: 3, d: 4 });
assert!(compressor.row_count() == 1);

// Finalize the compression, flushing the compressor's pending bits
let bytes = c.finish();

// Initialize the decompressor
let mut decompressor = TestRowDecompressorImpl::new();

// Decompress the bit buffer
decompressor.decompress(&bytes).unwrap();

// Access data by column
let a = decompressor.col_a();

// Rotate the data back to row-major
let rows= decompressor.rows();

如果您想压缩到现有的缓冲区，可以使用 finish_into(&mut vec_buf) 方法来避免分配新的缓冲区。如果需要，它将通过预留正好所需的额外空间来继续追加到缓冲区。

let mut compressor = TestRowCompressorImpl::new(32);
let mut bytes: Vec<u8> = Vec::new();
bytes.extend([0xDE, 0xAD, 0xBE, 0xEF]);
compressor.finish_into(&mut bytes);
assert_eq!(vec_buf[0], 0xDE);
assert_eq!(vec_buf[1], 0xAD);
assert_eq!(vec_buf[2], 0xBE);
assert_eq!(vec_buf[3], 0xEF);

基准测试

有关更多信息，请查看 tsz-bench 中的基准测试。

TSZ V2 压缩方案

这可以通过 CompressV2 和 DecompressV2 过程宏访问。默认情况下，使用增量方案，增量-增量工作正在进行中。增量对于某些噪声样本使系统略带不可预测性的系统可能更好。当增量-增量通常为0时，增量-增量可以与第二次压缩相结合，从而实现更高的可压缩性。

压缩方案在每个词之前包含一个单比特，以指示以下内容

• 是一个截断的二进制编码标题，指示后续比特数和从上一个增量到增量-增量的比特数。每个增量-增量是zigzag编码的

  1. 0, 00, 1 比特
  2. 0, 01, 5 比特
  3. 0, 10, 9 比特
  4. 0, 110, 16 比特
  5. 0, 111, 64 比特

• 以下是一个截断的二进制编码标题，指示下一个32比特中比特打包的增量（不是增量-增量）的数量。每个增量都是zigzag编码的

  1. 1, 10, 1, 1 样本（64比特）
  2. 1, 01, 1, 1 样本（32比特）
  3. 1, 00, 补0, 2个样本（16比特）
  4. 1, 01, 补000, 3个样本（10比特）
  5. 1, 10, 补0, 4个样本（8比特）
  6. 1, 110, 8个样本（4比特）
  7. 1, 111, 补00, 10个样本（3比特）

在更新的方案中，第二次压缩算法（如LZ4或ZSTD）可显著提高压缩比率。一个空间优化的第二次压缩算法将包括熵编码，最小单词大小为4比特。所有标题和增量比特序列都是4比特对齐的，字节倾向于0000以表示常数斜率，以及1111以表示在+-3范围内连续的10个数据点。增量zigzag编码中的值也可能包括前导0的字节。

TSZ V1 压缩方案

这可以通过 DeltaEncodable、Compressible 和 Decompressible 过程宏访问。如果您有高度可预测的数据或不想使用另一个算法进行第二次压缩，这仍然可能是一个合适的选择。然而，该方案必须按比特操作（使用 bitvec），这比TSZ V2中使用的半字节对齐的优化压缩结构要慢。

初始压缩方案实现包括

1. 第一行的每个列的全值的VLQ编码
2. 第一行到第二行的增量VLQ编码
3. 对于后续的每一行，一个一元编码标题，指示后续比特数和从上一个增量到增量-增量的比特数。
   1. 标题 0, 0 比特
   2. 标题 10, 4 比特
   3. 标题 110, 7 比特
   4. 标题 1110, 9 比特
   5. 标题 11110, 12 比特
   6. 标题 111110, 15 比特
   7. 标题 1111110, 18 比特
   8. 标题 11111110, 32 比特
   9. 标题 111111110, 64 比特

V1的示例

以下示例编码了2个时间戳和4个值。第一个时间戳是SoC的运行时间毫秒。第二个时间戳是UTC微秒。这些值是4个int16_t数据通道，缓慢增加并偶尔重置。本例中的数据以1赫兹的频率收集。

本例中压缩比降低至3.2倍，如果继续示例，每251字节的数据包将降低至5.9倍。

| soc_bits | utc_bits | channel0_bits | channel1_bits | channel2_bits | channel3_bits | | -------- | -------- | ------------- | ------------- | ------------- | ------------- | --- | | 16 | 64 | 8 | 8 | 16 | 16 | | 17 | 40 | 6 | 6 | 6 | 1 | 6 | | 1 | 10 | 1 | 6 | 6 | 6 | | 6 | 10 | 6 | 6 | 1 | 6 | | 6 | 10 | 6 | 1 | 1 | 1 |

请参阅文档以获取更多信息。

最佳压缩示例

为了获得最大的压缩比，整数线性序列，如递增整数，其差分-差分为0。在这个简化示例中，我们有最小的差分-差分，0。第二次使用LZ4或ZSTD压缩，将基本上压缩为零。同样，差分-差分为0相当于编码一个常数差分，这也将通过第二次遍历进行高度压缩。

性能配置

V2压缩方案包括在原生位宽上对每一行进行数学计算。在32位微控制器上，i64数学可能非常昂贵，因此内部数据结构使用usize存储位。要在32位系统上使用i64，请指定不会从样本到样本溢出的位宽。您可以像这样明确选择要使用的位宽

use tsz_compress::prelude::*;
#[derive(Copy, Clone, CompressV2, DecompressV2)]
pub struct AbcdRow {
    #[tsz(delta = "i32")]
    pub ts: i64,
    pub a: i8,
    pub b: i16,
    #[tsz(delta = "i16")]
    pub c: i32,
    #[tsz(delta = "i8")]
    pub d: i64,
}

这允许前两行使用正常的列宽，然后所有delta/delta-delta指令在指定的位宽上操作。例如，第一个和第二个行上的纪元时间戳可能为8字节，然后50Hz模拟前端将使用32位计算大约20000微秒的差分，其余压缩将使用32位。