compression - 少量のデータを圧縮する

Question

私は約80から150ビット程度のビットストリームを生成するプログラムを持っています。これを圧縮したいのは、人々がそれらを送信できるように、それらをある種のASCII文字列に変換するからです。

そのようなストリームで動作する可能性のある、優れた無料のビット対応コンプレッサーを知っている人はいますか？「標準オプション」に関する私の主な問題は、このストリームを実際にはバイトではなくビットとして扱う必要があることです。そうしないと、構造が失われ、オーバーヘッドがゲインを圧倒します。

添加：

これらのストリームを圧縮したい理由は、ユーザーがおそらくbase64エンコーディングのようなものを使用して、それらを切り取って貼り付けるためです。したがって、一部のデータを保存すると便利です。

これは、それを見たい人のための例です。読みやすくするためにフォーマットを追加します。

110 110 - This is a 6x6 grid (the maximum is 7x7, so we only need 3 bits!)

000000
011110
010010
010010
011110
000000 - This is one layout grid

000000
000000
001000
000100
000000
000000 - This is the second layout grid

今、私たちはいくつかの作品をリストします

010 11111111 - A piece is a 3-bit colour code, then an 8-bit list of 'on / off' bits.
001 10101010 - Another bit!
001 10101010 - Another, identical bit!

これを「ビットとして」と見なす必要がある理由は、ビットストリーム（特に「グリッド」の多くの0）として表示すると明らかな圧縮オプションがあり、バイトストリームと見なすと消えてしまうためです。

score 10 · Accepted Answer

150 ビットを圧縮することで何を達成したいと考えていますか? この 19b メッセージのいくつかを集約しない限り、何を得たいのかわかりません。ユーザーに「コード」を送受信させたいUIの問題ですか？

base64エンコーディングはどうですか？これは、バイナリデータを受け取り、簡単に送信または入力できるようにコード化された文字に変換します。

score 4 · Accepted Answer

クリス、それらのサンプルを投稿してくれてありがとう。ランレングスエンコーディングは、あなたが望む方法だと思います。それは実装するのがかなり簡単なはずです。

http://en.wikipedia.org/wiki/Run-length_encoding

これらすべての連続する 0 でうまく機能します。

これらの文字列を圧縮する主な理由は、切り取りと貼り付けを容易にするためですか? 理にかなっています。興味深いプロジェクトのようですね。

弦をより人間が扱いやすいものにしようとしているだけなら、準備は整っているように思えます。それらを圧縮して回線上でより高速に送信しようとしている場合、小さな文字列を圧縮する利点は、MTU サイズなどの他の TCP の問題によって無効になる可能性があると思います。（私はそこでの経験がないので、最後の一口は塩の粒でいっぱいにしてください）

幸運を！

score 3 · Accepted Answer

この種のデータを大幅に圧縮できる汎用アルゴリズムはないと思います。

最善の策は、データの構造を分析して、カスタムの圧縮アルゴリズムを見つけるか、既存のアルゴリズムをカスタマイズすることです（おそらく、事前に入力された辞書などを使用して）。

score 3 · Accepted Answer

私の最初の提案は、 range encodingを調べることです。それ以外の

1: ビットデータからバイナリデータに圧縮してから

2: バイナリデータを base64 ASCII データにエンコードし、

ビットを直接範囲 0 からN(ここでNは、使用している印刷可能な文字数から 1 を引いた数) にパックしてから、非常に簡単なマッピングを行うことができます。

私の 2 番目の提案は、PNG で採用されているフィルター方法を調べて、同様の方法を使用してデータをより圧縮できるようにすることができるかどうかを検討することです。2 つのサンプルレイアウトグリッドだけから判断するのは困難ですが、最初のグリッドからは、「上と左の隣接ピクセルに基づいて各ピクセルを予測し、そのピクセルが一致した場合は各ピクセルを 0 に変換する」などの方法が考えられる可能性が非常に高いようです。予測と、その予測に反する場合は 1」を使用すると、より均一なデータセットが得られるため、圧縮率が高くなります。

score 2 · Accepted Answer

ストリームが非常に小さいので、ここにいくつか投稿できますか?

また、それらのストリームに圧縮を許可するのに十分な冗長性があると確信していますか? データの繰り返しブロックはありますか?

ちょっと遠回りですが、具体的な答えがない場合は、ROM シーンを調べて、「クロノトリガー」や「ファイナルファンタジー III. " これらのゲームではテキスト文字列が圧縮されていたことを私は知っています (当時、バイトは非常に貴重でした)。スキームを解明することは、ハッカーにとって楽しい挑戦でした。たくさんの短い小さな文字列が圧縮されていると言ったとき、それが私の頭に浮かんだ唯一のことです。

ただし、根本的な問題は残る可能性があります。これらの ROM の圧縮スキームは、多くの文字列 (つまり、"Timbuktu" が 58 の異なる文字列で発生した場合) にまたがる冗長性を利用し、単一のストリーム内ではあまり利用しなかったと想像できます。

score 2 · Accepted Answer

zlibの使用を検討することをお勧めします。ダウンロード可能で、ライセンスにより、ほぼすべてのプロジェクトで使用できます。重要な点は、広く使用されているため、適切にデバッグされていることです。データが重要な場合は、今後ランダムな日付で hombrew アルゴリズムの奇妙なエッジケースをデバッグする必要はありません。

少しいじりましたが、ストリーム指向の圧縮が可能です。ただし、一度に少量のデータを供給するだけの場合、それがどれほど優れているかはわかりません。損失のない圧縮は、パターンを見つけて排除することで機能する傾向があり、一度に 12 バイトのような小さなものをフィードする場合、見つけるパターンは多くありません。

私は Juan の回答に賛成しているわけではありません。あなたは多くの情報を提供しませんでしたが、実際にデータを失う圧縮形式は必要ないと思います。最も一般的なグラフィック、オーディオ、およびビデオの圧縮アルゴリズムは非可逆です。それらは、元の情報の一部が削除またはわずかに変更された画像または音声を適切に取り込む人間の感覚の能力に依存しています。

score 1 · Accepted Answer

JBIG はあなたが必要とするものを提供するかもしれません。

http://en.wikipedia.org/wiki/JBIG

http://www.jpeg.org/jbig/index.html

http://www.cl.cam.ac.uk/~mgk25/jbigkit/

JBIG は、1 bpp のファックスイメージを圧縮するために使用されます。

score 1 · Accepted Answer

G3 および G4 TIFF の圧縮に使用されるCCITT のGroup 3 および Group 4ロスレスエンコーディングスキームは、バイナリデータを念頭に置いて設計されました。G4 TIFF は、通常 OCR とファックスに使用される白黒の画像です。頭に浮かぶ別の単純なスキームはRLEです。

score 0 · Accepted Answer

zlib 圧縮 (おそらく gzip と同じアルゴリズム) は無料です。いくつかの設定がありますが、ビットに周期的なパターンがない限り、どれだけ節約できるかわかりません.

png および gif グラフィックファイルは基本的にビットパターンの表現であるため、これらが使用する圧縮アルゴリズムを見つけることができます。

score 0 · Accepted Answer

必要なのは、可逆バイナリ圧縮です。他にたくさんのリソースがなくても、論文やウェブ記事があると確信しています。それらの用語をグーグルで検索すると、必要なものが得られると思います。

どのくらいのデータについて話しているのですか？パイプが小さいか、スループットが高すぎて圧縮する必要がありますか?

振り返ってみると、データは非常に小さいため、トラフィックを分析し、基本的に既知のビットパターンのマッピング/ハッシュである独自の「圧縮」を行わない限り、おそらく価値のある利益を得ることはできません。

他の誰かが言ったように、いくつかのサンプルデータを投稿してください。その後、おそらくより良いアドバイスがあります。

score 0 · Accepted Answer

私はティムと同じ考えを持っていました.そのような少量のデータはほとんど圧縮する価値がないようです. 実際のところ、あなたが本当に調べたいのは、uuencode や mime-encode (別名 " Base64 ") のような何らかの ASCII エンコーディング方法であることをお勧めします。

score 0 · Accepted Answer

すでに述べたことに加えて、「少量のデータを圧縮する」ことは本質的に少し無意味ではありませんか? データ、プラットフォーム、または役立つ可能性のある用途について詳しく説明できれば.

ビットと ascii については、何を目指しているのか完全にはわかりませんが、Michael が述べたように、Base64 は任意のバイナリをより使いやすくする方法を提供します。

バイナリから ascii への変換は、圧縮の反対であることに注意してください。

compression - 少量のデータを圧縮する

12 に答える 12

Related

Reference