Revision history for LZW
Additions:
http://einstein.informatik.uni-oldenburg.de/rechnernetze/seite8.htm
Additions:
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.
http://www.youtube.com/watch?v=dLvvGXwKUGw
http://www.youtube.com/watch?v=dLvvGXwKUGw
Deletions:
Additions:
Literatur zum LZW
- SkriptRoth2008, S. 18
- SkriptCarl, S. 85
- Karrenberg2005
- SkriptRoth2008, S. 18
- SkriptCarl, S. 85
- Karrenberg2005
Deletions:
Additions:
=====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.
SkriptRoth2008, S. 18 und SkriptCarl, S. 85
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
%%
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.
SkriptRoth2008, S. 18 und SkriptCarl, S. 85
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
%%
