压缩和解压缩整数数组的函数

Question

我最近被要求完成对于C++角色的任务,但是作为应用程序并没有决定要取得进展的任何进一步的我以为我会在这里发布一些反馈/咨询/改进/我已经忘记了概念的提醒.

任务是:

以下数据是整数值的时间序列

int timeseries[32] = {67497, 67376, 67173, 67235, 67057, 67031, 66951,
66974, 67042, 67025, 66897, 67077, 67082, 67033, 67019, 67149, 67044,
67012, 67220, 67239, 66893, 66984, 66866, 66693, 66770, 66722, 66620,
66579, 66596, 66713, 66852, 66715};

例如,该系列可能是每天超过32天的股票收盘价.

如上所述,数据将占用32 x sizeof(int) bytes = 128 bytes 假设4字节的整数.

使用delta编码,编写要压缩的函数,以及解压缩数据的函数,如上所述.

好的,所以在此之前我从未考虑压缩,所以我的解决方案远非完美.我解决问题的方式是将整数数组压缩成一个字节数组.当将整数表示为一个字节时,我保持计算最高有效字节(msb)并将所有内容保持到这一点,同时将其余部分抛弃.然后将其添加到字节数组中.对于负值,我将msb递增1,以便在解码时通过保持前导1位值来区分正字节和负字节.

解码时,我解析这个锯齿状的字节数组,然后简单地反转压缩时执行的先前操作.如前所述,我从未在此任务之前查看压缩,因此我确实提出了自己的方法来压缩数据.我最近在看C++/Cli,之前没有真正使用它,所以决定用这种语言写它,没有特别的原因.下面是课程,最底层是单元测试.任何建议/改进/改进将非常感激.

谢谢.

array<array<Byte>^>^ CDeltaEncoding::CompressArray(array<int>^ data)
{
    int temp = 0;
    int original;
    int size = 0;

    array<int>^ tempData = gcnew array<int>(data->Length);
    data->CopyTo(tempData, 0);

    array<array<Byte>^>^ byteArray = gcnew array<array<Byte>^>(tempData->Length);

    for (int i = 0; i < tempData->Length; ++i)
    {
            original = tempData[i];
            tempData[i] -= temp;
            temp = original;

            int msb = GetMostSignificantByte(tempData[i]);

            byteArray[i] = gcnew array<Byte>(msb);
            System::Buffer::BlockCopy(BitConverter::GetBytes(tempData[i]), 0, byteArray[i], 0, msb );

            size += byteArray[i]->Length;
    }

    return byteArray;
}

array<int>^ CDeltaEncoding::DecompressArray(array<array<Byte>^>^ buffer)
{
    System::Collections::Generic::List<int>^ decodedArray = gcnew System::Collections::Generic::List<int>();

    int temp = 0;

    for (int i = 0; i < buffer->Length; ++i) 
    {
            int retrievedVal = GetValueAsInteger(buffer[i]);
            decodedArray->Add(retrievedVal);

            decodedArray[i] += temp;
            temp = decodedArray[i];
    }

    return decodedArray->ToArray();
}

int CDeltaEncoding::GetMostSignificantByte(int value)
{
    array<Byte>^ tempBuf = BitConverter::GetBytes(Math::Abs(value));

    int msb = tempBuf->Length;

    for (int i = tempBuf->Length -1; i >= 0; --i)
    {
            if (tempBuf[i] != 0)
            {
                    msb = i + 1;
                    break;
            }
    }

    if (!IsPositiveInteger(value))
    {
            //We need an extra byte to differentiate the negative integers
            msb++;
    }

    return msb;
}

bool CDeltaEncoding::IsPositiveInteger(int value)
{
    return value / Math::Abs(value) == 1;
}

int CDeltaEncoding::GetValueAsInteger(array<Byte>^ buffer)
{
    array<Byte>^ tempBuf;

    if(buffer->Length % 2 == 0)
    {
            //With even integers there is no need to allocate a new byte array
            tempBuf = buffer;
    }
    else
    {
            tempBuf = gcnew array<Byte>(4);
            System::Buffer::BlockCopy(buffer, 0, tempBuf, 0, buffer->Length );

            unsigned int val = buffer[buffer->Length-1] &= 0xFF;

            if ( val == 0xFF )
            {
                    //We have negative integer compressed into 3 bytes
                    //Copy over the this last byte as well so we keep the negative pattern
                    System::Buffer::BlockCopy(buffer, buffer->Length-1, tempBuf, buffer->Length, 1 );
            }
    }

    switch(tempBuf->Length)
    {
    case sizeof(short):
            return BitConverter::ToInt16(tempBuf,0);
    case sizeof(int):
    default:
            return BitConverter::ToInt32(tempBuf,0);
    }
}

然后在测试课中我有:

void CTestDeltaEncoding::TestCompression()
{
    array<array<Byte>^>^ byteArray = CDeltaEncoding::CompressArray(m_testdata);

    array<int>^ decompressedArray = CDeltaEncoding::DecompressArray(byteArray);

    int totalBytes = 0;
    for (int i = 0; i<byteArray->Length; i++)
    {
            totalBytes += byteArray[i]->Length;
    }

    Assert::IsTrue(m_testdata->Length * sizeof(m_testdata) > totalBytes, "Expected the total bytes to be less than the original array!!");

    //Expected totalBytes = 53
}

Answer 1

这闻起来很像我的作业.关键短语是:"使用delta编码."

增量编码意味着您对每个数字和下一个数字之间的增量(差异)进行编码:

67497,67376,67173,67235,67057,67031,66951,66974,67042,67025,66897,67077,67082,67033,67019,67149,67044,67012,67220,67239,66893,66984,66866,66693,66770, 66722,66620,66579,66596,66713,66852,66715

会变成:

[基数:67497]: - 121,-203,+ 62

等等.假设8位字节,原始数字每个需要3个字节(并且给定3个字节整数类型的编译器数量,通常最终会得到4个字节).从外观来看,差异很容易适合每个2个字节,如果你可以忽略一个(或可能两个)最低有效位,你可以将它们分别放在一个字节中.

增量编码最常用于声音编码之类的事情,您可以在没有重大问题的情况下"捏造"精确度.例如,如果您从一个样本到下一个样本的变化大于您要留下的空间进行编码,则可以对当前差异的最大变化进行编码,并将差异添加到下一个增量(如果您不是记住一些反向跟踪,你也可以分配一些回到以前的delta.这将充当低通滤波器,限制样本之间的梯度.

例如,在您给出的系列中,简单的delta编码需要十位来表示所有差异.然而,通过丢弃LSB,几乎所有样本(实际上除了一个之外)都可以以8位编码.那个有差异(右移一位)-173,所以如果我们把它表示为-128,我们剩下45个.我们可以在前一个和下一个样本之间平均分配该错误.在这种情况下,输出将不是输入的精确匹配,但如果我们谈论的是声音之类的东西,差异可能不会特别明显.