このシナリオに適した圧縮 (解凍) ルーチンは何ですか?
https://stackoverflow.com/questions/1348479
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
次の特性を持つ、バイナリ (16 進数データ) 上の組み込みシステムのような制限されたリソース環境に最適化された FAST 解凍ルーチンが必要です。
- データは 8 ビット (バイト) 指向です (データ バスの幅は 8 ビットです)。
- バイト値は 0 ～ 0xFF の均一な範囲ではなく、各 DataSet にポアソン分布 (釣鐘曲線) があります。
- データセットは事前に修正され (フラッシュに書き込まれるため)、各セットが 1 ～ 2MB を超えることはほとんどありません。
圧縮には必要なだけ時間がかかりますが、組み込みシステム (3Mhz ～ 12Mhz コア、2K バイト RAM) のような制限されたリソース環境で実行されるため、メモリ フットプリントが最小限の最悪のシナリオでは、バイトの解凍には 23μS かかるはずです。 。
良い減圧ルーチンとは何でしょうか?
基本的なランレングス エンコーディングは無駄が多すぎるように思えます。圧縮データにヘッダー セットを追加して、頻繁に繰り返されるパターンを表すために未使用のバイト値を使用すると、驚異的なパフォーマンスが得られることがすぐにわかります。
ほんの数分しか投資しなかった私にとって、この分野を愛する人々によって、もっと優れたアルゴリズムがすでに存在しているはずです。
基本的な RLE とのパフォーマンスを比較できるように、PC 上で試してみる「すぐに使える」サンプルをいくつか用意したいと考えています。
解決
パフォーマンスだけが重要な場合に私が使用する 2 つのソリューション:
- LZO GPLライセンスを持っています。
- リブルズフ BSDライセンスを持っています。
- miniLZO.tar.gz これは
LZO, 、組み込み開発に適した「縮小」バージョンに再パックしただけです。
どちらも 非常に 解凍するときも速いです。それを見つけました LZO よりわずかに小さい圧縮データが作成されます。 liblzf ほとんどの場合。速度については独自のベンチマークを行う必要がありますが、私はそれらは「本質的に同等」であると考えています。どちらもよりも光年速いです zlib, ただし、どちらも (ご想像のとおり) それほど圧縮されません。
LZO, 、 特に miniLZO, 、 そして liblzf どちらも埋め込みターゲットに最適です。
他のヒント
は、各値のpropabilityは、すべてのデータセット上に固定されている、あなたが固定されたコード（コードツリーがデータに埋め込まれていない）とハフマン符号化を作成できることを意味値の予め設定された分布を持っている場合。
データに応じて、私は（ブライアンのリンクを参照）、固定コードやLZ77とハフマン試してみます。
さて、思い浮かぶ主なアルゴリズムは次の 2 つです。 ハフマン そして LZ.
1 つ目は基本的に辞書を作成するだけです。辞書のサイズを十分に制限すれば、かなり高速になるはずですが、あまり優れた圧縮は期待できません。
後者は、出力ファイルの繰り返し部分に後方参照を追加することで機能します。これは、ファイル i/o を使用して後方参照を読み取るか、最近読み取ったデータのチャンクを RAM に保存する必要があることを除けば、実行に必要なメモリはおそらくほとんどありません。
繰り返されるセクションが互いに近接する傾向がある場合は、LZ が最良の選択肢であると思われます。あなたが言及したように、ハフマンは、頻繁に繰り返される要素の辞書を作成することによって機能します。
、私は品質に多くの損失なしに4ビット/サンプルにそれを減らすれる、差分PCMまたはADPCM、または類似のもののいずれかで見てね。
最も基本的な差動PCMの実装では、あなただけの現在のサンプルとアキュムレータとの間に4ビットの符号付きの違いを保存し、アキュムレータにその違いを追加し、次のサンプルに移動します。 [-8,7]の外側の違い、それならば、あなたは値をクランプする必要があり、それが追いつくためにアキュムレータのためにいくつかのサンプルを取ることがあります。復号は非常に速いだけアキュムレータに各値を加算し、次のサンプルとしてアキュムレータの出力、ほとんどメモリを使用しています。
信号が大声で、より高いピッチを取得したときにアキュムレータが速く追いつくのに役立つ基本的なDPCM上小さな改善は、彼らはまだているより大きな非線形範囲に4ビット値を復号するためにルックアップテーブルを使用することで1離れてゼロに近いが、限界に向かってより大きな増分で増加させます。および/または、あなたは、乗算器を切り替えるの値のいずれかを予約することができます。エンコーダにそれを使用する際に決定。これらの改善によって、あなたはより良い品質を達成するか、またはサンプルの代わりに、4あたり3ビットで逃げるます。
あなたのデバイスは、非線形μ-lawまたはA-lawのADCを持っている場合は、8ビットサンプルを11-12ビットと同等の品質を得ることができます。それともあなたはおそらく、あなたのデコーダでそれを自分で行うことができます。 http://en.wikipedia.org/wiki/M-law_algorithmする
あなたが作っているものに応じて、すでにあなたのためのすべてのこれを行うが、安価なチップアウトがあるかもしれません。私はいずれにも見ていない。
あなたは、コマンドラインスイッチと圧縮ソフトウェアツールか、異なるアルゴリズムを試してみることができます圧縮ライブラリのいずれかで異なる圧縮アルゴリズムを試してみてください。 アプリケーションの典型的なデータを使用してください。 次に、あなたのニーズに最適にフィットされているアルゴリズムを知っています。
私は、スタートアップを上のRAMにアプリケーションイメージを解凍ブートローダのための組み込みシステムではzlibを使用していました。ライセンスはGPLノーナンセンス、うまく許容します。これは、単一のmallocの呼び出しを行いませんが、私の場合は私が単に静的ブロックへのポインタを返されたスタブ、および対応する遊離（）スタブでこれを置き換えます。私はサイズが権利を取得するために、そのメモリ割り当ての使用状況を監視することによって、これをしませんでした。お使いのシステムは、動的なメモリ割り当てをサポートできる場合、それははるかに簡単です。
