GIF形式 - 個別の可変長コード

Question

GIF形式を解析し、画像データの読み取りに1つの問題を抱えています。このデータは、可変長値を含むビットアレイのように表されます。

元：

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

コードの長さが増加することもありますが、この増加をどのように検出できるか理解できません。初期コードサイズ（最初のコードEx。4の長さ）があります。

Standartは言うだけです：

付録F.可変長コードLZW圧縮。

...

アルゴリズムの変数長コードのアスペクトは、初期コードサイズ（LZWイニシャルコードサイズ）に基づいており、圧縮コードに使用されるビットの初期数を指定します。入力ストリーム内のコンプレッサーによって検出されたパターンの数が、現在のビット数でエンコードできるパターンの数を超えると、LZWコードあたりのビット数が1つ増加します。

...

Answer 1

GIFファイルを解析するとき、画像記述子には、不コード化されていないシンボルのビット幅が含まれます（例：8ビット）。おそらくすでにご存知のように、圧縮データの初期コードサイズは、エンコードされていないシンボルのビット幅（例：9ビット）よりも少し広いです。

また、おそらくご存知のように、GIFファイルの圧縮コード値の可能性は、徐々にサイズが増加し、12ビットが必要な最大0xfff == 4095まで増加します。

減圧装置が圧縮データから引っ張るすべてのコードについて、Decompressorは新しいアイテムをその辞書に追加します。たとえば、Decompressorの最初の2つの9ビットコードが0x028 0x0ffである場合、Decompressorは辞書に2バイトシーケンスを追加します。後で減圧器がコード0x102を読み取った場合、減圧装置は0x102コードを2つの8ビットバイト0x28 0xffにデコードします。

dictionaryに追加される次のアイテムには、コード0x103が割り当てられます。

dictionaryに追加される次のアイテムには、コード0x104が割り当てられます。 ...

最終的に、Decompressorは、コード0x1FFが割り当てられた辞書にアイテムを追加します。これは、9ビットに収まる最大の数字です。そのアイテムを辞書に保存した後、減圧装置は10ビットコードの読み取りを開始します。

dictionaryに追加される次のアイテムには、コード0x200が割り当てられます。

Decompressorにコード幅を増分するように指示するデータシーケンスには、特別な「コマンド」はありません。 Decompressorは、辞書にこれまでに含まれるアイテムの数を追跡する必要があります（多くの場合、次のアイテムを辞書に書く場所のインデックスとして便利に再利用できます）。 Decompressorがアイテム0x1ffを辞書に追加すると、Decompressorが10ビットコードの読み取りを開始する時が来ました。 Decompressorがアイテム0x3ffを辞書に追加すると、Decompressorが11のビットコードを読み始める時が来ました。

• ウィキペディア：グラフィックインターチェンジ形式
• ウィキペディア：可変長コードを備えたLempel – Ziv – Welch

Answer 2

見る この例 まず、標準を見るよりもLZWを理解する方が明確かもしれません。と これ 有用かもしれません。