在 C 中压缩一系列接近的数字

Question

我有多个时间序列，每个时间序列包含 400 个彼此接近的数字序列。我有成千上万的时间序列；每个都有自己的一系列接近数字。

TimeSeries1 = 184.56, 184.675, 184.55, 184.77, ...

TimeSeries2 = 145.73, 145.384, 145.96, 145.33, ...

TimeSeries3 = -126.48, -126.78, -126.55, ...

我可以为每个时间序列存储一个 8 字节的双精度数，因此对于 大多数 个时间序列，我可以通过乘以 100 并取当前值和先前值的增量。这是我的 compress/decompress 代码：

struct{
    double firstValue;
    double nums[400];
    char compressedNums[400];
    int compressionOK;
} timeSeries;

void compress(void){
    timeSeries.firstValue = timeSeries.nums[0];
    double lastValue = timeSeries.firstValue;
    for (int i = 1; i < 400; ++i){ 
        int delta = (int) ((timeSeries.nums[i] * 100) - (lastValue* 100));

        timeSeries.compressionOK = 1;
        if (delta > CHAR_MAX || delta < -CHAR_MAX){
            timeSeries.compressionOK = 0;
            return;
        }
        else{       
            timeSeries.compressedNums[i] = (char) delta;
            lastValue = timeSeries.nums[i];
        }
    }
}   

double decompressedNums[400];    

void decompress(void){
    if (timeSeries.compressionOK){
        double lastValue = timeSeries.firstValue;

        for (int i = 1; i < 400; ++i){
            decompressedNums[i] = lastValue + timeSeries.compressedNums[i] / 100.0;
            lastValue = decompressedNums[i];
        }
    }
}

我可以容忍一些有损，每个数字大约 0.005。但是，我得到的损失超出了我所能容忍的范围，尤其是因为其中一个压缩系列的精度损失继续存在并导致损失增加。

所以我的问题是：

有什么我可以改变的来减少损耗吗？
是否有完全不同的压缩方法可以与这个 8 比 1 的比率相媲美或更好？

Answer 1

您可以通过计算增量而不是根据前一个元素的精确值，而是根据前一个元素的计算近似值（即增量之和）来避免精度的缓慢漂移。这样，您将始终获得最接近下一个值的近似值。

就个人而言，我会为此目的使用整数运算，但浮点运算也可能没问题，因为浮点即使不精确也是可重现的。

Answer 2

查看存储在内存中的值：

184.   == 0x4067000000000000ull
184.56 == 0x406711eb851eb852ull

前两个字节相同，但后六个字节不同。

对于整数增量，乘以 128 而不是 100，这将得到小数部分的 7 位。如果增量对于一个字节来说太大，则使用三字节序列 {0x80, hi_delta, lo_delta}，因此 0x80 用作特殊指示符。如果增量恰好为 -128，则为 {0x80, 0xff, 0x80}。

Answer 3

您应该在转换为 int 之前对值进行舍入以避免出现问题，如此代码所示。

#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

enum { TS_SIZE = 400 };

typedef struct
{
    double firstValue;
    double nums[TS_SIZE];
    signed char compressedNums[TS_SIZE];
    int compressionOK;
} timeSeries;

static
void compress(timeSeries *t1)
{
    t1->firstValue = t1->nums[0];
    double lastValue = t1->firstValue;
    for (int i = 1; i < TS_SIZE; ++i)
    {
        int delta = (int) round((t1->nums[i] - lastValue) * 100.0);

        t1->compressionOK = 1;
        if (delta > CHAR_MAX || delta < -CHAR_MAX)
        {
            printf("Delta too big: %d (%.3f) vs %d (%.3f) = delta %.3f\n",
                    i-1, t1->nums[i-1], i, t1->nums[i], t1->nums[i] - t1->nums[i-1]);
            t1->compressionOK = 0;
            return;
        }
        else
        {
            t1->compressedNums[i] = (char) delta;
            lastValue = t1->nums[i];
        }
    }
}

static
void decompress(timeSeries *t1)
{
    if (t1->compressionOK)
    {
        double lastValue = t1->firstValue;

        for (int i = 1; i < TS_SIZE; ++i)
        {
            t1->nums[i] = lastValue + t1->compressedNums[i] / 100.0;
            lastValue = t1->nums[i];
        }
    }
}

static void compare(const timeSeries *t0, const timeSeries *t1)
{
    for (int i = 0; i < TS_SIZE; i++)
    {
        char c = (fabs(t0->nums[i] - t1->nums[i]) > 0.005) ? '!' : ' ';
        printf("%c %03d: %.3f vs %.3f = %+.3f\n", c, i, t0->nums[i], t1->nums[i], t0->nums[i] - t1->nums[i]);
    }
}

int main(void)
{
    timeSeries t1;
    timeSeries t0;
    int i;

    for (i = 0; i < TS_SIZE; i++)
    {
        if (scanf("%lf", &t0.nums[i]) != 1)
            break;
    }
    if (i != TS_SIZE)
    {
        printf("Reading problems\n");
        return 1;
    }

    t1 = t0;

    for (i = 0; i < 10; i++)
    {
        printf("Cycle %d:\n", i+1);
        compress(&t1);
        decompress(&t1);
        compare(&t0, &t1);
    }
    return 0;
}

使用以下数据（从 18456..18855 范围内的整数除以 100 并随机少量扰动（约 0.3%，以保持值足够接近）生成），我得到了相同的数据，然后再进行完整的 10 次压缩和解压循环。

184.60 184.80 184.25 184.62 184.49 184.94 184.95 184.39 184.50 184.96
184.54 184.72 184.84 185.02 184.83 185.01 184.43 185.00 184.74 184.88
185.04 184.79 184.55 184.94 185.07 184.60 184.55 184.57 184.95 185.07
184.61 184.57 184.57 184.98 185.24 185.11 184.89 184.72 184.77 185.29
184.98 184.91 184.76 184.89 185.26 184.94 185.09 184.68 184.69 185.04
185.39 185.05 185.41 185.41 184.74 184.77 185.16 184.84 185.31 184.90
185.18 185.15 185.03 185.41 185.18 185.25 185.01 185.31 185.36 185.29
185.62 185.48 185.40 185.15 185.29 185.19 185.32 185.60 185.39 185.22
185.66 185.48 185.53 185.59 185.27 185.69 185.29 185.70 185.77 185.40
185.41 185.23 185.84 185.30 185.70 185.18 185.68 185.43 185.45 185.71
185.60 185.82 185.92 185.40 185.85 185.65 185.92 185.80 185.60 185.57
185.64 185.39 185.48 185.36 185.69 185.76 185.45 185.72 185.47 186.04
185.81 185.80 185.94 185.64 186.09 185.95 186.03 185.55 185.65 185.75
186.03 186.02 186.24 186.19 185.62 186.13 185.98 185.84 185.83 186.19
186.17 185.80 186.15 186.10 186.32 186.25 186.09 186.20 186.06 185.80
186.02 186.40 186.26 186.15 186.35 185.90 185.98 186.19 186.15 185.84
186.34 186.20 186.41 185.93 185.97 186.46 185.92 186.19 186.15 186.32
186.06 186.25 186.47 186.56 186.47 186.33 186.55 185.98 186.36 186.35
186.65 186.60 186.52 186.13 186.39 186.55 186.50 186.45 186.29 186.24
186.81 186.61 186.80 186.60 186.75 186.83 186.86 186.35 186.34 186.53
186.60 186.69 186.32 186.23 186.39 186.71 186.65 186.37 186.37 186.54
186.81 186.84 186.78 186.50 186.47 186.44 186.36 186.59 186.87 186.70
186.90 186.47 186.50 186.74 186.80 186.86 186.72 186.63 186.78 186.52
187.22 186.71 186.56 186.90 186.95 186.67 186.79 186.99 186.85 187.03
187.04 186.89 187.19 187.33 187.09 186.92 187.35 187.29 187.04 187.00
186.79 187.32 186.94 187.07 186.92 187.06 187.39 187.20 187.35 186.78
187.47 187.54 187.33 187.07 187.39 186.97 187.48 187.10 187.52 187.55
187.06 187.24 187.28 186.92 187.60 187.05 186.95 187.26 187.08 187.35
187.24 187.66 187.57 187.75 187.15 187.08 187.55 187.30 187.17 187.17
187.13 187.14 187.40 187.71 187.64 187.32 187.42 187.19 187.40 187.66
187.93 187.27 187.44 187.35 187.34 187.54 187.70 187.62 187.99 187.97
187.51 187.36 187.82 187.75 187.56 187.53 187.38 187.91 187.63 187.51
187.39 187.54 187.69 187.84 188.16 187.61 188.03 188.06 187.53 187.51
187.93 188.04 187.77 187.69 188.03 187.81 188.04 187.82 188.14 187.96
188.05 187.63 188.35 187.65 188.00 188.27 188.20 188.21 187.81 188.04
187.87 187.96 188.18 187.98 188.46 187.89 187.77 188.18 187.83 188.03
188.48 188.09 187.82 187.90 188.40 188.32 188.33 188.29 188.58 188.53
187.88 188.32 188.57 188.14 188.02 188.25 188.62 188.43 188.19 188.54
188.20 188.06 188.31 188.19 188.48 188.44 188.69 188.63 188.34 188.76
188.32 188.82 188.45 188.34 188.44 188.25 188.39 188.83 188.49 188.18

在我进行舍入之前，这些值会迅速分开。

如果您没有 round() — 它已添加到 C99 标准中的标准 C — 那么您可以使用这些行来代替 round():

int delta;
if (t1->nums[i] > lastValue)
    delta = (int) (((t1->nums[i] - lastValue) * 100.0) + 0.5);
else
    delta = (int) (((t1->nums[i] - lastValue) * 100.0) - 0.5);

这对于正值和负值正确舍入。您也可以将其分解为一个函数；在 C99 中，您可以将其设为 inline 函数，但如果可行，您也可以在库中拥有 round() 函数。在切换到 round() 函数之前，我首先使用了这段代码。

在 C 中压缩一系列接近的数字

Compress series of close numbers in C

c

compression

time-series