Formato GIF: códigos separados de longitud variable

Question

Intento analizar el formato GIF y tengo un problema con la lectura de datos de imagen. Estos datos representados como matriz de bits, que contienen valores de longitud variable.

ex:

0010-1010-0010-0000-00111-10000-11111...

A veces, la longitud del código aumenta, pero no puedo entender cómo puedo detectar este aumento. Solo tengo el tamaño del código inicial (longitud del primer código Ex. 4).

Standart solo dice:

Apéndice F. Compresión LZW de código de longitud variable.

...

El aspecto de código de longitud variable del algoritmo se basa en un tamaño de código inicial (tamaño de código inicial LZW), que especifica el número inicial de bits utilizados para los códigos de compresión. Cuando el número de patrones detectados por el compresor en el flujo de entrada excede el número de patrones codificables con el número actual de bits, el número de bits por código LZW aumenta en uno.

...

Answer 1

Al analizar un archivo GIF, el descriptor de imagen incluye el ancho de bit de los símbolos no codificados (ejemplo: 8 bits). Como probablemente ya sepa, el tamaño del código inicial de los datos comprimidos es un poco más ancho que el ancho de bit de los símbolos no codificados (Ejemplo: 9 bits).

Además, como probablemente ya sepa, los posibles valores de código comprimido en un archivo GIF aumentan gradualmente de tamaño, hasta un máximo de 0xFFF == 4095 que requiere 12 bits para almacenar.

Para cada código que el descompresor extrae de los datos comprimidos, el descompresor agrega un nuevo elemento a su diccionario. Por ejemplo, si los dos primeros códigos de 9 bits, el descompresor se lee es 0x028 0x0ff, el descompresor agrega una secuencia de dos bytes a su diccionario. Más tarde, si el descompresor lee el código 0x102, el descompresor decodifica ese código 0x102 a los dos bytes de 8 bits 0x28 0xff.

Al siguiente elemento al descompresor agrega al diccionario se le asigna el código 0x103.

Al siguiente elemento al descompresor agrega al diccionario se le asigna el código 0x104. ...

Finalmente, el descompresor agrega un elemento al diccionario al que se le asigna el código 0x1ff. Ese es el número más grande que se ajusta a 9 bits. Después de almacenar ese elemento en el diccionario, el descompresor comienza a leer códigos de 10 bits.

Al siguiente elemento al descompresor agrega al diccionario se le asigna el código 0x200.

No hay ningún "comando" especial en la secuencia de datos que le indique al descompresor que incrementa el ancho del código. El descompresor debe realizar un seguimiento de cuántos elementos contiene el diccionario hasta ahora (que a menudo puede reutilizarse convenientemente como el índice de dónde escribir el siguiente elemento en el diccionario). Cuando el descompresor agrega el elemento 0x1ff al diccionario, es hora de que el descompresor comience a leer códigos de 10 bits. Cuando el descompresor agrega el elemento 0x3ff al diccionario, es hora de que el descompresor comience a leer los códigos de 11 bits.

• Wikipedia: formato de intercambio gráfico
• Wikipedia: Lempel-Ziv-Welch con códigos de longitud variable

Answer 2

Mirar este ejemplo Primero, puede ser más claro entender LZW que mirar el estándar. Y este También puede ser útil.