嵌入式算法11---矩阵转置与压缩

在整个物联网系统中，嵌入式设备作为数据采集、过滤、缓存、传输的节点，前面系列文章分别介绍了嵌入式设备相关的各种数据过滤、校验和压缩存储算法。缓存和传输阶段，考虑到嵌入式设备的存储空间和传输带宽限制，数据包的压缩还可进一步优化。

以嵌入式终端环境数据采集为例，以10秒间隔采样温度、湿度、气压、风速、四项环境数据，正常情况下，数据在短时间内都是小幅波动或者维持不变。假如采集结果（瞎编的，表意为主）如下表：

数据按字节流存储到文件或者传输出去，占30字节。

unsigned char source_data[30]={10,27,75,98,3,20,27,75,98,3,30,27,75,99,3,40,27,76,99,3,50,28,76,99,2,60,29,76,99,2}

前文行程编码要求数据中尽可能出现连续的内容，上表数据并不适合行程编码来压缩。

线性代数的基础是矩阵，此时此刻，矩阵转置的算法就可发挥作用了。将数据原始数据以二维数据的方式保存。

unsigned char source_matrix[5][6]={
10,10,30,98,3,
20,27,75,98,3,
30,27,75,99,3,
40,27,76,99,3,
50,28,76,99,2,
60,29,76,99,2}

观察数据，按C语言的行优先方式没有连续的数据，但如果以列为优先，则数据中存在较多的连续数据。因此先将数据进行矩阵行列转置后，即可满足行程编码的要求。

实现效果以及源码如下：

#include "stdio.h"
#include "string.h"

void log(char *head,unsigned char* data,unsigned int len,unsigned char line)
{
    unsigned int i;

    printf("%s\r\n",head);

    for(i=0;i<len;i++)
    {
        printf("%3d ",data[i]);
        if(((i+1)%line)==0)
        {
            printf("\r\n");
        }
    }
    printf("\r\n");
}

//矩阵转置，执行一次行列交互，再次执行则恢复原样
// row 和 column 表示输入矩阵的行和列
void matrix_transpose(unsigned char* input, unsigned char row, unsigned char column, unsigned char* output)
{
    unsigned char i, j;

    for(i = 0; i < row; i++)
    {
        for(j = 0; j < column; j++)
        {
            *(output + j * row + i) = *(input + i * column + j);
        }
    }
}


int main(int argc, char *argv[])
{
    //原始6行5列的数据
    unsigned char source[30]={10,27,75,98,3,20,27,75,98,3,30,27,75,99,3,40,27,76,99,3,50,28,76,99,2,60,29,76,99,2};

    //转成5行6列，用于行程编码
    unsigned char change[30]={0};

    //恢复为原始的6行5列
    unsigned char resume[30]={0};

    log("source",(unsigned char*)source,sizeof(source),15);
    log("source",(unsigned char*)source,sizeof(source),5);

    matrix_transpose((unsigned char*)source,6,5,change);
    log("change",change,sizeof(change),5);
    log("[new]",(unsigned char*)change,sizeof(change),15);

    matrix_transpose(change,5,6,(unsigned char*)resume);
    log("resume",(unsigned char*)resume,sizeof(resume),5);

    return 0;
}

运行结果如下：

source
 10  27  75  98   3  20  27  75  98   3  30  27  75  99   3
 40  27  76  99   3  50  28  76  99   2  60  29  76  99   2

source
 10  27  75  98   3
 20  27  75  98   3
 30  27  75  99   3
 40  27  76  99   3
 50  28  76  99   2
 60  29  76  99   2

change
 10  20  30  40  50
 60  27  27  27  27
 28  29  75  75  75
 76  76  76  98  98
 99  99  99  99   3
  3   3   3   2   2

[new]
 10  20  30  40  50  60  27  27  27  27  28  29  75  75  75
 76  76  76  98  98  99  99  99  99   3   3   3   3   2   2
 【转置后相同数据集中连续出现】

resume
 10  27  75  98   3
 20  27  75  98   3
 30  27  75  99   3
 40  27  76  99   3
 50  28  76  99   2
 60  29  76  99   2

其中[new]块数据就适合行程编码来压缩空间，为提高压缩比，可以每20组数据包分为一个矩阵进行转置压缩，太少则压缩比不明显。

矩阵转置与行程编码两算法，可以解决固定长度重复出现，内部数据变化趋于稳定的数据包压缩。