prev up inhalt next

LZW-Komprimierung (Lempel/Ziv/Welch, 1984)

Ein wichtiger Bestandteil des GIF-Formates ist die LZW-Komprimierung für Zeichenketten.

Starte mit Stringtabelle, gefüllt mit characters, und fülle sie mit Verweisen auf bereits gelesene Substrings.

x := get_char();
w := x;
repeat
   x := get_char();
   if wx in Tabelle
      then w := wx
      else put_string(code(w));
           trage wx in Tabelle ein
           w := x
   endif
until x = EOF



w Input Output String Code
      a 1
      b 2
      c 3
  a      
a b 1 ab 4
b a 2 ba 5
a b      
ab c 4 abc 6
c b 3 cb 7
b a      
ba b 5 bab 8
b a      
ba b      
bab a 8 baba 9
a a 1 aa 10
a a      
aa a 10 aaa 11
a a      
aa a      
aaa a 11 aaaa 12

Entwicklung von Output und Tabelle für den Input ababcbababaaaaaaa
String    
Präfix- Erwei-  
String- terungs-  
Index character Code
  a 1
  b 2
  c 3
1 b 4
2 a 5
4 c 6
3 b 7
5 b 8
8 a 9
1 a 10
10 a 11
11 a 12
Implementation der
Stringtabelle


prev up inhalt next