問題タブ [lzw]

GIF87a ラスター データ ストリームからデータ バイトをデコードしようとしています。LZW 可変長コードの読み取り方法 (および LSB... 最下位バイトが最初にこれに収まる方法) がわかりません。ラスター データ ストリームは次のように始まります (16 進数)。

• 06 -> コードサイズ 6
• 6b -> 107 のブロック バイト数
• 40 -> クリア コー​​ド (2^6)、10 進数で 64、16 進数で 40
• 86 -> 実際のデータの開始

GIF87a 仕様: http://www.w3.org/Graphics/GIF/spec-gif87.txt

ラスター ストリームには、グローバル マップ (または LZW ツリーの親) を指すインデックスが必要ですが、それを読み取る方法がわかりません。

例として、誰かが最初の数バイト (86 から始まる) を変換できますか?

事前にお詫び申し上げますが、これは実際にはフォトショップの質問ではありません。むしろ、私は説得力のあるものを考え出そうとしていますが、アニメーション用に可能な限り最小のファイルを生成するために、gif形式の圧縮と機能を可能な限り活用しています。

いくつかの制約：

• 少なくとも20または30フレームである必要があります。私はもっ​​と少ないもので試しました（そしてそれらはほとんど圧縮できないので、15フレームは一般的に言えば30の半分のサイズです）
• サイズは約256x192以上である必要があります
• ただし、カラーである必要はなく、フルグレースケールである必要もありません。わずか16枚のグレーで説得力のある静止画を見てきました
• パターンを持つことはできますが、人間の目にすぐにわかるパターンはありません。誰かが1つのフレームを取り、1〜2分後にパターンを見つけることができれば（これにより圧縮可能になりますか？）、問題ありません。
• フレーム2からnはかなりのアルファを使用できますが、アルファの大きな横縞を使い始めたとき、それはすぐに目に見えました。したがって、簡単なチートでRLEの束を積み上げることはできません。
• 上記のすべてで、30〜33msのフレーム速度で見栄えがする必要があります。可変速度はなく、それよりも大幅に速いものに依存することもありません。

上記の制約に準拠するapngも使用できます。あなたがそれを思い付くことができれば、おそらくmpegでさえあります（私はDCTがその魔法をどのように行うかについては知らない）。

理想的には250kバイトの範囲で何かを下げることができますが、先週調理した9メガの怪物よりもかなり小さいもので解決します。

ああ、最後にもう1つ、グラフィックを提供してくれる人はいないことは明らかです。最終的に自分でそこにたどり着くためのトリックを探しています。

重複の可能性:
php を使用して .Z ファイルを解凍する方法はありますか?

Windows 環境で Unix .Z ファイルを解凍する PHP の関数について、手がかりや提案を探しています。

データが繰り返されるバイナリ データにロスレス アルゴリズムを適用した場合、次のシナリオのどれが最高の比率を達成するのだろうかと考えていました。

圧縮率がパターンに依存すると仮定するのは正しいですか?

1. サイズ
2. 繰り返される回数

たとえば、バイナリ データ:

10 10 10 10 10 10 10 10 パターン（10）サイズ 2、パターン（10）繰り返し 8

1001 1001 1001 1001 パターン (1001) サイズ 4、パターン (1001) 繰り返し 4

0000000 11111111 パターン (0) サイズ 1、パターン (0) 繰り返し 8; パターン (1) サイズ 1、パターン (1) 繰り返し 8。または 0000000 11111111 パターン (0000000) サイズ 8、パターン (0000000) 繰り返し 8; パターン (11111111) サイズ 8、パターン (11111111) 繰り返し 1。

上記のうち、圧縮率が最も高いものと最も低いものはどれですか?

前もって感謝します。

演習としてSDL_Surfacesをさまざまな形式にエクスポートするCライブラリを作成していますが、これまでのところ、BMP、TGA、およびPCX形式を使用していません。現在、私はGIF形式に取り組んでおり、それを機能させることに非常に近いと感じています。私の実装はこれの修正版です。

私の現在の問題は、GIFLZW圧縮画像データサブブロックの書き込みです。最初のサブブロックの位置208まで、すべてがスムーズに進みます。元のファイルの3バイトは（位置207から開始）：16進数の「B829 B2」であり、私のものは「B841B2」です。その後、バイトは再び「同期」します。圧縮されたストリームのさらに下流では、おそらく最初のエラーが原因で、同様の違いを見つけることができます。私のファイルも元のファイルよりも短いです。

0は有効なエントリであるため、lzw_entry構造体のタイプをuint16_tからintに変更して、-1を「空の」エントリとして許可することに注意してください。ただし、圧縮されたストリームには実際には違いはありませんでした。元の実装では、代わりに初期化されていないデータを使用して空のエントリをマークします。

辞書の値を誤って読み取っていると思います。そのため、位置208に予想よりも別のコードが表示されます。そうでなければ、私のビットパッキングは正しくありません。

圧縮コードの簡略版を追加しました。何が問題なのでしょう？また、「辞書」データ構造を改善する方法、またはビットストリーム書き込みを高速化する方法を教えてください。

最後に、私はあちこちでいくつかのコードを最適化できることも知っています:)

更新：私はさらにいくつかのテストを行い、AkiSuihkonenが提案したビットパッキングアルゴリズムを実装しました。目立った違いはありませんでした。これは、lzw_table構造体でコードを誤って検索/保存していることと、エラーがメインループにあることを示しています。

LZWデコンプレッサをphpにあるJSendからjavascriptに変換しようとしていますが、理解できない関数に到達しました。

これは私がこれまでにjavascriptで持っているものですが、これをjavascriptで実行すると、sWord定義されていないという文句が表示され、php関数を見ると、これがエラーを生成しない方法がわかりませんか？

これが私がこれまでにjavscriptに持っているものです：

私は、既存の用語と重複しないことを期待して、自分自身を転がす用語ループを思いついた。基本的に、私は印刷されたテキストのループを見つけるためのアルゴリズムを考え出そうとしています。

単純なものから複雑なものまでのいくつかの例

例1

与えられた：

私は言いたい：

またはアルゴリズム的に：

例2

与えられた：

私は言いたい：

またはアルゴリズム的に：

例3

与えられた：

私は言いたい：

またはアルゴリズム的に：

それは私が知っているアルゴリズムを思い出させませんでした。問題のいくつかはあいまいになる可能性があるように感じますが、今のところ、解決策の1つを見つけるだけで十分です。効率はいつでも歓迎ですが、必須ではありません。これどうやってするの？

編集

まず第一に、すべての議論に感謝します。ロゼッタのLZWアルゴリズムを採用し、入力で実行しました。

それは私に与えました：

私が持っている辞書：

圧縮には適しているように見えますが、私が望んでいたものではありません。私が必要としているのは、私の例からのアルゴリズム表現の圧縮のようなものです。

• 後続のシーケンス（シーケンスが繰り返されている場合、間に他のシーケンスはありません）
• 辞書はなく、ループのみ
• 還元不可能
• 最大シーケンスサイズ（アルゴリズム表現を最小化する）
• ネストされたループが許可されているとしましょう（コメントで前に言ったこととは反対に）

GIF LZW 解凍に関する多数の記事を読んだことがありますが、それがどのように機能するか、またはコーディングの観点から、より厄介なコーディングのビットをどのように解決するかについて、いまだに混乱しています。

私が理解しているように、LZW 圧縮データの GIF のバイト ストリームに到達すると、ストリームは次のように伝えます。

最小コードサイズ、別名最初のバイトが始まるビット数。

さて、私が理解しているように、これにクリア コー​​ド用に 1 つ追加するか、クリア コー​​ドと EOI コード用に 2 つ追加する必要があります。しかし、私はそれがどれであるかについて混乱していますか？

つまり、3 つのカラー コード (01、10、11) があるとします。EOI コードを (00 として) 仮定すると、最小コード サイズ (2) に続くバイトは 2 ビットになるか、クリアを考慮して 3 ビットになります。コード？それとも、クリア コー​​ドと EOI コードの両方が既に最小サイズに組み込まれていますか?

2 番目の質問は、動的にサイズ変更されたビットをファイルから読み取る最も簡単な方法は何ですか? 偶数バイト (8) から奇数ビット (3 ビット、12 ビットなど) を読み取るのは、厄介でバグが多いように聞こえるからです。

tar.Zファイルのファイルレイアウトを理解しようとしています。（いわゆる.tazファイル。圧縮tarファイル）。

このファイルは、tar -Zオプションを使用するか、unix compressユーティリティを使用して作成できます（結果は同じです）

このファイル構造に関するドキュメントをグーグルで検索しようとしましたが、このファイル構造に関するドキュメントがありません。

これがLZW圧縮ファイルであり、マジックナンバー「1F9D」で始まることは知っていますが、私が理解できるのはそれだけです。誰かがファイルヘッダーか何かについてもっと詳しく教えてください。

このファイルを解凍する方法や、このファイルを処理できるLinuxコマンドについては興味がありません。

知りたいのは内部ファイルの構造/ヘッダー/フォーマット/レイアウトです。前もって感謝します

私はここから次のCコードを持っています:

http://marknelson.us/1989/10/01/lzw-data-compression/

XOR ハッシュ アルゴリズムを使用して、部分文字列配列要素を検索する必要がなくなり、代わりに部分文字列の「アドレス」を生成すると述べています。

次に、以下の行が主要部分であると思われるハッシュ関数があります。

• ここでは、(定数の定義に従って) 4 ビットから左にシフトされた整数値があります。

• 次に、この値に別の整数値を適用した XOR を取得します。

シフト部分は未使用のビットを取り除くだけであり、12 ビットから 16 ビットの非常に短い部分文字列に単一の単純な XOR 演算が適用されていることは確かです。私はこれについて非常に間違っているかもしれませんが。

この特定の XOR ハッシュ アルゴリズムを説明する名前またはアルゴリズム名の可能なリスト、または可能であれば、この部分文字列アプリケーションに適したアルゴリズム名のリスト (部分文字列の LZW 辞書など) は?

……

……

……