嵌入式算法10---行程编码

1、行程编码

嵌入式设备采集的数据，变化比较平缓，长时间趋于稳定的状态，其采样结果会有大量连续且相同的数值，对应这些数据，常规的压缩算法在硬件资源有限的嵌入式设备无法运行，代码空间和RAM要求不能满足的情况下，简单有效的行程编码不失为一种最佳选择。

行程编码（Run Length Encoding，RLE), 又称游程编码，主要思路是将一个相同值的连续串用一个代表值和串长来代替。例如字符串“AAABBBBCCCCCJJJJJJ”，可以用“3A4B5C6J”来记录，原本长度18字节的字符串使用8个字节即可无损表达。

为便于直观显示，举例的编码是进行了特殊描述，“3A4B5C6J”实际应该是 3‘A’ 4‘B’ 5‘C’ 6‘J’，字符个数的数字转为字符显示，例如3变成了‘3’显示更易理解。

以下举例也是这个规则，正确方式是应该是以%X查看，如果不明白3和‘3’的区别，请先补习C基础。

2、局限性与改进型

行程编码的原理简单，但算法需结合实际，统计数据出现概率与次数，有针对性的改进编码，提高压缩比。

1. 按前面范例规则，原始数据全部都不连续出现，如源字符串“ABCDE”编码后变成“1A1B1C1D1E”，其长度反而扩大一倍，因此对于随机出现没有连续字符的数据，基本规则不适合。
2. 可以改进为编码时查询连续出现的才进行编码，只出现一次的直接使用原始值，不进行处理。如"111233334"编码为“31 2 43 4”，字符2和4只出现一次，编码时忽略。但缺点是解码无法分辨其中的2是数值出现次数，还是数值本身。
3. 因此对编码与未编码的分段，使用标记区分段。例如定义编码段以E开头，则"111233334"编码为“E31 2 E43 4”，解析时只对出现E的字段才进行解析，单个字段直接原样替换。
4. 增加段标记后，每个连续段编码后都是3个字节，如果相同字符值出现2次，如“11335577”则编码后为“E21 E23 E25 E27”,其长度超过原始长度，因此可以改为，只有连续出现的次数大于3的才进行编码。例如"112223333"编码为“11 222 E43”。
5. 因为表示字符连续次数的数字分配了一个字节，某个字符如连续出现255次以上，则拆分为两部分。如“AAA…AAA”连续出现300次，则编码以%X显示为 45 FF 41 45 2D 41 ，其中’E’=0x45,‘A’=0x41。

45 FF 41 //行程编码 255 个’A’

45 2D 41 //行程编码 45 个’A’

6. 前面描述编码段的头以’E’作为标记，字符连续出现次数大于3的才进行编码处理的，因此 ‘E’ 后面的数字肯定大于3。如果源数据中存在‘E’，则以 ‘E’0转义，这样才能解析分辨，是真实的’E’，还是编码标记。
   如 “EEEEE”编码后以16进制显示为 45 00 45 00 45 00 45 00 45 00 ，结果是长度增加一倍，因此定义合理的标记很关键。

选择字数据串中出现概率最小的为标记。如纯ASCII字符串（0-0x7F），选择0x80则避开该问题。

7. 算法规则没有最好的，只有最合适的，如果认可前面的规则，可继续阅读下面的源码，包括编码和解码。

3、源码

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

//配置为数据源中出现概率最小的数
#define FLAG_ENCODE_HEAD 0x80

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

    printf("%s:",head);

    for(i=0;i<len;i++)
    {
        printf("%02X ",data[i]);
    }
    printf("\r\n");
}

//行程编码
//输入待编码的数据及长度，提供输出编码数据的缓冲区
//返回编码后的长度
int compress_encode(unsigned char *dect, unsigned char *src, unsigned int len)
{
    unsigned char last = 0, count = 0;
    unsigned char *dd = dect;

    unsigned char flag = 1;

    while(len)
    {
        if(flag)
        {
            flag = 0;
        }
        else if(last == FLAG_ENCODE_HEAD)
        {
            *dect++ = FLAG_ENCODE_HEAD;
            *dect++ = 0x00;
        }
        else if(last == *src)
        {
            if(count < 0xFF)
            {
                count++;
            }
            else
            {
                *dect++ = FLAG_ENCODE_HEAD;
                *dect++ = count;
                *dect++ = last;
                count = 1;
            }
        }
        else
        {
            count++;
            if(count > 3)
            {
                *dect++ = FLAG_ENCODE_HEAD;
                *dect++ = count;
                *dect++ = last;
                count = 0;
            }
            else
            {
                while(count)
                {
                    *dect++ = last;
                    count--;
                }
            }
        }
        last = *src;
        src++;
        len--;
        if(len == 0)
        {
            count++;
            if(count > 3)
            {
                *dect++ = FLAG_ENCODE_HEAD;
                *dect++ = count;
                *dect++ = last;
                count = 0;
            }
            else
            {
                while(count)
                {
                    if(last == FLAG_ENCODE_HEAD)
                    {
                        *dect++ = FLAG_ENCODE_HEAD;
                        *dect++ = 0x00;
                    }
                    else
                    {
                        *dect++ = last;
                    }
                    count--;
                }
            }
        }
    }
    return (dect - dd);
}

//解码
//输入待解码的数据及长度，提供输出解码数据的缓冲区
//返回解码后的长度
int compress_decode(unsigned char *dect, unsigned char *src, unsigned int len)
{
    unsigned char cc = 0;
    unsigned char *dd = dect, *src2 = src;

    while(len)
    {
        if(*src == FLAG_ENCODE_HEAD)
        {
            if(len == 1 || (src[1] == 0 && len < 2) || (src[1] != 0 && len < 3))
            {
                return -2;
            }
            cc = src[1];
            if(!cc)
            {
                *dect++ = FLAG_ENCODE_HEAD;
                src += 1;
                len -= 1;
            }
            else
            {
                while(cc)
                {
                    *dect++ = src[2];
                    cc--;
                }
                src += 2;
                len -= 2;
            }
        }
        else
        {
            *dect++ = *src;
        }
        src++;
        len--;
    }

    return (dect - dd);
}


int main(int argc, char *argv[])
{
    unsigned char input[100]={"AAAAAAAAABBBBBBBBBCCCCCCCCCDDDEFGGGGGGGGGGG#"};

    //最差情况下编码后的长度是源数据的2倍，这种情况下应该调整编码规则
    unsigned char encode_buff[200]={0};
    int encode_len;

    unsigned char decode_buff[100]={0};
    int decode_len;

    encode_len=compress_encode(encode_buff,input,strlen((char *)input));
    log("encode",encode_buff,encode_len);
    printf("len=%d->%d\r\n",strlen((char *)input),encode_len);

    decode_len=compress_decode(decode_buff,encode_buff,encode_len);
    log("decode",decode_buff,decode_len);

    printf("output:[%s] , ratio=%f\r\n",decode_buff,(float)encode_len/decode_len);
    if(memcmp(input,decode_buff,decode_len)==0)
    {
        printf("test ok\r\n");
    }
    else
    {
        printf("test fail\r\n");
    }

    return 0;
}

运行输出

encode:80 09 41 80 09 42 80 09 43 44 44 44 45 46 80 0B 47 23

len=44->18

decode:41 41 41 41 41 41 41 41 41 42 42 42 42 42 42 42 42 42 43 43 43 43 43 43 43 43 43 44 44 44 45 46 47 47 47 47 47 47 47 47 47 47 47 23

output:AAAAAAAAABBBBBBBBBCCCCCCCCCDDDEFGGGGGGGGGGG#] , ratio=0.409091

test ok

4、小节

游程编码适用于数据本身具有大量连续重复出现的内容，可以结合实际数据源，有针对性的调整编码规则，提高压缩比。