RLE压缩算法总结

1、RLE压缩算法介绍

RLE(Run Length Encoding)压缩算法是一种无损压缩算法。算法特点：简单、易实现。
RLE将待压缩数据看作一个字符序列，序列中存在两种情况：1）连续重复的字符；2）孤立的字符。压缩对象主要是连续重复的字符，例如连续字符 AAAAA，可以使用字符5A表示。

2、RLE文本压缩算法

2.all*is*well用2.a2l*is*we2l表示存在问题，原因是解码器不知道第一个2和第二个2分别代表什么意义，需要区分是原始字符串中的字符还是代表紧跟着的字符的重复次数。可以使用一个特殊字符比如@表示，例如@2l可以知道@字符后面的2表示字符l出现了两次。可以使用2.a@2l*is*we@2l压缩2.all*is*well（实际没有压缩效果）。

上述方法限制

• 1 很多文本字符串一般很少出现3个连续相同的字符，这种情况下，往往起不到压缩的效果。
• 2 重复次数字符串最大限制为255。可以优化3-258，0代表3，255代表258
• 3 字符@不可以出现在待编码的字符中。否则需要重新选一个特殊字符。如果待编码字符中有所有的字符，则需要其他解决方案。
  [//]: # (MNP5算法是RLE的一个RLE的变体)

3、实验

#include <stdio.h>
#include <string.h>
#include <malloc.h>

int encode_RLE(char* input, char* output)
{
    int i=0, j=0, k=0;
    for(; i<strlen(input); ) {
        /*待编码字符的第一个字符*/
        char head = input[i];
        for (j = i+1; j < strlen(input); j++) {
            /*后面第一个不相同字符位置*/
            if(input[j] != head)
                break;
        }
        /*重复字节数大于等于3*/
        if(j-i>=3)
        {
            output[k++]='@';
            output[k++]=(char)(j-i-3+'0'); //便于打印偏移到'0'.
            output[k++]=head;
        }else{
            /*重复次数小于3*/
            for(int m=0; m<j-i; m++)
                output[k++]=head;
        }
        i=j;
    }
    return k;
}

int decode_RLE(char *input, char* output)
{
    int k=0;
    for(int i=0; i<strlen(input);){
        if(input[i]=='@') {
            i++;
            for (int j = 0; j < input[i]-'0'+3; j++)
                output[k++]=input[i+1];
            i=i+2;
            continue;
        }
        output[k++]=input[i++];
    }
    return k;
}

int main() {
    char* input = (char*)malloc(1024);
    char* output = (char*)malloc(1024);
    char* result = (char*)malloc(1024);

    memset(input, 0, 1024);
    memset(output, 0, 1024);
    memset(result, 0, 1024);

    printf("Please input a string:");
    scanf("%s", input);
    printf("input length is %d.\n", (int)strlen(input));
    int k=encode_RLE(input, output);
    printf("Compressed data is:%s, and length is %d.\n", output, k);
    int m = decode_RLE(output, result);
    printf("decompress data is %s, and length is %d.\n", result, m);

    return 0;
}

4、总结

RLE方法思路简洁明了，实现简单，但是，在很多情况下压缩效果不明显。