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
 c=c%10;
 if(c<=5)   // make atleast 50% data is 0 for testing compression
 {c=0;}
 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;
 for(l=0;l<S;l++)
 {
 for(k=0;k<R;k++)
 {
 for(i=0;i<P;i++)
 {
 for(j=0;j<Q;j++)
 {
 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++)
 {
 if(EKMR[i][j]!=0)
{
 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
}
						}
	if(z==1)
	{
	FW2[z]=count1-1;
	}
	else
		{
			FW2[z]=count1+FW2[z-1];//enter total non zero number till
		}
				count1=0;
				z++; //increment of 3rd array
			}

Now calculate the ratio data compression rate

 float ratio= (S*P)*(R*Q);
		 int r=x+y+z;
		 ratio=r/ratio;
		 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

Advertisements

About kishor datta gupta

Graduate Research Assistant at University of Memphis Software Engineer at Silicon Orchard LTD. Former Research Assistant at Lamar University Former Software Engineer at Samsung R&D Institute Bangladesh Studies Ph.D. Computer Science at University of Memphis Studied Masters of Science in Computer Sciences at Lamar University Studied BSC in CSE at Khulna University of Engineering and Technology Studied HSC (completed) at Chittagang college 04-06 Studied High school at ST. Placid's High School'04 Studied Junior Secondary School at Saint Mary's School Lives in Memphis, Tennessee
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