Issue implementing algorithm of Lempel Ziv

[napsak]

I have been struggling with this program for many hours. I've also looked through most all of the 114 posts listed here for c++ relevant to my issue. The problem is with my array that holds code word not seen yet, it gets replaced everytime, letme explain.
I have my dictionary of code words setup as a struct with two
variables "code" and "key". I have no problem creating a dictionary
and I can even add to it. What happens is I do this:
STRING = get input character
WHILE there are still input characters
CHARACTER = get input character
IF STRING+CHARACTER is in the string table then
STRING = STRING+character
ELSE
output the code for STRING
add STRING+CHARACTER to the string table
STRING = CHARACTER
END of IF
END of WHILE

Everything works great the first time through the loop. Then what
happens is not good. The buffer I use to hold the STRING+CHARACTER
writes itself into all the following new structs I create that hold
more code words for the dictionary. Unfortunately my code is not very
clear, but I seem to know it inside and out. Could anyone please help direct me to what I can do to
possibly get my issue resolved? Thank you for your time and
consideration. attachments enclosed that can be opened in notepad.

Bit of code that is a member function of the user defined struct follows:

void token::newTable(token oldTable[])

{

ifstream input;

  input.open("text.txt", ios::in);



  if (!input)

    {

    cerr<<"Error opening file:" <<endl;

    return;

    }

  token newTable[5];

  int codeCntr=3;

  for(int j=0;j<=codeCntr;j++){

cout <<oldTable[j].key <<endl;

    newTable[j]=oldTable[j];

cout <<newTable[j].code <<endl;}

  int found=0;

  int k=0, h=0, first_time=1;//, loopCntr=1;

first_time=0;

//char current, next;

  char c[20]="";

  char tempString[20]="";

  char buffer[20]="";

// char *emptyArray[20]="     ";

ofstream outdata;

outdata.open("outdata.txt");

//buffer[30]=emptyArray[30];

//cout<<buffer<<"<---intial buffer"<<endl;

input.get(*tempString);

strcat(buffer,tempString);

  while(!input.eof())

    {

cout<< newTable[codeCntr].key<<endl<<endl;

//for(int m=0;m<1;m++)

//{

//buffer=emptyArray;

cout<< newTable[codeCntr].key<<endl;

//}

//for(int m=0;m<5;m++)

//buffer[m]=0;

input.get(*c);

//      strcat(buffer,tempString);

      strcat(buffer,c);



cout <<c <<"<---c value" <<endl;

cout <<buffer<<"<--buffer value"<<endl;



cout <<tempString <<"<---tempString"<<endl;

found=0;

for(k=0;k<=codeCntr;k++)

{

usleep(1600);

cout <<newTable[k].key <<"<---newTable character"<<endl;;

cout <<buffer<<" b4 if statement" <<endl;



  if(char(newTable[k].key)==char(buffer)&&found==0)

  {

        tempString=buffer;

        cout<<"found it**************" <<endl<<k<<endl;

for(int m=0;m<1;m++)

buffer[m]=0;

found=1;

//for(int l=0;l<10;l++)

//  buffer[30]=emptyArray[30];

//  strcpy(tempString,"    ");

  }

}

 if(found==0) 

{

h=0;

codeCntr++;

//char bufferHolder[20]=" ";



//bufferHolder=buffer;

      newTable[codeCntr].code=codeCntr;

cout<<newTable[codeCntr].code<<" newTable code"<<endl;

cout<<   (newTable[codeCntr].key=buffer)<<endl;

cout<< newTable[codeCntr].key<<endl;

strcpy(buffer,"\0");

 tempString=c;

cout<<tempString<<"<--tempString in no found" <<endl;

cout<<c<<"<--c value" <<endl;

cout<<codeCntr<<" = newTable.code"<<endl;

//for(int m=0;m<5;m++)

//{

//buffer=emptyArray;

cout<< newTable[codeCntr].key<<endl;

cout<<buffer<<"buffer after delete"<<endl;

cout<< newTable[codeCntr].key<<endl;

  

cout<<"in !found statement" <<endl;

}



    }//end first while loop



//for(int h=0;h<3;h++)

//cout<<  newTable[h].key;

input.close();

outdata.close();

return; 

}

here is all other code including above:

Script started on Sun Apr 17 05:51:07 2005
$ cat zipa.cpp

#include <iostream>

#include <cstring>

#include <fstream.h>

#include <unistd.h>

#include <stdlib.h>

#include <string.h>





using std::itoa;

using std::cout;

using std::endl;

using std::ifstream;

class token

{

  public:

    token(int=0, char* ="        ");

    token setTable(int);

    void newTable(token[]);

    ~token();

//  private:

    int code;

    char * key;

};

//*************************************************************

token::token(int newCode, char *newKey)

{

  code=newCode>0 ? newCode:1;

  key=new char [strlen(newKey)+1];

  strcpy(key,newKey);

}

//*************************************************************

token::~token()

{

}

//*************************************************************

token token::setTable(int q)

{

token table[30];

  char *AlphaArray[]={"A","B","C","D"};

  table[q].key=AlphaArray[q];



  table[q].code=q;

//cout<< "in setTable member function"<<endl;

//cout<< AlphaArray[q] <<endl;

//cout<< table[q].key <<endl;

return table[q];

}

//*************************************************************

void token::newTable(token oldTable[])

{

ifstream input;

  input.open("text.txt", ios::in);



  if (!input)

    {

    cerr<<"Error opening file:" <<endl;

    return;

    }

  token newTable[5];

  int codeCntr=3;

  for(int j=0;j<=codeCntr;j++){

cout <<oldTable[j].key <<endl;

    newTable[j]=oldTable[j];

cout <<newTable[j].code <<endl;}

  int found=0;

  int k=0, h=0, first_time=1;//, loopCntr=1;

first_time=0;

//char current, next;

  char c[20]="";

  char tempString[20]="";

  char buffer[20]="";

// char *emptyArray[20]="     ";

ofstream outdata;

outdata.open("outdata.txt");

//buffer[30]=emptyArray[30];

//cout<<buffer<<"<---intial buffer"<<endl;

input.get(*tempString);

strcat(buffer,tempString);

  while(!input.eof())

    {

cout<< newTable[codeCntr].key<<endl<<endl;

//for(int m=0;m<1;m++)

//{

//buffer=emptyArray;

cout<< newTable[codeCntr].key<<endl;

//}

//for(int m=0;m<5;m++)

//buffer[m]=0;

input.get(*c);

//      strcat(buffer,tempString);

      strcat(buffer,c);



cout <<c <<"<---c value" <<endl;

cout <<buffer<<"<--buffer value"<<endl;



cout <<tempString <<"<---tempString"<<endl;

found=0;

for(k=0;k<=codeCntr;k++)

{

usleep(1600);

cout <<newTable[k].key <<"<---newTable character"<<endl;;

cout <<buffer<<" b4 if statement" <<endl;



  if(char(newTable[k].key)==char(buffer)&&found==0)

  {

        tempString=buffer;

        cout<<"found it**************" <<endl<<k<<endl;

for(int m=0;m<1;m++)

buffer[m]=0;

found=1;

//for(int l=0;l<10;l++)

//  buffer[30]=emptyArray[30];

//  strcpy(tempString,"    ");

  }

}

 if(found==0) 

{

h=0;

codeCntr++;

//char bufferHolder[20]=" ";



//bufferHolder=buffer;

      newTable[codeCntr].code=codeCntr;

cout<<newTable[codeCntr].code<<" newTable code"<<endl;

cout<<   (newTable[codeCntr].key=buffer)<<endl;

cout<< newTable[codeCntr].key<<endl;

strcpy(buffer,"\0");

	tempString=c;

cout<<tempString<<"<--tempString in no found" <<endl;

cout<<c<<"<--c value" <<endl;

cout<<codeCntr<<" = newTable.code"<<endl;

//for(int m=0;m<5;m++)

//{

//buffer=emptyArray;

cout<< newTable[codeCntr].key<<endl;

cout<<buffer<<"buffer after delete"<<endl;

cout<< newTable[codeCntr].key<<endl;

  

cout<<"in !found statement" <<endl;

}



    }//end first while loop



//for(int h=0;h<3;h++)

//cout<<  newTable[h].key;

input.close();

outdata.close();

return; 

}

//*************************************************************

int main()

{  

  token table [10];



//  char wordArray[50];

//  char tempLetter;

/*  char charValue;

  int intValue;

  int matched;

  int codeCntr=4;

  int wordCntr=0;

*/

  int codeCntr=3;//This is how many letters are in dictionary

  int i; 

/*  ifstream indata;

  indata.open("text.txt", ios::nocreate);



  if (!indata)

    {

    cerr<<"Error opening file:" <<endl;

    return 0;

    }*/

  for(i=0;i<=codeCntr;i++){

//indata >>tempLetter;

    table[i]=table[i].setTable(i);

//cout<<table[i].key <<"from main" <<endl;

}



  table[0].newTable(table);

/* 

  while (!indata.eof())

    {

    matched=0;

    while (!matched)

    {

      codefound=0;

      while(!codefound)

      {

        if( 

      codeCntr++;

        

  

  nextCode=getToken(indata);

cout<<value <<endl;

*/

return 0;

}



$ g++ zipa.cpp

$ a.out

A

0

B

1

C

2

D

3

D



D

B<---c value

AB<--buffer value

A<---tempString

A<---newTable character

AB b4 if statement

B<---newTable character

AB b4 if statement

C<---newTable character

AB b4 if statement

D<---newTable character

AB b4 if statement

4 newTable code

AB

AB

B<--tempString in no found

B<--c value

4 = newTable.code



buffer after delete



in !found statement







a<---c value

a<--buffer value

B<---tempString

A<---newTable character

a b4 if statement

B<---newTable character

a b4 if statement

C<---newTable character

a b4 if statement

D<---newTable character

a b4 if statement

a<---newTable character

a b4 if statement

found it**************

4







B<---c value

B<--buffer value

a<---tempString

A<---newTable character

B b4 if statement

B<---newTable character

B b4 if statement

C<---newTable character

B b4 if statement

D<---newTable character

B b4 if statement

B<---newTable character

B b4 if statement

found it**************

4







A<---c value

A<--buffer value

B<---tempString

A<---newTable character

A b4 if statement

B<---newTable character

A b4 if statement

C<---newTable character

A b4 if statement

D<---newTable character

A b4 if statement

A<---newTable character

A b4 if statement

found it**************

4







B<---c value

B<--buffer value

A<---tempString

A<---newTable character

B b4 if statement

B<---newTable character

B b4 if statement

C<---newTable character

B b4 if statement

D<---newTable character

B b4 if statement

B<---newTable character

B b4 if statement

found it**************

4







C<---c value

C<--buffer value

B<---tempString

A<---newTable character

C b4 if statement

B<---newTable character

C b4 if statement

C<---newTable character

C b4 if statement

D<---newTable character

C b4 if statement

C<---newTable character

C b4 if statement

found it**************

4







B<---c value

B<--buffer value

C<---tempString

A<---newTable character

B b4 if statement

B<---newTable character

B b4 if statement

C<---newTable character

B b4 if statement

D<---newTable character

B b4 if statement

B<---newTable character

B b4 if statement

found it**************

4









<---c value



<--buffer value

B<---tempString

A<---newTable character



 b4 if statement

B<---newTable character



 b4 if statement

C<---newTable character



 b4 if statement

D<---newTable character



 b4 if statement



<---newTable character



 b4 if statement

found it**************

4









<---c value



<--buffer value



<---tempString

A<---newTable character



 b4 if statement

B<---newTable character



 b4 if statement

C<---newTable character



 b4 if statement

D<---newTable character



 b4 if statement



<---newTable character



 b4 if statement

found it**************

4

$ ^Z

$ ^C

$ ^D


script done on Sun Apr 17 05:51:44 2005

[Valmont]

This is horrible. Give me some compilable code so I can work straight away. Remove everything not needed. And initiatate any container that should be on startup ( othewise post the text file as well). I can't work with this.

[napsak]

Sorry, I know this is terrible code. I am not very good with programming. I really appreciate you taking the time to post. I'm reading about containers now so I can see how to make this program easier to work with I am also notating the program and removing unneeded stuff so things make more sense then the garbage I had.

[napsak]

Great! Instead of using the user defined struct I had I am going to instantiate an integer and character vector for the dictionary with the help from my book "A First Book of C++ From Here to There"

[napsak]

Yes, please disregard that first bunch of mess of code. Here is an update on how is looking so far:

Script started on Sun Apr 17 17:29:35 2005
$ cat zipc.cpp

#include <iostream>

#include <cstring>

#include <fstream.h>

#include <unistd.h>

#include <stdlib.h>

#include <string.h>

#include <vector.h>

//----------------------------------------------------------

/* global variable that is number of characters dictionary 

starts with */

  int NUMELS = 10;



using namespace std;

using std::cout;

using std::endl;

using std::ifstream;

using std::string;//Thanks HighCommander4

using std::vector;



void compressText(vector<int> &, vector<char> &);



//*************************************************************







//*************************************************************





//*************************************************************



//*************************************************************

void compressText(vector<int> &code, vector<char> &key)

{

//----------------------------------------------------------

/* opens input file to read from and checks for errors*/

  ifstream input;

  input.open("text.txt", ios::nocreate);



  if (!input)

    {

    cerr<<"Error opening file:" <<endl;

    return;

    }  

//----------------------------------------------------------

/* opens output file to hopefully write compressed data to*/

  ofstream outdata;

  outdata.open("outdata.txt");

//----------------------------------------------------------



  char c[20]="";  

  char buffer[20]="";

  char tempString[20]="";

  int codeCntr = NUMELS;



  int found=0, k;



input.get(*tempString);

strcat(buffer,tempString);

//----------------------------------------------------------

/* reads in data until end of file. for loop checks if data 

contained in buffer has been seen before. for now if it has 

found a macth it prints a message.  If not found it adds the 

data in buffer to vector*/



  while(!input.eof())

    {



      input.get(*c);

      strcat(buffer,c);

cout<<c <<"<--c value" <<endl;



      found=0;

    for(k=0;k<=codeCntr;k++)

      {

cout<< key[k]<<"<---key value"<<endl;

cout<< buffer<<"<---buffer value"<<endl;

        usleep(1600);



      if(key[k]==*(buffer)&&found==0)

        {

          tempString=buffer;

	  found=1;

cout<<"found it**************" <<endl<<key[k]<<endl;

        }

      }

    if(found==0) 

      {

        codeCntr++;

	code.insert(code.begin() + codeCntr,codeCntr);

	key.insert(key.begin() + codeCntr,*buffer);

        tempString=c;



cout<<"in !found statement" <<endl;

      }



    }//end  while loop



outdata.close();

return; 

}

//*************************************************************

int main()

{  

  int a[NUMELS];

  char b[NUMELS];

  int i;

//----------------------------------------------------------

//opens text file to compress and checks for opening correct



  ifstream indata;

  indata.open("text.txt", ios::nocreate);



  if (!indata)

    {

    cerr<<"Error opening file:" <<endl;

    return 0;

    }

//----------------------------------------------------------

//populates dictionary of known letters in text



vector<int> code(a, a + NUMELS);

vector<char> key(b, b + NUMELS);



//----------------------------------------------------------

//call to function to start compression of text file



  compressText(code, key);

  for(i=0;i<NUMELS;i++)

    



return 0;

}

//*************************************************************



$ g++ zipc.cpp

$ a.out

B<--c value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

Segmentation Fault

$ ^D


script done on Sun Apr 17 17:29:56 2005

[Valmont]

What's up with the spaces between every line of code napsak?

And this seems useless as well

$ g++ zipc.cpp

$ a.out

B<--c value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

 <---key value

AB<---buffer value

Segmentation Fault

$ ^D


script done on Sun Apr 17 17:29:56 2005

And once you got something up and working, make sure to tell what is suppose to happen and everything you know. Don't forget, I am a complete stranger and possibly not so clever. The better you communicate, the faster and better I can work.

[napsak]

Originally Posted by Valmont

And once you got something up and working, make sure to tell what is suppose to happen and everything you know. ... The better you communicate, the faster and better I can work.

Definitely, will do. Sorry for the spaces in the code I inserted I will try to make sure it is a little more concise. What I am trying to accomplish here is implementing an algorithm for compression and decompression using Lempel-Ziv. I need to read in data from a input file and then write compressed data to an output file. I am supposed to develop separate classes (with appropriate member functions) for compression and decompression but, I would be happy just to get something to work. I should also verify it was correctly implemented by doing a diff and wc of original file, but I still need to read man pages on these commands. The Lempel-Ziv algorithm is something like this:

STRING = get input character
    WHILE there are still input characters DO
        CHARACTER = get input character
        IF STRING+CHARACTER is in the string table then
            STRING = STRING+character
        ELSE
            output the code for STRING
            add STRING+CHARACTER to the string table
            STRING = CHARACTER
        END of IF
    END of WHILE
    output the code for STRING

obtained from: Lempel-Ziv Compression by Mark Nelson

The assignment is suppose to work through a server client program but, for know I think that is a little beyond me. I just want to focus on understanding the code behind this algorithm. Once again thank you very much for your guidance, it is really helping me get a better understanding of what is going on.

[Valmont]

Bloody C. The code is fairly easy but I am not confident with C so I cannot translate it.

@Redhead, can you take a peek on the link he gave. The code is down the page.

@napsak.
So you want a translation to C++?
I can't do that tonight. It is late here in europe. I'll check it out tomorrow after work, which is noon new-york time.

[redhead]

Originally Posted by Valmont

Bloody C. The code is fairly easy but I am not confident with C so I cannot translate it.
@Redhead, can you take a peek on the link he gave. The code is down the page

I'm looking at it now, but I'm at work so it migth be a few hours befor I get time to realy look into it.. On first glance it seems pretty straight forward tho..

@napsak.
Sorry I didn't pitch in untill now, but the first section of code you provided was so messy and in C++ (which I know Valmont lives and breeth for) so I couldn't wrap my head around it, and decided to wait it out, and see where this might end up.

[napsak]

Redhead and Valmont, Thank you both for yourhelp with trying to get this program running. Unfortunately I could not work with vectors b/c Icould not find out how to make the char vector hold more then one value? But , i did go back to orignal code and worked it out. What my whole problem was is that I was not creating a new struct to add data too.

 if(found==0) 
{

      newTable[codeCntr+1].code=codeCntr+1;
      newTable[codeCntr+1].key=buffer;
//strcpy(buffer,emptyArray);
	tempString=c;
cout<<"in !found statement" <<endl;
cout<<newTable[codeCntr+1].code<<"<--added to dictionary"<<endl;
cout<<newTable[codeCntr+1].key<<"<--added to dictionary"<<endl;
codeCntr++;
strcpy(buffer,emptyArray);
}

I know this does not make sense most likely, but it was just an elementary item such as not creating a 'new' struct that prevented this guy from running right. I will post the code revised and working correctly sometime next week. I really hope you two did not get overally envolved with translating the code from Mark Nelson b/c I got mine to work, thank you again and take care. Is there anything I can do to help you guys out ,besides vote for your reputation? (Can't send you guys money b/c i'm poor college dude).

[Valmont]

Well, at least this format is readable. The previous thing you posted was a monster .
Next time, make your format sort of "pretty". So we can read it.

[napsak]

Thanks to extreme help and work, the compression is done.
Template used for dictionary was a list.
Here is compress code: This code is credited to Rui Wang

class compress
{
private:
        ifstream sourceFile;
        ofstream compressedFile;
        list<string> table;
        list<string>::iterator table_string;

        void initialize()
        {
                string c;

                for (int i=-128; i<128; i++)
                {
                        c = (char)i;
                        table.push_back(c);
                }
        }

        int searchTable(string str)
        {
                int pos = 0;
                bool strFouned = false;

                table_string = table.begin();

                while (table_string != table.end())
                {
                        if (str == *table_string)
                        {
                                strFouned = true;
                                break;
                        }
                        table_string ++;
                        pos++;
                }

                if (strFouned)
                {
                        return pos;
                }
                else
                {
                        return -1;
                }
        }

        void writeCode(int code)
        {
                int val;

                val = code/255;
                compressedFile.put((char)val);
                val = code%255;
                compressedFile.put((char)val);
        }

public:
        compress(char *inputFile, char *outputFile)
        {
                sourceFile.open(inputFile, ios::binary);

                if (!sourceFile)
                {
                        cout << "File could not be opened!" << endl;
                }

                compressedFile.open(outputFile, ios::binary);
                initialize();
        }
	~compress()
        {
                if (sourceFile)
                {
                        sourceFile.close();
                        compressedFile.close();
                }
        }

        void doCompress()
        {
                string buffer, tempString, c;
                int pos;

                buffer = sourceFile.get();

                c = sourceFile.get();
                while (!sourceFile.eof())
                {
                        tempString = buffer + c;
                        pos = searchTable(tempString);

                        if (pos == -1)
                        {
                                pos = searchTable(buffer);
                                writeCode(pos);
                                table.push_back(tempString);
                                buffer = c;
                        }
                        else
                        {
                                buffer = tempString;
                        }
                        c = sourceFile.get();
                }

                pos = searchTable(buffer);
                if (pos == -1)
		{
                        pos = table.size();
                }
                writeCode(pos);
        }
};

usage in main

compress *Compress = new compress(argv[2],argv[3]);

Compress->doCompress();

delete Compress;

[Valmont]

I'll write a console app later where the parsing and compressing is visualized .