Bit Map Compression of Binary Files


Bit Map

A bit map compression scheme consists of a bit map and a physical database which stores the non-constant values. The bit map is employed to indicate the presence or absence of non-constant data. The following example shows how the bit map compression scheme can be employed to implement a version of constant suppression.

Example:

Original data string
d1, c, c, d2, c, c, c, d3

Compressed data string
Bit map: 10010001.
Physical database: dl, d2, d3.

For the bit map compression method, the mapping mechanism must search the whole bit map for both forward and backward mapping. And thus, the access time for both forward and backward mapping is O(N), where N is the number of bits in the bit map or equivalently the number of elements in the database.

Program in CPP:
From the above theory, we have designed the program that is stated below. this program takes input from the secondary memory as binary (.bin) file.
thank you!
Continue reading

Run Length Encoding (RLE)

Run-Length Encoding:

The application of run-length encoding to constant removal is that each consecutive run of constants (there can be a few different types of constants to be removed) is replaced by a triple consisting of a separator SEP, an encoding of the constant X to be removed and a counter C indicating the length of the run. To search a run-length encoded database for both forward and backward mapping, a sequential search has to be done to sequence through the data, counting the number of unsuppressed values and references to the number of repeated values. The time required here is again O (N).

This program is developed by Md.Mushfiqur Rahman and Abdullah Al Mahmud during the time of undergrad thesis in CSE, KUET.

#include iostream.h
#include fstream.h
#include string.h
#include stdlib.h
#include stdio.h
#include time.h

int main()
       {
//     char ins;
       char pd[500];
       int len;

//    printf("Please enter the actual data :");
//    gets(ins);

time_t t;
srand((unsigned) time(&t));
printf("random numbers from 0 to 9,a-z,A-Z\n\n");
char ch;
ofstream out("raw_data.txt");
for(int i=0; i<100 ; i++)
{
int r=rand()%123;
if((48<r && r<58) ||(64<r && r<91) ||(96<r && r<123))
{
//    printf(" %c",r);
ch=(char)r;
out<<ch;
if(ch == 'o'||ch=='O'||ch=='0')
for(int x=0;x<i;x++)
out<<ch;
}
}
out.close();

ifstream in("raw_data.txt");
         in>>pd;
         in.close();

         printf("The original data is :");
         puts(pd);
         len=strlen(pd);
         //puts(pd);

         int j,count[500]={0};

         ofstream fout("Encoded.txt");

       printf("\nEncoded String is: ");
       for(i=0;i< len;i*=1)
          {
             j = 0;
             count[i] = 1;
            do
               {
                 j++;
if(pd[i+j] == pd[i])
count[i]++;
}
         while(pd[i+j]==pd[i]);
         if(count[i]==1)
         {
           printf("%c",pd[i++]);
           fout<<pd[i];
           }
         else
           {
              printf("$%d%c",count[i],pd[i]);
              fout<<'$'<<count[i]<<pd[i];
              i += count[i];
            }
          }
                cout<<endl;
                fout.close();

                 return 0;
               }