nicht angemeldet
Hallo Cheatah,
da Du ein so'n flinken Jung' bist, sollte ich wohl
besser erstmal zur Kompression durchstarten, es
wird die wohl härteste Nuss des ganzen Unterfangens.
(ob das richtig ist, weiss ich noch nicht)
Ich nehme mir dazu mal
GIF-COMP.TXT
LZW and GIF explained
von Steve Blackstock vor.
LZW = Lempel Ziv Welch.
Dieses Kompressionsverfahren geht zunächst mal davon aus,
daß in Datenströmen sich wiederholende Muster vorhanden
sind. Diese müssten sich herausfiltern/kürzen lassen.
Es wird gesagt, daß das Verarbeitungsverfahren 3 Objekte
handhaben muß:
"the charstream, the codestream, and the string table"
Bei der Kompression ist der 'charstream' der Input,
der 'codestream' der Output und die 'string table' eine Art
temporärer Zwischenzustand. Bei der Dekompression sind
'charstream' und 'codestream' vertauscht.
Der erste Schritt ist die Initialisierung der 'string table'.
Dazu müssen zunächstmal Annahmen gemacht werden.
Hierzu muß eine Codegröße (Anzahl bits) angenommen werden.
12 bits ermöglicht/erfordert eine Menge von 0->FFF hex oder
4096 Einträge in der 'string table'.
Außerdem es muß bekannt sein wieviel Zustände unsere Daten
(character) annehmen können. Unter der Annhame, daß sie 32
Zustände (zB. Farbwerte für jedes Pixel) annehmen können,
kann die 'string table' wie folgt initialisiert werden.
code#0 to character#0,
code#1 to character#1,
...
code#31 to character#31.
Damit wird definiert, daß jeder 'code' von 0 bis 31
auf einen Wurzelwert (root) abgebildet wird.
Es gibt in der Tabelle keine weiteren Einträge mit
dieser Eigenschaft.
Nun geht das Komprimieren los.
Zunächst wird etwas definiert was wir "current prefix" nennen.
Es ist lediglich ein "prefix" {Variable?} in dem wir Sachen
speichern können und womit wir auch vergleichen können.
Wir beziehen uns als "[.c.]" darauf.
Anfangs ist "current prefix" noch leer.
Ferner wird noch ein "current string" definiert in dem dieser
"current prefix" und das nächste Zeichen des Eingangsstroms
gespeichert werden. Ich beziehe mich auf das "current string"
als "[.c.]K", wobei K ein Datum des Eingangsstroms ist.
So, laß uns schauen welches das erste Zeichen des Eingangs-
stroms ist.
Nenn es P und der "current string" wird [.c.]P. (zu diesem
Zeitpunkt ist das natürlich ein 'Wurzelwert'.)
Laß uns jetzt die "string table" absuchen um zu sehen ob
[.c.]P enthalten ist. Es ist es, weil unsere "string table"
derart initialisiert ist, daß jeder mögliche Wurzelwert ent-
halten ist. In diesem Fall brauchen wir nichts weiter zu machen.
Nun wird [.c.]P zum "current prefix" gemacht und das nächste
Zeichen aus dem Eingangsstrom übernommen. Laß es uns Q nennen.
Dadurch wird "current prefix" zu [.c.]Q {=PQ?}.
Jetzt wird die "string table" abgesucht um zu sehen ob [.c.]Q
enthalten ist. Es ist nicht enthalten, also muß etwas getan werden.
[.c.]Q (=PQ) wird als code#32 in die "string table" eingetragen
und [.c.] wird im Ausgangsstrom eingetragen.
Nun geht das Ganze von vorn los, wobei der "current prefix"
schlicht den Wurzelwert P enthält.
Füge weiter Zeichen des Eingangsstroms als [.c.]K hinzu, bis
[.c.]K nicht mehr in der "string table" gefunden werden kann.
Trage dann [.c.]K in der "string table" ein und im Ausgangs-
strom ein.
In Pseudocode ausgedrückt:
[1] Initialize string table;
[2] [.c.] <- empty;
[3] K <- next character in charstream;
[4] Is [.c.]K in string table?
(yes: [.c.] <- [.c.]K;
go to [3];
)
(no: add [.c.]K to the string table;
output the code for [.c.] to the codestream;
[.c.] <- K;
go to [3];
)
It's as simple as that! So einfach ist das! {oder?}
Natürlich, wenn Du zu [3] zurückkommst und im Eingangsstrom
keine Zeichen mehr sind, dann schreibst Du den code für [.c.]
in den Ausgangsstrom und bist fertig.
Du kannst die Tabelle nun wegschmeissen.
Cheatah, hast Du's verstanden? Ich noch nicht.
Es kommt jetzt ein Beispiel, aber erst demnächst in diesem Kino.
Bei GIF-Daten können maximal 256 Zustände (8bit Palette) auf-
treten und ein Datenblock darf doch nur 256 Byte lang werden.
Dieses ist aber der Ausgangsstrom.
Wie lang muß die Tabelle werden?
Vielleicht kommt's ja noch.
Die obige Beschreibung bezieht sich auf standard LZW-Kompression,
GIF-LZW macht einige zusätzliche Annahmen und kann auch etwas
vereinfachen.
Klaus