Giff LZW-Kompression

Question

http://giflib.sourceforge.net/whatsinagif/lzw_image_data.html

Ich lese diese Seite Giff der LZW-Komprimierung zu verstehen. Es zeigt codierten Codes von seiner Probenbild:

# 4 # 1 # 6 # 6 # 2 # 9 # 9 ..

Nach variabler Länge in Bytes komprimiert, es wird:

8C 2D 99

..

was bedeutet:

# 4 - 3 Bits

# 1 - 3 Bits

# 6 - 3 Bits

# 6 - 3 Bits

# 2 - 4 Bits

# 9 - 4 Bits

Diese Daten komprimierte Bild korrekt ist, wie ich die GIFF Probe erzeugten Bild mit Photoshop und verifizierten binären Inhalten.

Es zeigt deutlich die Zunahme Bitgröße passiert, wenn Ausgangscode # 2

Dies ist jedoch, wie die Seite spricht über die Bitgröße Erhöhung: When you are encoding the data, you increase your code size as soon as your write out the code equal to 2^(current code size)-1

Jumping back to our sample image, we see that we have a minimum code size value of 2 which means out first code size will be 3 bits long. Out first three codes, #1 #6 and #6, would be coded as 001 110 and 110. If you see at Step 6 of the encoding, we added a code of #7 to our code table. This is our clue to increase our code size because 7 is equal to 2^3-1 (where 3 is our current code size). Thus, the next code we write out, #2, will use the new code size of 4 and therefore look like 0010.

Aber in seiner Codierung Tabelle, Schritt 6 ist, wo Eintrag Nr. 7 zum LZW-Wörterbuch hinzugefügt wird, aber der für die Ausgabe hinzugefügte Code ist der erste # 6. Gemäß dem Algorithmus sollten die zwei # 6 jeweils 4 Bits sein, aber wie kommt es, dass sie tatsächlich 3 Bits sind?

nach dieser Seite https://www.eecis.udel.edu/~amer/CISC651/lzw.and.gif.explained.html

sagt es die gleiche Sache über Bitgröße If you're encoding, you start with a compression size of (N+1) bits, and, whenever you output the code (2**(compression size)-1), you bump the compression size up one bit

so was falsch ist ??

Answer 1

Schauen Sie sich das Beispiel auf der Seite an, mit der Sie noch einmal verknüpft haben: Das Bild hat nur 4 Farben, d. H. Der LZW-Kompressor beginnt mit 3-Bit-Codes. Das Wörterbuch enthält bisher 6 Einträge: die Literale 0..3, den Clear Code 4 und den EOI Code 5. Die ersten beiden Codes sind der Clear Code 4 und das Literal 1. So beginnen alle GIF LZW Streams. Jetzt beginnt die Komprimierung, weil das Bild mit einer Folge von Einsen beginnt. Nachdem zwei weitere Codes in den Stream geschrieben wurden, sind die 8 Wörterbuch-Slots erschöpft, und die Codegröße wird auf 4 erhöht. Der nächste Code - das Literal 2 - wird als 4-Bit-Zahl geschrieben.

Wie Sie sehen, ist nichts falsch. So funktioniert GIF mit einem 4-Farben-Bild.