#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//#include <mpi.h>

/**
 * LZW-Algorithmus
 * @author Andreas Tobola
 * @since Januar 2009
 * Implementierung anhand der Anleitung aus dem
 * Skript 'Informationstheorie und Codierung' auf S. 85
 */
 
char w[32000][100];  // Wörterbuch
unsigned short dicsize = 0;  
 
void dicinsert(char p[])
{
    memcpy(w[dicsize], p, 100);
    dicsize++;
}

 
unsigned short dicsearch(char p[])
{
    unsigned short i;
    for (i=0; i<dicsize; i++)
    {
        if (strcmp(p, w[i]) == 0)
            return (i+1);
    }
    return 0;
}

void dicprint()
{
    unsigned short i;
    for (i=0; i<dicsize; i++)
    {
        printf("%d -> %s \n",i+1, w[i]);
    }
}
 
int main(int argc, char** argv)
{
   FILE *fd;
   char i;   // Input character
   char pi;  // Previous input character
   char p[100];  // Pharse
   unsigned short k = 0;
   unsigned short ldi; // last dic index
   unsigned long iBytes = 0;
   unsigned long oBytes = 0;
   
   fd = fopen(argv[1], "rb");
   if (fd == 0)
   {  
      printf("Can not open file %s", argv[1]);
      return 1;
   }  
   
   // Wörterbuch mit Alphabet initialisieren
   while ((i = fgetc(fd)) != EOF)
   {
        i = pi - i;
       
        p[0]=i;
        p[1]=0;
   
        if (dicsearch(p)==0)
            dicinsert(p);
           
        pi = i;
   }
   
   rewind(fd);

   // Folgen suchen und ind das Wörterbuch hinzufügen
   
   while ((i = fgetc(fd)) != EOF)
   {
        unsigned short di; // last dic index
       
        i = pi - i;
       
        iBytes++;  // Count input bytes
       
        p[k]=i;
        p[k+1]=0;
       
        //printf("%c ... '%s' ",i,p);              
       
        di = dicsearch(p);
       
        if (di==0)
        {      
            //printf("\t %2d \t dic. entry: '%s'", ldi, p);
            dicinsert(p);          
            p[0] = p[k]; // Nächste Folge beginnt mit dem letzten Zeichen der aktuellen Folge.
            p[1] = 0;
            k=0;
            ldi = dicsearch(p);
            oBytes++; //count output bytes
           
        }
        else
        {
            ldi = di;
        }
       
        k++;
       
        //puts(" ");
       
        pi = i;
       
       
   }  
   
 
   //printf("  ... '%s'\t %d  (last code)\n", p, ldi);
   oBytes++;

   printf("Input:  %d\n", iBytes);
   printf("Output: %d\n", oBytes);
   printf("Compr. ratio: %.1f %\n", ((float)oBytes)/((float)iBytes)*100);
   printf("Dictonary: %d entries\n", dicsize);
     
   //dicprint();


   return 0;
}

./lzw2 Testdatei
Input:  832
Output: 607
Compr. ratio: 73.0 %
Dictonary: 808 entries