1 基本思想

将原始时序数据转为频域数据，只保留部分能量较大的频域分量，以实现有损编码。

2 存储结构

• N：数据长度
• M：保留的频域分量个数
• 2^β：value的量化级别（离散粒度）
• id[i]：保留的频域分量索引
• s[i]：保留的频域分量值的符号
• v[i]：保留的频域分量值的绝对值
• v[i]'：|v[i]|-min{|v|}

3 编码方案

3.1 离散余弦变换：

根据预先设定的blockSize，将原始时序数据顺序划分为若干个block（最后一个block的长度可能小于blockSize）。

对每一个block都进行离散余弦变换DCT，得到一系列频域分量，每一个频域分量可以表示为索引和值两部分。在后续保留分量时，按照能量（值的平方）从高到低。

3.2 自适应量化：

由于频域分量的值是一个实数，在存储时需要量化（离散）为整数进行存储。因此，整个编码过程存在两种误差：

• 系统误差：由于舍弃低能量频域分量导致的误差；
• 量化误差：由于量化和舍入导致的误差。

根据预先指定的信噪比，总体误差是固定的。显然，如果量化等级（离散粒度）很小，每一个值量化的结果都会很大，会导致较大的空间占用；如果量化等级很大，那么在总体误差固定的情况下，会保留更多的频域分量以减小系统误差，也会导致较大的空间占用。随着量化等级的增大，总体的空间占用先减少，后增加，需要自适应的寻找合适的量化等级。

实践中，量化等级固定为2^β，β是一个步长为1的整数。先将β设置为一个较小的值，再逐步增大，直到空间占用不再下降。

3.3 索引编码：

索引序列采用分组编码的方式。每8个一组，先记录它们的最大有效位宽作为编码位宽，再将这些索引都按照同样的位宽编码。

3.4 值编码：

值序列在忽略符号的情况下，是严格降序排列的。因此，可以将前一个值的有效位宽作为后一个值的编码位宽。

4 解码方案

4.1 索引解码：

4.2 值解码：

4.3 离散余弦逆变换：

从索引序列和值序列中恢复部分频域分量，剩余分量填充为0，进行离散余弦逆变换IDCT，转为时域数据。

5 实验评估

5.1 性能对比：

对一组长度为170,000的真实气温数据，使用不同的方式进行编码压缩，结果如下：

• TS_2DIFF+GZIP是压缩比最大的无损编码压缩方式，它的空间占用远远低于PLAIN+UNCOMPRESSED，但有损编码压缩可以进一步大幅减少空间；
• 在TS_2DIFF+GZIP的基础上，可以继续应用有损的SDT压缩方法。由于该方法直接删除了大量数据点，而在查询时又没有通过插值进行恢复，因此查询开销远低于其余方法；
• FREQ+GZIP可以取得最佳的空间压缩效果，在精度损失与SDT方法相当的情况下，可以节约30%的空间占用。

5.2 参数对性能的影响：

频域编码在配置文件中包括两个参数：`freq_snr`指定了编码的信噪比；`freq_block_size`指定了编码进行时频域变换的分组大小。对上述数据，测试在不同参数下的空间占用、编码时间和解码时间：

空间占用：

• 随着SNR的增大，我们需要保存更多的频域分量，因此空间占用也不断增大；
• 在SNR较小时，增大block size可以降低空间占用，而SNR较大时，增大block size反而会增加空间占用。这是因为block size同时影响了下面两项：
  • 随着block size增大，频域分辨率提高，能量更加集中，这一效应在SNR较小时占主导；
  • 随着block size增大，索引序列的空间占用随之增大，由于SNR较大时保留的频域分量较多，这一效应占主导；

编码时间：

• 为了突出参数的影响，这里的编码时间是用于执行编码算法的时间。由于写入开销的大部分都与编码无关，这里不将其计入。
• 随着block size的增加，编码时间增加，这是因为dct算法的复杂度是O(nlogn)，在更大的block上执行会消耗更多的时间；
• 随着SNR的增大，编码时间先减后增，这是因为SNR同时影响了下面两项：
  • 随着SNR增大，在自适应量化步骤中，量化噪声更加容易超过总体噪声阈值，量化等级的搜索空间减少，进而减少该步骤的时间开销；
  • 随着SNR增大，需要编码的二进制块增大，对索引和值序列的编码会消耗更多时间；

解码时间：

• 为了突出参数的影响，这里的解码时间是用于执行解码算法的时间。由于查询开销的大部分都与解码无关，这里不将其计入。
• 随着block size的增加，解码时间增加，这是因为idct算法的复杂度是O(nlogn)，在更大的block上执行会消耗更多的时间；
• 随着SNR的增加，解码时间增加，这是因为需要解码的二进制块增大，对索引和值序列的解码会消耗更多时间。