Hallo Cheatah,

ich geh' jetzt nochmal an gif-comp.txt ran.

Ach so, hab Dir faulem Stück noch die Quellen rausgesucht:
http://www.dcs.ed.ac.uk/%7Emxr/gfx/gif87a.txt
http://www.dcs.ed.ac.uk/%7Emxr/gfx/gif89a.txt
http://www.dcs.ed.ac.uk/%7Emxr/gfx/gif-comp.txt
aber nicht angewöhnen, nachher rostest Du womöglich noch ein.
Das wollen wir doch garnicht erst einreissen lassen.

Also nun an der Kompression weiter:

"
Ein paar Worte (vier) sollten noch zur Effizienz verloren werden:
'benutze eine hashing Strategie'. {use a hashing strategy}
Das Durchsuchen der 'string table' kann rechnertechnisch recht
aufwendig sein und hashing ist die Mühe wert.
Beachte auch, daß geradlinige LZW-Kompression die Gefahr beinhaltet
die 'string table' überlaufen zu lassen. Es kann dann passieren, daß
man einen 'code' vorfindet/zusammenstellt, der nicht mehr auf die
Anzahl bits abzubilden geht die für die 'codes' bereitgestellt wurde.
Es gibt verschiedene Möglichkeiten damit umzugehen und GIF verwendet
eine besonders clevere, da kommen wir aber noch hin.

Eine wichtige Sache ist noch zu beachten. Wenn [...]K in der
'string table' ist, dann ist auch [...] vorhanden. Dieses gilt
zu jedem beliebigen Zeitpunkt während der Kompression.
Dieser Umstand legt eine effiziente Methode nahe Strings in der
Tabelle abzuspeichern. Statt die ganzen Strings von K's abzulegen,
kann auch folgendes bedacht werden. Jeder String kann als prefix
plus einem Zeichen betrachtet werden, als [...]K. Wenn man also
[...]K abspeichern will, weiß man, daß [...] bereits vorhanden ist.
Daher kann man auch einfach den code für [...] und das Zeichen
für K ablegen.

Dieses bezieht sich auf Kompression. Dekompression ist vielleicht
schwerer zu verstehen, es ist aber wirklich einfacher zu programmieren.
Wir haben hierbei auch mit einer initialisierten 'string table' anzu-
fangen. Diese Tabelle leiten wir von unserem Wissen über die Zustände
ab die wir annehmen unsere Zeichen im Zeichenstrom annehmen können.
Bei GIF-Dateien steht diese Information im Header, als Anzahl möglicher
Zustände die unsere Pixel annehmen können. Der Charm von LZW ist, daß
dieses alles ist was wir zu wissen haben. Den Rest der Tabelle bauen
wir während der Dekompression auf. Die Kompression ist derart erfolgt,
daß wir niemals einen code im Codestrom antreffen werden den wir nicht
in einen String übersetzen könnten.

Wir müssen etwas "current code" genanntes definieren, das ich als
"<code>" referenzieren werde. Ausserdem noch einen "old-code" den ich
als "<old>" referenzieren werde.
Um anzufangen, laß uns den ersten code untersuchen. Dieses ist jetzt
<code>. Dieser code wird als Darstellung eines Wurzelwertes in der
initialisierten Tabelle vorhanden sein. Schreibe diesen Wurzelwert
in den Ausgangsstrom. Mache dann diesen code zum old-code <old>.
* Laß uns jetzt den nächsten code untersuchen und ihn zu <code>
machen. Er wird möglicherweise nicht in der 'string table' vorhanden
sein, laß uns aber erstmal annehmen, daß er es ist.
Schreibe den String der dem code entspricht in den Ausgangsstrom.
Suche nun das erste Zeichen im String den Du gerade übersetzt hast.
Nenn ihn K. Füge ihn mit dem aus <old> gebildeten prefix [...] zu
einem neuen String [...]K zusammen. Setze diesen String [...]K in
die 'string table' und den old-code <old> auf den aktuellen code <code>.
Wiederhole das Verfahren von dem Punkt an wo ich den Stern '*' gesetzt
habe und Du hast alles.
Lies diesen Abschnitt nochmal wenn Du ihn eben nur überflogen hast!!!

Laß uns die Möglichkeit untersuchen, daß <code> nicht in der 'string
table' vorhanden ist. Erinnere Dich an die Kompression und versuche
zu verstehen was geschieht wenn einen String wie P[...]P[...]PQ im
Eingangsstrom auftaucht. Nimm an, daß P[...] bereits in der 'string
table' steht, P[...]P aber noch nicht.
Der Komprimierer wird P[...] erkennen und feststellen, daß P[...]P
nicht in der 'string table' vorhanden ist. Er wird den code für
P[...] rausschreiben und P[...]P in die 'string table' einfügen.
Dann wird er sich für den nächsten String bis P[...]P durcharbeiten
und herausfinden, daß P[...]P in der Tabelle ist, als der gerade
hinzugefügte code, also wird er den code für P[...]P ausgeben wenn
er P[...]PQ nicht in der Tabelle finden kann.
Der Dekomprimierer hinkt dem Komprimierer immer einen Schritt hinterher.
Wenn der Dekomprimierer den code für P[...]P sieht, wird er diesen
code noch nicht in die 'string table' geschrieben haben haben, weil er
das Anfangszeichen von P[...]P benötigt hätte um den String für den
letzten code, P[...] zusammenzusetzen und den code für P[...]P zu
bilden.

Wie auch immer, wenn ein Dekomprimierer einen code findet den er noch
nicht kennt, wird es stets derjenige sein, der als nächstes der 'string
table' hinzugefügt wird.
So kann er schätzen welches der code sein könnte, und er wird tat-
sächlich immer richtig liegen.
Wenn ich ein Dekomprimierer wäre und den code#124 sähe und meine
'string table' hätte lediglich Einträge bis code#123 hinauf, dann
könnte ich mir vorstellen was code#124 zu sein hätte, könnte ihn
der 'string table' hinzufügen und den String ausgeben.
Wenn code#123 den String generiert hat auf den ich mich hier als [...]
beziehe, dann wird code#124, in diesem speziellen Fall, [...] plus
dem ersten Zeichen von [...] sein. Also füge schlicht das erste
Zeichen von [...] am Ende seinerselbst zu. Nicht schlecht.

Als (sehr gewöhnliches) Beispiel dieses besonderen Falles, laß uns
ein Bild voraussetzen bei welchem die ersten drei Pixel die gleiche
Farbe haben. Mein Datenstrom sieht also etwa so aus: QQQ....
Zur besseren Übersicht, laß uns meinetwegen annehmen, daß wir 32
Farben haben und, daß Q die Farbe color#12 ist.
Der Komprimierer wird die Folge 12,32,... bilden.
(Wenn du nicht weißt warum, dann denke ein Minütchen darüber nach.)
Erinnere Dich daran, daß #32 anfänglich nicht in der Tabelle steht,
da sie nur von #0 bis #31 geht.
Der Dekomprimierer wird #12 sehen und es richtig in die Farbe Q über-
setzen. Dann wird er #32 sehen und noch nicht wissen was das heißt.
Wenn er aber lang genug darüber nachdenkt, kann er sich vorstellen,
daß QQ der Eintrag #32 in der Tabelle sein müsste und, daß QQ die
nächste Ausgabe sein sollte.

Der Pseudocode für die Dekompression sollte also irgendwie so aussehen:

[1] Initialize string table;
     [2] get first code: <code>;
     [3] output the string for <code> to the charstream;
     [4] <old> = <code>;
     [5] <code> <- next code in codestream;
     [6] does <code> exist in the string table?
      (yes: output the string for <code> to the charstream;
            [...] <- translation for <old>;
            K <- first character of translation for <code>;
            add [...]K to the string table;        <old> <- <code>;  )
      (no: [...] <- translation for <old>;
           K <- first character of [...];
           output [...]K to charstream and add it to string table;
           <old> <- <code>
      )
     [7] go to [5];

Auch hier gilt, wenn Du zu Schritt [5] zurückkommst und keine codes
mehr übrig sind, dann bist Du fertig.
Ausgabe von Strings und das auffinden der Anfangszeichen in Strings
sind allesamt ein Effizienzproblem, ich werde aber keine Andeutungen
zu ihrer Lösung machen. Der halbe Spaß an der Programmierung besteht
aus dem Ausdenken dieser Lösungen.
"

So, bin immernoch nicht fertig, aber doch auch rechtschaffen fertig.
Genug für heute.
Es kommen noch einige GIF-Spezialitäten. Nicht viel, aber anscheinend
auch nicht ganz einfach geschrieben. Der Rest dieses Aufsatzes wird
aber wohl auch noch nicht die endgültige Erleuchtung bringen.
Ich baue noch auf einige Informationen in den beiden anderen Texten.
Sollte auch das nicht ausreichen, dann wird die Such in den Algo-
rithmenbiebeln losgehen.

Klaus