Home > Back-end >  How to decode a rle string in C
How to decode a rle string in C

Time:04-30

I'm working on this problem to decode a compressed string to its original. Does anyone know how to solve this problem? It should decode "W28bA4B2CB2CB2Ca3" to its original "WWWWWWWWWWWWWWWWWWWWWWWWWWWWbAAAABBCBBCBBCaaa", I don't know how to extract number from this string

int getcount(char *rle)
{   
    int count=0;



    return count;
}

char *decode_rle(char *rle, char *str)
{
    char *ptr=rle;
    char *ptrend=&rle[strlen(rle)];
    char decoding[100];
    int i=0,j=0,count=0, digit=0;
    strcpy(str, "");
```

    str[i] = '\0';
    return str;
}

int main(){
    char str_org[]="WWWWWWWWWWWWWWWWWWWWWWWWWWWWbAAAABBCBBCBBCaaa";
    char rle[100];
    runlengthencoding(str_org,rle);
    printf("str_org:[%s] => rle:[%s]\n",str_org,rle);

    char str_dec[100];
    decode_rle(rle,str_dec);
    printf("rle:[%s] => str_dec:[%s]\n",rle, str_dec);
    return 0;
}

CodePudding user response:

  • You can define the function to extract numbers from RLE encoded strings as below. Call it every time you encounter a digit in encoded-string.
#include <ctype.h>
static inline int
rle_ext_count (const char *rle) {
    int count = 0;
    for (int di = 0; isdigit (rle[di]);   di) {
        count = count * 10   rle[di] - '0';
    }
    return count;
}
  • With static inline we're telling compiler that this function is local to translation unit, and try to inline this small piece of code wherever it's called to mitigate small functions' call overheads.

  • Then your RLE-Decode of a valid RLE encoded string will be :

// Note it doesn't validates the encoding
// e.g "W28bA4B2CB2CB2Ca3" to "WWWWWWWWWWWWWWWWWWWWWWWWWWWWbAAAABBCBBCBBCaaa"
int rle_decode (const char *rle, char *data) {
    int dlen = 0;
    for (int ci = 0; rle[ci]; /*   ci */) {
        int repeat_count = 0;
        if (isdigit(rle[ci])) {
            repeat_count = rle_ext_count(rle   ci);
            while (isdigit(rle[ci]))   ci; // skip digits;
        }
        if (repeat_count) {
            if (!dlen) return -1;   // only this validation is necessary  (rle can't begin with a number)
            for (int rch = data[dlen -1], ri = 1; ri   < repeat_count; )
                data[dlen  ] = rch;
        } else
            data[dlen  ] = rle[ci  ];
    }
    data[dlen] = '\0';
    return dlen;
}
  • Assuming you already have a working RLE-Encode function, testing rle_decode() :
int main() {
//    char str_org[] = "WWWWWWWWWWWWWWWWWWWWWWWWWWWWbAAAABBCBBCBBCaaa";
    char rle[] = "W28bA4B2CB2CB2Ca3";
    char str_dec[100];
    int dec_len = rle_decode (rle, str_dec);
    if (dec_len < 0) {
        printf ("ERROR: Decoding RLE string [%s]\n", rle);
        return 1;
    }
    printf ("rle:[%s] => str_dec:[%s] Length %d\n", rle, str_dec, dec_len);
    return 0;
}
  • Validating a RLE-String is a different question.

CodePudding user response:

Here's a decoding program that produces the desired output:

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int c, lst = EOF;
    int n = 0;
    while ((c = getchar()) != EOF) {
        if (isdigit(c)) {
            n *= 10;
            n  = c - '0';
        } else {
            if (lst != EOF) {
                if (n == 0) n  ; /* 0 -> 1 */
                for (int i = 0; i < n; i  )
                    putchar(lst);
                lst = EOF;       /* already printed */
            }
            n = 0;
            lst = c;
        }
    }
    return 0;
}

if you want it decoded as arrays, you can use the following routine:

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>

char *rle_decode(char *src, char *dst, size_t sz)
{   
    int c, lst = 0;
    int n = 0;
    char *saved = dst;

    while ((c = *src  ) != 0) {
        if (isdigit(c)) {
            n *= 10;
            n  = c - '0';
        } else {
            if (lst) {
                if (n == 0) n  ; /* 0 -> 1 */
                for (int i = 0; i < n; i  )
                    if (sz--) *dst   = lst;
                lst = 0;         /* already printed */
            }
            n = 0;
            lst = c;
        }
    }
    if (lst) {
        if (n == 0) n  ;
        for (int i = 0; i < n; i  )
            if (sz--) *dst   = lst;
    }
    *dst = 0;
    return saved;
}

int main()
{   
    char buffer[256];
    char source[] = "W28bA4B2CB2CB2Ca3";

    printf("rle_decode(\"%s\", buffer, %zd) => \"%s\"\n",
        source, sizeof buffer,
        rle_decode(source, buffer, sizeof buffer));

    return 0;
}
  • Related