File compression and multi-dimensional array

Question

Scenario A simple matrix could be used to store data about images by using 1’s and 0’s to represent dark

and light shades of color similar to a bitmap. You will find a file data.txt under your assignment

3 on Moodle. The file looks the image of an X drawn on a canvas.

0110000000000110

0011000000001100

0001100000011000

0000110000110000

0000011001100000

0000001111000000

0000000110000000

0000001111000000

0000011001100000

0000110000110000

0001100000011000

0011000000001100

0110000000000110

If we look at the data in the file, there are a lot of repeated digits present in the file. This causes

a lot of overhead in storing the file as you have to store so many numbers. The goal of this

assignment is to use a compression algorithm to compress the file and try to make it smaller

without loosing any information about the data present in the data file.

Compression Algorithm:

One method of compressing a file is to recognize repeated digits and replace the runs of

repetition with a number representing the repetition length. For instance for a line in you file

such as ;

0110000000000110

Can be represented with the line:

1 2 10 2 1

Because there is 1 zero, 2 ones, 10 zeros, 2 ones and 1 zero. It is already understood that only

zeros and ones appear and that zeros apper first in a given line. Thus storing the new line of

data is much shorter (5 numbers) than the original line (16 numbers)

To decompress the encoded file you can follow the reverse implementation of the method

stated above, for example for the encoded data:

4 2 4 2 4

The decompressed data is:

0000110000110000

Objectives

You have to complete the following tasks to successfully complete the assignment.

1. Read the data file data.txt and store its data in a multi-dimentional array
2. Create a file called compressed.txt
3. For every row in the multi-dimensional array
4. a. Compress the data the file data using compression scheme discussed above
5. b. Take the compressed line and write it to your compresed.txt file
6. Create a function called decompress. This function should:
7. a. Read the data from compressed.txt file
8. b. Decompress it using decompression scheme shown above
9. c. Print decompressed data to console
10. Create the main function that carries out all the tasks listed above

1.2.2 Use of Functions in Assignment:

It necessary that you implement this assignment using functions. To obtain the maximum

score you must demonstrate the ability to create and use functions of your own. For

example, you may consider creating and using the following functions in your program:

1. Encoding function
2. Decoding function
3. Printing Welcome Message

1.4 Note:

1. In all your program constructs you must write comments where necessary. Don’t write

comments for obvious code, but segments of code which seem complex.

1. All input should be validated wherever necessary

c++

Answer 1

using namespace std;

#include <iostream>

#include <string.h>

#define WORD_LEN (16)

#define MAX_LINES (1024)

typedef struct _TWord

{

char bitstr[WORD_LEN+1];

int intstr[WORD_LEN];

int iCount;

int startingBit;

}*TWord;

#define WORD_SIZE (sizeof(struct _TWord))

#define TWORD_SIZE (sizeof(TWord))

int bits2Ints(TWord word)

{

int bitStreak=1;

word->startingBit = (word->bitstr[0]=='1') ? 1 : 0;

word->iCount=0;

for (int iLoop=0; iLoop<WORD_LEN-1; iLoop++)

{

if ( word->bitstr[iLoop]!=word->bitstr[iLoop+1])

{

word->intstr[word->iCount++] = bitStreak;

bitStreak=1;

}

else

{

bitStreak++;

}

}

word->intstr[word->iCount++] = bitStreak;

}

ints2Bits(TWord word)

{

char curBit = (word->startingBit==1) ? '1' : '0';

int iIndexPos=-1;

for (int iLoop=0; iLoop<word->iCount; iLoop++)

{

for (int jLoop=0; jLoop<word->intstr[iLoop]; jLoop++)

{

word->bitstr[++iIndexPos]=curBit;

}

if (curBit=='1')

{

curBit='0';

}

else

{

curBit='1';

}

}

word->bitstr[WORD_LEN]=0;

}

DumpWord(TWord word)

{

cout << word->bitstr << endl;

for (int iLoop=0; iLoop<word->iCount; iLoop++)

{

cout << word->intstr[iLoop] << endl;

}

cout << " starting bit " << word->startingBit << endl;

}

int Compress ( char * input_filename, char * output_filename )

{

char A[MAX_LINES][WORD_LEN];

struct _TWord word[MAX_LINES];

int iLineCount=0;

int iLoop;

int wordCount =0;

FILE * infile = fopen(input_filename,"r");

FILE * outfile = fopen(output_filename,"w");

for (iLoop=0; iLoop<MAX_LINES; iLoop++)

{

if (fscanf(infile,"%s",A[iLoop])== EOF)

{

cout << A[iLoop] << endl;

break;

}

cout << A[iLoop] << endl;

}

iLineCount = iLoop;

cout << iLineCount << " lines compressed " << endl;

for (iLoop=0; iLoop<iLineCount; iLoop++)

{

strcpy(word[iLoop].bitstr,A[iLoop]);

bits2Ints(&word[iLoop]); //compression takes place here

DumpWord(&word[iLoop]);

fprintf(outfile,"%d %d ",word[iLoop].startingBit,word[iLoop].iCount);

for (int jLoop=0; jLoop<word[iLoop].iCount; jLoop++)

{

fprintf(outfile," %d ",word[iLoop].intstr[jLoop]);

}

fprintf(outfile,"\n");

}

fclose(infile);

fclose(outfile);

return(iLoop);

}

int Decompress( char * input_filename, char * output_filename)

{

struct _TWord word[MAX_LINES];

int iLineCount=0;

int iLoop;

int wordCount =0;

FILE * infile = fopen(input_filename,"r");

FILE * outfile = fopen(output_filename,"w");

for (iLoop=0; iLoop<MAX_LINES; iLoop++)

{

if (fscanf(infile,"%d %d",&word[iLoop].startingBit, &word[iLoop].iCount)!=EOF)

{

for (int jLoop=0; jLoop<word[iLoop].iCount; jLoop++)

{

fscanf(infile,"%d",&word[iLoop].intstr[jLoop]);

}

ints2Bits(&word[iLoop]);

fprintf(outfile,"%s\n",word[iLoop].bitstr);

}

else

{

break;

}

}

fclose(infile);

fclose(outfile);

return(iLoop);

}

int main()

{

Compress( (char*)"data.txt",(char*)"compressed.txt");

Decompress ((char*) "compressed.txt",(char *) "copydata.txt ");

}

Answer 2

using namespace std;

#include <iostream>

#include <string.h>

#define WORD_LEN (16)

#define MAX_LINES (1024)

typedef struct _TWord

{

char bitstr[WORD_LEN+1];

int intstr[WORD_LEN];

int iCount;

int startingBit;

}*TWord;

#define WORD_SIZE (sizeof(struct _TWord))

#define TWORD_SIZE (sizeof(TWord))

int bits2Ints(TWord word)

{

int bitStreak=1;

word->startingBit = (word->bitstr[0]=='1') ? 1 : 0;

word->iCount=0;

for (int iLoop=0; iLoop<WORD_LEN-1; iLoop++)

{

if ( word->bitstr[iLoop]!=word->bitstr[iLoop+1])

{

word->intstr[word->iCount++] = bitStreak;

bitStreak=1;

}

else

{

bitStreak++;

}

}

word->intstr[word->iCount++] = bitStreak;

}

ints2Bits(TWord word)

{

char curBit = (word->startingBit==1) ? '1' : '0';

int iIndexPos=-1;

for (int iLoop=0; iLoop<word->iCount; iLoop++)

{

for (int jLoop=0; jLoop<word->intstr[iLoop]; jLoop++)

{

word->bitstr[++iIndexPos]=curBit;

}

if (curBit=='1')

{

curBit='0';

}

else

{

curBit='1';

}

}

word->bitstr[WORD_LEN]=0;

}

DumpWord(TWord word)

{

cout << word->bitstr << endl;

for (int iLoop=0; iLoop<word->iCount; iLoop++)

{

cout << word->intstr[iLoop] << endl;

}

cout << " starting bit " << word->startingBit << endl;

}

int Compress ( char * input_filename, char * output_filename )

{

char A[MAX_LINES][WORD_LEN];

struct _TWord word[MAX_LINES];

int iLineCount=0;

int iLoop;

int wordCount =0;

FILE * infile = fopen(input_filename,"r");

FILE * outfile = fopen(output_filename,"w");

for (iLoop=0; iLoop<MAX_LINES; iLoop++)

{

if (fscanf(infile,"%s",A[iLoop])== EOF)

{

cout << A[iLoop] << endl;

break;

}

cout << A[iLoop] << endl;

}

iLineCount = iLoop;

cout << iLineCount << " lines compressed " << endl;

for (iLoop=0; iLoop<iLineCount; iLoop++)

{

strcpy(word[iLoop].bitstr,A[iLoop]);

bits2Ints(&word[iLoop]); //compression takes place here

DumpWord(&word[iLoop]);

fprintf(outfile,"%d %d ",word[iLoop].startingBit,word[iLoop].iCount);

for (int jLoop=0; jLoop<word[iLoop].iCount; jLoop++)

{

fprintf(outfile," %d ",word[iLoop].intstr[jLoop]);

}

fprintf(outfile,"\n");

}

fclose(infile);

fclose(outfile);

return(iLoop);

}

int Decompress( char * input_filename, char * output_filename)

{

struct _TWord word[MAX_LINES];

int iLineCount=0;

int iLoop;

int wordCount =0;

FILE * infile = fopen(input_filename,"r");

FILE * outfile = fopen(output_filename,"w");

for (iLoop=0; iLoop<MAX_LINES; iLoop++)

{

if (fscanf(infile,"%d %d",&word[iLoop].startingBit, &word[iLoop].iCount)!=EOF)

{

for (int jLoop=0; jLoop<word[iLoop].iCount; jLoop++)

{

fscanf(infile,"%d",&word[iLoop].intstr[jLoop]);

}

ints2Bits(&word[iLoop]);

fprintf(outfile,"%s\n",word[iLoop].bitstr);

}

else

{

break;

}

}

fclose(infile);

fclose(outfile);

return(iLoop);

}

int main()

{

Compress( (char*)"data.txt",(char*)"compressed.txt");

Decompress ((char*) "compressed.txt",(char *) "copydata.txt ");

}