Jun 132012
 

What is “Run Length Encoding (RLE)” ? Write a function, which will accept a string and convert it to a Run Length Encoded string.

Solution:

Run Length Encoding is way to compress data. It is used when data is repeated multiple times, in such cases rather than storing that many copies of the data, lit stores only one copy of the data and count of the number of times it is repeated.

For example:

Input String: AAAAAAAAAAAABAAAAAAAAAACCCKKKKKKKKKKKKRRRRRRR
RLE Encoded String: A12B1A10C3K12R7

Advantages:

This is a lossless data compression technique, because data can be recovered as it was on de-compression.

Algorithm:

  1. i = 0
  2. while i < number of char in input string
    1. Write, ith it on output string.
    2. See how many following character are same as this one.
    3. Put the count to output string.
    4. Increment i by count.

Code:

    /* Does the RLE of Source (src) and put it in the dest string.
     * Caller should ensure that the size of dest is sufficient enough
     * to hold the data */
    void encodeRLE(char* src, char* dest)
    {
        int i, j, k, runlen;
        char temp[100];
        int srcLen = strlen(src);

        /* traverse the input string one by one */
        for(i=0, j=0; i<srcLen; i++)
        {
            dest[j++] = src[i];

            // Count the length of Run
            for(runlen = 1; (i+1 < srcLen) && (src[i] == src[i+1]); runlen++, i++)
                ;

            sprintf(temp, "%d", runlen);

            for(k=0; temp[k]!='\0';)
                dest[j++] = temp[k++];
        } 

        // terminating the dest string
        dest[j] = '\0';

    }

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)