Wiki source for LZW


Show raw source

=====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}}
Valid XHTML :: Valid CSS: :: Powered by WikkaWiki