nicht angemeldet
Hallo Cheatah,
nun zu den GIF-Variationen diese Themas.
"
Im Headerteil einer GIF-Datei, im Raster-Data-stream, gibt es ein
'code size' genanntes Feld. Ein unglücklicher Name für dieses Feld,
wir müssen aber damit leben. In Wirklichkeit ist es die Grundgröße,
die 'root size'.
Die tatsächliche Anzahl der 'compression codes' in bits schwankt
während der Kompression/Dekompression und ich werde die Größe
"compression size" nennen.
Die Tabelle enthält anfänglich, wie üblich alle Wurzelwerte der codes,
aber oben werden noch zwei spezielle codes angefügt. Nimm an, Du hast
eine code-Größe ("code size") die üblicherweise der Anzahl der Bits
pro Pixel im Bild entspricht, also N. Wenn die Anzahl der Bits/Pixel
eins ist, dann muß N gleich 2 sein: die Wurzelwerte belegen die
Plätze #0 und #1 der anfänglichen Tabelle und die beiden speziellen
codes belegen die Plätze #4 und #5.
In jedem anderen Fall, ist N die Anzahl von Pixeln pro Byte, die
Wurzelwerte belegen die Plätze #0 bis #(2**N-1) und diese beiden
speziellen codes (2**N) und (2**N + 1). Die anfängliche Größe der
Kompressionscodes wird N+1 bits pro code betragen.
Wenn Du am Komprimieren bist, gibst Du die codes jeweils (N+1) bitweise
aus und wenn Du am Dekodieren bist holst Du Dir jeweils (N+1) bits aus
dem Eingangstrom.
Nun zu den beiden speziellen codes: <CC> oder 'clear code' ist (2**N)
und <EOI> oder 'end of information' ist (2**N+1).
<CC> sagt dem Kompressor, daß die 'String table' neu aufzubauen ist
und, daß die 'compression size' auf (N+1) zurückzusetzen ist.
<EOI> bedeutet, daß nichts mehr im 'codestraem' vorhanden ist.
Wenn Du am Kodieren oder Dekodieren bist, solltest Du Sachen die der
'string table' hinzuzufügen sind ab <CC>+2 einsetzen.
Wenn Du am Kodieren bist, solltest Du <CC> als allerersten code aus-
geben und danach immer wenn Du code #4095 (hex FFF) erreichst, da GIF
keine 'compression sizes' erlaubt die größer als 12 bits sind.
Wenn Du am Dekodieren bist, solltest Du Deine 'string table' neu
initialisieren wann immer Du <CC> siehst. Die variablen 'compression
sizes' sind wahrlich keine besondere Aufgabe.
Wenn Du am Kodieren bist, fängst Du mit einer 'compression size' von
(N+1) bit an, und, wann immer Du den code (2**(compression size)-1)
ausgibst haust Du die 'compression size' um ein bit hoch. So wird
der nächste code den Du ausgibst um ein Bit länger. Denk aber daran,
daß die längste 'compression size' 12 bits ist, was einem code von
4095 enstpricht. Wenn Du so weit gekommen bist, mußt Du <CC> als
nächsten code ausgeben und neu aufsetzen {and start over}.
Wenn Du dekodierst, mußt Du die 'compression size' erhöhen SOBALD Du
#(2**(compression size) - 1) in die 'string table' schreibst.
Der nächste code den Du LIEST, wird ein bit länger sein.
Mach nicht den Fehler mit dem Hinzufügen des codes (2**compression
size) zu warten. Du wirst dann schon ein bit des vorhergehenden codes
verloren haben.
Das Packen der codes in den Datenstrom der raster data ist auch ein
potentieller Stolperstein für den Anfänger.
Das niederwertigste Bit im code sollte mit dem niedrigsten verfügbaren
bit im ersten erreichbaren byte im codestream übereinstimmen.
Als Beispiel, wenn Du mit 5-bit compression codes anfängst, und Deine
ersten drei codes <abcde>, <fghij>, <klmno>, sind, wobei e, j, und o
bit#0 darstellen, dann sollte Dein codestream lauten:
byte#0: hijabcde
byte#1: .klmnofg
Also, der Unterschied zwischen reinem LZW und GIF-LZW ist:
zwei zusätzliche spezielle codes und
variable compression sizes.
Wenn Du also LZW verstehst und diese Unterschiede auch, dann verstehst
Du alles!
Nur als eine Art P.S., Du magst bemerkt haben, daß ein Komprimierer
ein klein wenig spielraum beim Komprimieren hat. Ich hab einen
'gierigen' Ansatz für die Kompression beschrieben indem ich soviel
Eingangszeichen wie möglich zusammengeklaubt habe bevor ich ein code
ausgegeben habe. Dieses ist tatsächlich die übliche LZW-Art Sachen zu
machen, und, dieses wird die besten Kompressionsergebnisse ergeben.
Aber, es gibt keine Regel die besagt, daß Du nicht irgendwo zwischen-
durch aufhören kannst um ein code für ein Prefix auszugeben, egal ob
es in der Tabelle steht oder nicht, und dann erst den String und das
nächste Zeichen in die 'string table' zu setzen. Es gibt verschiedene
Gründe das so tun zu wollen, besonders wenn die Strings besonders lang
werden und hashing schwierig machen. Wenn Du es für erforderlich hältst,
dann tu es.
"
Soweit dieser letzte Teil.
Weißt Du nun was böhmische Dörfer sind?
Ich glaub ich weiß auch das nicht mehr.
Ich bin immer mehr dazu übergegangen nur noch zu übersetzen,
wohl vor allem weil ich nicht mehr mitkam.
Ich werde mir das Ganze nochmal vornehmen.
Ein paar Randbedingungen sind ja doch noch rübergekommen,
aber den Algorithmus zu implementieren würde ich mich noch nicht trauen.
Klaus
PS: mal sehen ob das was wird, mein Proxy hat
andauernd behauptet, daß Stefans Server down ist
ERROR (57). 2 blue screens hatte ich auch noch.