Lempel Ziv Walsh
Kompression
MedienTechnik
.bmp
.tiff
.png
.gif
MedienTechnik
Beispiel:
A
B
C
A
B
C
A
B
C
A
B
C
D
Codetabelle
Codetabelle initialisieren
Präfix = ““
Lese nächstes Zeichen A
Muster = Präfix + A
Muster in
Codetabelle ?
=A
ja
01:A
02:B
03:C
Ende
04:D
05:
06:
07:
08:
Präfix = Muster09:
Präfix:
A
nein
Muster in Codetabelle eintragen
Muster:
LZW-Code von Präfix ausgeben
Präfix = A
Output:
LZW-Code von Präfix ausgeben
MedienTechnik
Beispiel:
A
B
C
A
B
C
A
B
C
A
B
C
D
Codetabelle
Codetabelle initialisieren
Präfix = ““
01:A
02:B
03:C
Lese nächstes Zeichen A
Ende
04:D
05: AB
Muster = Präfix + A =AB
06:
07:
08:
Muster in
Präfix = Muster09:
Codetabelle ?
ja
Präfix:
B
A
nein
Muster in Codetabelle eintragen
Muster:
LZW-Code von Präfix ausgeben
Präfix = A
=B
LZW-Code von Präfix ausgeben
Output:
01
MedienTechnik
Beispiel:
A
B
C
A
B
C
A
B
C
A
B
C
D
Codetabelle
Codetabelle initialisieren
Präfix = ““
01:A
02:B
03:C
Lese nächstes Zeichen A
Ende
04:D
05:AB
=BC
Muster = Präfix + A
06: BC
07:
08:
Muster in
Präfix = Muster09:
Codetabelle ?
ja
Präfix:
C
B
nein
Muster in Codetabelle eintragen
Muster:
LZW-Code von Präfix ausgeben
Präfix = A
=C
LZW-Code von Präfix ausgeben
Output:
01 02
MedienTechnik
Beispiel:
A
B
C
A
B
C
A
B
C
A
B
C
D
Codetabelle
Codetabelle initialisieren
Präfix = ““
01:A
02:B
03:C
Lese nächstes Zeichen A
Ende
04:D
05:AB
=CA
Muster = Präfix + A
06:BC
07: CA
08:
Muster in
Präfix = Muster09:
Codetabelle ?
ja
Präfix:
A
C
nein
Muster in Codetabelle eintragen
Muster:
LZW-Code von Präfix ausgeben
Präfix = A
=A
LZW-Code von Präfix ausgeben
Output:
01 02 03
MedienTechnik
Beispiel:
A
B
C
A
B
C
A
B
C
A
B
C
D
Codetabelle
Codetabelle initialisieren
Präfix = ““
01:A
02:B
03:C
Lese nächstes Zeichen A
Ende
04:D
05:AB
=AB
Muster = Präfix + A
06:BC
07: CA
08:
Muster in
Präfix = Muster09:
Codetabelle ?
ja
Präfix:
AB
C
nein
Muster in Codetabelle eintragen
Muster:
LZW-Code von Präfix ausgeben
Präfix = A
LZW-Code von Präfix ausgeben
Output:
01 02 03
MedienTechnik
Beispiel:
A
B
C
A
B
C
A
B
C
A
B
C
D
Codetabelle
Codetabelle initialisieren
Präfix = ““
01:A
02:B
03:C
Lese nächstes Zeichen A
Ende
04:D
05:AB
=CA
Muster = Präfix + A
06:BC
07: CA
08:
Muster in
Präfix = Muster09:
Codetabelle ?
ja
Präfix:
A
C
nein
Muster in Codetabelle eintragen
Muster:
LZW-Code von Präfix ausgeben
Präfix = A
=A
LZW-Code von Präfix ausgeben
Output:
01 02 03
LZW-Komprimierung
MedienTechnik
ABCABCABCABCD
Präfixtabelle begrenzen 4096
Präfixtabelle kann bei
bekannter Codierungsstrategie
rekonstruiert werden
Muster:
Aktion
Ausgabe
A
AB
BC
CA
AB
ABC
CA
CAB
BC
BCA
AB
ABC
ABCD
hat Code
neu AB=04
neu BC=5
neu CA=6
hat Code
neu ABC=7
hat Code
neu CAB=8
hat Code
neu BCA=9
hat Code
hat Code
neu
ABCD
01
A B C D AB
01 02
A B C D AB BC
01 02 03
A B C D AB BC CA
01 02 03
A B C D AB BC CA
01 02 03 04
A B C D AB BC CA ABC
01 02 03 04
A B C D AB BC CA ABC
01 02 03 04 06
A B C D AB BC CA ABC CAB
01 02 03 04 06
A B C D AB BC CA ABC CAB
01 02 03 04 06 05
A B C D AB BC CA ABC CAB BCA
01 02 03 04 06 05
A B C D AB BC CA ABC CAB BCA
01 02 03 04 06 05
A B C D AB BC CA ABC CAB BCA
01 02 03 04 06 05 07 04 A B C D AB BC CA ABC CAB BCA
Erkannte Präfixe

Powerpoint 97