=====LZW=====

LZW steht für Lampel-Ziv-Welch und ist ein 1984 entwickeltes Kopressionsverfahren, das u.a. in Kompressionsprogrammen zip, gzip, bzip und Bildformaten gif, tiff Verwndung fand.

Literatur zum LZW
	- SkriptRoth2008, S. 18 
	- SkriptCarl, S. 85
	- Karrenberg2005


Beispielprogramm für die Komprimierung in [[C]] für die Kodierung von Dateien
%%(c)
#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;
}
%%


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



http://einstein.informatik.uni-oldenburg.de/rechnernetze/seite8.htm
http://www.youtube.com/watch?v=dLvvGXwKUGw


----
Siehe auch {{backlinks}}