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位系统兼容（并在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时，增量-增量与第二次遍历压缩结合使用时，可压缩性会更高。

压缩方案在每个单词之前包含一个位，用于指示以下内容是一个截断的二进制编码头，指示后续位数和从上一个增量到增量-增量的位数。

• 以下是一个截断的二进制编码头，指示下一个32位中位打包增量（不是增量-增量）的数量。每个增量都是Zigzag编码的

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

• 以下是一个截断的二进制编码头，指示下一个32位中位打包增量（不是增量-增量）的数量。

  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数据通道。本例中的数据以1Hz的频率收集。

在此示例中，压缩比降低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 |

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

最佳压缩示例

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

性能配置

V2压缩方案包括每行在原生位宽上发生的数学运算。i64数学在32位微控制器上可能非常昂贵，因此内部数据结构使用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模拟前端将具有约20000微秒的delta，其余压缩使用32位。