3

この質問は、LZWアルゴリズムに厳密に限定されるものではなく、LZ77およびLZ78の他の実装をカバーする場合があります。

私はLZW辞書コーディングスキームを含む圧縮/解凍ユーティリティを書こうとしています。問題は、エンコード段階で各コードワード（または「コード」）が書き出された後に、区切り文字（スペース）を含める必要があることです。出力がデコーダーに直接ストリーミングされ、後でデコードするために圧縮ファイルに保存される可能性があるとは想定できないため、これを行ってきました（この場合、デコーダーは何が分離するかを検出するための何らかの方法が必要になりますコードワード-区切り文字）。

最近、これは不要であり、デコーダーは、おそらく以前に読み取ったコードに基づいて、毎回読み取る圧縮ファイルの量を動的に「把握」できる必要があると言われました。これにより、各コードの後に​​余分なバイトを挿入する（コストのかかる）必要がなくなると思われます。

デコーダーがこれをどのように理解できるかわかりません。多分それがどのように機能するかを理解している誰かが私にそれを説明することができますか？ありがとう。

編集：

ディクショナリは、「入力文字列」を整数（コード）にマッピングするハッシュテーブルであり、入力データが読み込まれるにつれて通常の方法で構築されます。コードは圧縮ファイルに書き出されます。デコーダーは、圧縮ファイルから各コード（整数）を読み取り、出力する関連文字列を辞書で検索するか、そのコードのエントリがない場合は、通常の方法で文字列がどうあるべきかを判断して更新しますその辞書。

「ファイルがストリーミングまたは保存されている場合、なぜ違いが生じるのですか？」エンコーダーの出力が一度に1つのコードをデコーダーにストリーミングする場合、デコーダーはコードを受信するときに各コードを処理できます。しかし、エンコーダーがすべてのコードをファイル（圧縮ファイル）に書き込み、後でそのファイルがデコーダーに送られる場合、デコーダーは、あるコードがどこから始まり、別のコードがどこから始まるかをどのように知るのでしょうか。ファイルは、数字のマッシュアップされたシーケンスになります。

例：区切り圧縮ファイル：127 32 45 22 228 122 209 ....区切りなし圧縮ファイル：127324522228122209 .. ..

-ロブ

4

2 に答える 2

2

LZW では、辞書は圧縮ファイルに保存されません。ファイルに書き込まれる各値は、その場所に応じて定義済みのビット幅です。たとえば、9 ビットのディクショナリ インデックスのペアとして開始し、その後に 8 ビットのデータが続き、10 ビットのインデックスに切り替えるときにインデックスが使い果たされるまで (これは正確な位置で発生します) 可能性があります。

詳細は、圧縮の実装方法によって異なります。一定の 12 ビット インデックスを使用するものもあります。ただし、余分な区切り文字は必要ありません。

また、データは 8 ビット境界で整列されていないため、データを正しく読み取っていない場合、区切り文字を検出する方法はありません!

編集：

LZW 圧縮アルゴリズムが実際に入力よりも小さいデータを生成することを期待している場合は、いくつかのことを行う必要があります。

まず、ファイルをテキストではなくバイナリとして記述する必要があります。テキストとして書き込むと、ファイルのサイズが縮小するのではなく拡大します。値 127 はバイナリ (01111111) で 1 バイトに格納できますが、区切りスペースを含む 4 バイトの UTF-8 が必要です ("127 " = 00110001 00110010 00110111 00100000)。

第 2 に、LZW は 1 バイトより大きく 2 バイト未満のコード値を処理するように設計されているため、データを正しく出力するにはビット操作を行う必要があります。最初の 256 個の暗黙的に定義されたテーブル エントリをエンコードするには、1 バイトだけで十分です。もう 1 ビット追加すると、さらに 256 エントリを処理できますが、9 ビットのインデックス付きテーブルのエントリはすぐに使い果たされます。12 ビットでは、妥当なテーブル サイズである 4096 のテーブル エントリを取得できます。2 つのフル バイトを使用すると、65 K のエントリを持つかなり大きなテーブルになります。これに関する問題は、テーブル スペースの全容量を使用していない場合、ビットを無駄にしていることです。出力には常に 0 のビットが多数含まれており、これは圧縮率にとって非常に悪いものです。

第 3 に、エンコードされたデータがバイト境界にオーバーラップするため、ストリーミング コーダー/デコーダーは一度に 1 つの値を処理できません。一定の 12 ビット コード サイズが使用される場合、一度に 2 つのコード化された値の倍数を処理できます。ただし、一般に、アルゴリズムは完全なファイルを処理するように設計されています。

于 2011-04-19T18:17:38.510 に答える
1

LZW では、ファイルが読み取られるときにコードブックが生成されるため、区切り文字が不要になります。各 char が LZW 出力に追加されると、8 ビットからより高い値 (通常は 10 または 12 ビット) に変換され、コードブック用のスペースが確保されます。例えば：

banana

LZW では、bはすでにコードブック (参考文献 2) にあるので、 に進みますba。 baコードブックにないので追記。

出力は現在

baであるコードブックで

27 =ba

(1-26 は az のインデックスです)

次に を保持し、 ->aを読み取ります。これもコードブックにないので追加。nan

出力は現在

banであるコードブックで

27 = ba 28 =an

最後まで繰り返す。結果は次のとおりです。

bana29であるコードブックで

27 = ba 28 = an 29 =na

区切り文字を追加する必要はありません。単語bana29がデコードされると、ルックアップが29コードブックに既に存在するためです。

これが、LZW で境界を定める必要がない理由を説明するのに役立つことを願っています

于 2011-04-19T18:25:34.073 に答える