Formato GIF - Codici a lunghezza variabile separati

Question

Sto cercando di analizzare il formato GIF e ho un problema con la lettura dei dati dell'immagine. Questi dati rappresentavano un array di bit, contenente valori a lunghezza variabile.

ex:

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

A volte aumenta la durata del codice, ma non riesco a capire come posso rilevarlo in aumento. Ho solo dimensione del codice iniziale (lunghezza del primo codice ex. 4).

Standart dice solo:

APPENDICE F. Compressione LZW a codice variabile.

...

L'aspetto del codice a lunghezza variabile dell'algoritmo si basa su una dimensione del codice iniziale (dimensione del codice iniziale LZW), che specifica il numero iniziale di bit utilizzati per i codici di compressione. Quando il numero di modelli rilevati dal compressore nel flusso di input supera il numero di modelli codificabili con il numero corrente di bit, il numero di bit per codice LZW è aumentato di uno.

...

Answer 1

Quando si analizza un file GIF, il descrittore di immagini include la larghezza dei bit dei simboli non codificati (esempio: 8 bit). Come probabilmente già sai, la dimensione del codice iniziale dei dati compressi è un bit più larga della larghezza del bit dei simboli non codificati (esempio: 9 bit).

Inoltre, come probabilmente già saprai, i possibili valori del codice compresso in un file GIF aumentano gradualmente di dimensioni, fino a un massimo di 0xFFF == 4095 che richiede 12 bit per archiviare.

Per ogni codice che il decompressore estrae dai dati compressi, il decompressore aggiunge un nuovo elemento al suo dizionario. Ad esempio, se i primi due codici a 9 bit le letture del decompressore sono 0x028 0x0FF, il decompressore aggiunge una sequenza di due byte al suo dizionario. Successivamente se il decompressore legge mai il codice 0x102, il decompressore decodifica il codice 0x102 sui due byte a 8 bit 0x28 0xFF.

L'elemento successivo che il decompressore aggiunge al dizionario viene assegnato il codice 0x103.

L'elemento successivo che il decompressore aggiunge al dizionario viene assegnato il codice 0x104. ...

Alla fine il decompressore aggiunge un elemento al dizionario a cui viene assegnato il codice 0x1ff. Questo è il numero più grande che si adatta a 9 bit. Dopo aver memorizzato quell'elemento nel dizionario, il decompressore inizia a leggere i codici a 10 bit.

L'elemento successivo che il decompressore aggiunge al dizionario viene assegnato il codice 0x200.

Non esiste un "comando" speciale nella sequenza dei dati che indica al decompressivo di incrementare la larghezza del codice. Il decompressore deve tenere traccia di quanti elementi contiene finora il dizionario (che spesso può essere riutilizzato comodamente come indice di dove scrivere l'elemento successivo nel dizionario). Quando il decompressore aggiunge l'articolo 0x1ff al dizionario, è tempo che il decompressore inizi a leggere i codici a 10 bit. Quando il decompressore aggiunge l'elemento 0x3ff al dizionario, è tempo che il decompressore inizi a leggere i codici a 11 bit.

• Wikipedia: formato di interscambio grafico
• Wikipedia: Lempel-Ziv-Welch con codici a lunghezza variabile

Answer 2

Guarda a questo esempio Innanzitutto, potrebbe essere più chiaro capire LZW che guardare lo standard. E questo può anche essere utile.