Run Length Encoding!!

RUN LENGTH ENCODING

Simple type of redundancy in a bit stream.  Long run of repeated bits

Consider the following bit stream:

0000000000000001111111000000011111111111

Total : 40 Bits

Representation : 4-bit counts to represent alternating runs of 0's and 1's.

15 0's. then 7 1's, then 7 0's, then 11 1's, i.e., (15,0), (7,1), (7,0) (11,1).

Since the maximum number of repetition is 15, which can be represented with 4 bits we can encode the bit stream as (1111,0), (0111,1), (0111,0), (1011,1).

The compression ratio in this is case is 20:40 = 1:2

Code:

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#define MAX_RLEN 50
using namespace std;
char *encode(char *src)
{
int rLen;
char count[MAX_RLEN];
int len = strlen(src);

char *dest = (char *)malloc(sizeof(char)*(len*2 + 1));

int i, j = 0, k;

/* traverse the input string one by one */
for(i = 0; i < len; i++)
{
/* Copy the first occurrence of the new character */
dest[j++] = src[i];

/* Count the number of occurrences of the new character */
rLen = 1;
while(i + 1 < len && src[i] == src[i+1])
{
rLen++;
i++;
}
int n=rLen;
int remainder,place=1,binary=0;

 while (n > 0)
    {
        remainder = n % 2;
        binary += remainder * place;
        place *= 10;
        n /= 2;
    }
/* Store binary in a character array count[] */

sprintf(count, " , %d\n", rLen);

/* Copy the count[] to destination */
for(k = 0; *(count+k); k++, j++)
{
dest[j] = count[k];
}
}
/*terminate the destination string */
dest[j] = '\0';
return dest;
}
/*driver program to test above function */
int main()
{
char str1[100];
printf("\n\t\t\tRUN-LENGTH ENCODING TECHNIQUE""\n\t\t\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n\n");
printf("\nEnter the String:: ");
cin.get(str1, 100);
printf("\n\nThe Run Length Encoding for the String is:: \n\n");
char *res = encode(str1);
printf("%s ", res);
getchar();

}

Shannon-Fano coding