Efficient representation of multi dimensional array operation and compressed data programming in cpp

This is based on an article of ” Efficient Representation Scheme For Scheme for multidimensional Array Operations” by Chun-Yan lin, Jen-Shiuh Liu and Yeh-ching Chung Member of IEEE published in march 2002.

in there paper they propose a new scheme called extended Karnaugh map representation (EKMR).

there approach can shortly described as they take traditional matrix representation on short form TMR, they convert in a 2d array by a very suitable algorithom.

And from these EKMR they generate three  different array which consists all the information of TMR taking most common data as a variant so takes less memory.

First take our TMR as a four dimensional array . we need to convert in a two dimentional EKMR, and we want to take ” 0″ as most common data.

so the cpp coding goes as like

//S,P,R,Q are the lentgh of each dimention of TMR
#define S 6
#define R 6
#define P 6
#define Q 6//j
//declaration of TMR and 2d EKMR
long TMR[S][R][P][Q];
long EKMR[S*P][R*Q];
using std::cout;
using std::cin;
using std::endl;

//creation of 4d matrix TKMR
void construct()
int l,k,i,j,c=0;
for(l=0;l<S;l++)//first dimension array loop
 for(k=0;k<R;k++)//second dimension array loop
 for(i=0;i<P;i++) //third dimension array loop
 for(j=0;j<Q;j++) //4th dimension array loop
 c= rand();     //taking a random value for data
 if(c<=5)   // make atleast 50% data is 0 for testing compression
 TMR[l][k][i][j]=c;//take the value in the array


now making of TMR to EKMR. or u can say that conversion of a 4D array in 2D array

int l,k,i,j,c=0;
 TMR[l][k][i][j]= EKMR[i * S + l][j * R + k] ;

now we know “0” is most common . So if we take 3 array and first array consists of all non zero value of EKMR and 2nd array consist of column position of these value and 3rd array consists number of the nonzero value in each row plus already counted row. So the code for this is

long *FW,*FW1,*FW2; // declaration of 3 1D array
int x=0;
int y=0;
int count=0;
int count1=1;
int count2=0;
int z=1;
FW2[0]=0;//assign 3rd arrays first value 0

//one dimensional array created
for(int i=0;i<(S*P);i++)
for(int j=0;j<(R*Q);j++)
 FW[x]=EKMR[i][j]; //ekmr value here
FW1[y]=j; //valuer position in column
		x++; // increment of first array
		y++;//increment of 2nd array
			FW2[z]=count1+FW2[z-1];//enter total non zero number till
				z++; //increment of 3rd array

Now calculate the ratio data compression rate

 float ratio= (S*P)*(R*Q);
		 int r=x+y+z;
		 cout<<"ratio is "<

the rare of data compressed proportionally depend on percentage of common data or the length of dimension.

this technique can be very efficient for image compressing .
so view this table for comparisoncode courtesy to Ashis chakrabatry


About kishordgupta

A software developer
This entry was posted in CPP, DATABASE and tagged , , , , , , , , . Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s