c - メモリ不足状態での LZW 圧縮/解凍

Question

メモリ不足の状態 (< 2k) で lzw 圧縮/解凍を実装する方法を教えてください。それは可能ですか？

score 4 · Accepted Answer

誰もが使用するzlibライブラリは、他の問題の中でも特に肥大化しています（組み込み用）。私はそれがあなたの場合にはうまくいかないと確信しています。私はもう少しメモリを持っていて、おそらく16Kで、それを収めることができませんでした。それはメモリの大きなチャンクを割り当ててゼロにし、もののコピーなどを保持します。アルゴリズムはおそらくそれを行うことができますが、既存のコードを見つけることは挑戦です。

私はhttp://lzfx.googlecode.comを使用しました。解凍ループは小さく、以前の結果に依存する古いlzタイプの圧縮であるため、非圧縮の結果にアクセスする必要があります...次のバイトは0x5です、次のバイトは0x23、次の15バイトは15 200バイト前のコピー、次の6バイトは127前のコピーです...新しいlzアルゴリズムは可変幅のテーブルベースであり、大きくても大きくてもかまいません。実装方法によって異なります。

私は繰り返しデータを処理し、数Kを数百に絞り込もうとしていました。圧縮率は約50％で、それほど大きくはありませんでしたが、仕事は完了し、解凍ルーチンはごくわずかでした。上記のlzfxパッケージは小さく、zlibとは異なり、数十のファイルではなく、コードがすぐそこにある2つの主要な関数のようです。バッファの深さを変更する可能性があります。必要に応じて、圧縮アルゴリズムを改善することもできます。解凍コード（おそらく20行または30行のコードなど）を変更する必要がありましたが、ポインターが重く、組み込み環境ではポインターが間違った場所にあったため、配列に切り替えました。レジスタとコンパイラの実装方法に応じて、追加のレジスタを書き込むかどうかを指定します。

より良いものを見つけたら、ここに投稿するか、stackoverflowを介して私にpingしてください。他の組み込みソリューションにも非常に興味があります。私はかなり検索しました、そして上記は私が見つけた唯一の有用なものでした、そして私は私のデータがそのアルゴリズムを使って十分に圧縮されるようなものであったことを幸運でした...今のところ。

score 3 · Accepted Answer

私はLZSSを使用しました。奥村晴彦のコードをベースに使用しました。非圧縮データ（2K）の最後の部分を辞書として使用します。圧縮されていないすべてのデータがメモリにある場合は、リンクしたコードを変更して、メモリをほとんど使用しないようにすることができます。少しグーグルすると、さまざまな実装が見つかります。

score 3 · Accepted Answer

メモリ不足の状態 (< 2k) で lzw 圧縮/解凍を実装する方法を教えてください。それは可能ですか？

なぜLZW？LZW には大量のメモリが必要です。これはハッシュ/辞書に基づいており、圧縮率はハッシュ/辞書のサイズに比例します。より多くのメモリ - より良い圧縮。少ないメモリ - 出力は入力よりもさらに大きくなる可能性があります。

私は長い間エンコーディングに触れていませんでしたが、IIRCハフマンコーディングは、メモリ消費に関しては少し優れています。

ただし、それはすべて、圧縮する情報の種類によって異なります。

score 2 · Accepted Answer

圧縮アルゴリズムの選択が明確に設定されていない場合は、代わりにgzip/LZ77を試してみてください。これは、私が一度使用して適応させた非常に単純な実装です。

ftp://quatramaran.ens.fr/pub/madore/misc/myunzip.c

入力の読み取り方法やエラー処理などをクリーンアップする必要がありますが、これは良いスタートです。データとコードを2kに収める必要がある場合も、おそらく大きすぎますが、少なくともデータサイズはすでに小さくなっています。

大きなプラスは、それがパブリックドメインであるため、好きなように使用できることです！

score 1 · Accepted Answer

私が最後に LZW 圧縮アルゴリズムを試してから 15 年以上経っています。

メモリの制約を考えると、これはせいぜい難しいでしょう。構築した辞書は、利用可能なものの大半を消費します。(コード + メモリ <= 2k と仮定します。)

辞書には小さな固定サイズを選択してください。1024 エントリとします。

各辞書エントリを .... の形式にします。

 struct entry {
    intType   prevIdx;
    charType  newChar;
 };

この構造により、辞書は再帰的になります。適切に機能させるには、前のインデックスのアイテムが有効である必要があります。これは実行可能ですか？わからない。しかし、それが私たちをどこに導くのかを考えてみましょう....

int と char に標準型を使用すると、すぐにメモリ不足になります。できるだけきつく詰め込みたいと思うでしょう。1024 エントリを保存するには 10 ビットかかります。あなたの新しいキャラクターは、おそらく8ビットかかります。合計 = 18 ビット。

18 ビット * 1024 エントリ = 18432 ビットまたは 2304 バイト。

一見、これは大きすぎるように見えます。私たちは何をしますか？最初の 256 エントリがすでにわかっているという事実を利用してください。通常の拡張 ASCII セットまたは何を持っているかです。これは、実際には 768 個のエントリが必要であることを意味します。

768 * 18 ビット = 13824 ビットまたは 1728 バイト。

これにより、コード用に約 320 バイトが残ります。当然、辞書のサイズをいじってみて何が良いかを判断することはできますが、コード用のスペースがあまり多くないということにはなりません。コードスペースが非常に少ないため、アセンブリでコーディングすることになると思います。

これが役立つことを願っています。

score 0 · Accepted Answer

BusyBoxのソースを調べて、その LZW 実装があなたの環境で動作するのに十分小さいかどうかを確認することをお勧めします。

score 0 · Accepted Answer

lzw の最下位の辞書はtrie on linked listです。LZW ABの元の実装を参照してください。フォークLZWSで書き直しました。フォークは互換性がありcompressます。詳細なドキュメントはこちら。

nビット辞書が必要(2 ** n) * sizeof(code) + ((2 ** n) - 257) * sizeof(code) + (2 ** n) - 257です。

そう：

9 ビットコード - 1789バイト。
12 ビットコード - 19709バイト。
16 ビットコード - 326909バイト。

辞書の要件ですのでご注意ください。スタック内の状態または変数には、約 100 ～ 150 バイトが必要です。

デコンプレッサは、コンプレッサよりも少ないメモリを使用します。

9 bitしたがって、データをバージョンで圧縮してみることができると思います。しかし、それは良い圧縮率を提供しません。あなたが持っているより多くのビット - 比率はより良いです。

score -2 · Accepted Answer

typedef   unsigned int     UINT;
typedef   unsigned char    BYTE;

BYTE *lzw_encode(BYTE *input ,BYTE *output, long filesize, long &totalsize);
BYTE *lzw_decode(BYTE *input ,BYTE *output, long filesize, long &totalsize);

c - メモリ不足状態での LZW 圧縮/解凍

8 に答える 8

Related

Reference