8

次のタプルのリストを圧縮形式で保存したいのですが、どのアルゴリズムが私に与えるのか疑問に思いました

  • 最小の圧縮サイズ
  • 最速の解凍/圧縮
  • 最適なトレードオフ（トレードオフ曲線の「ひざ」）

私のデータは次のようになります。

(<int>, <int>, <double>), 
(<int>, <int>, <double>), 
...
(<int>, <int>, <double>)

2つのintの1つは特定の時点を指し、1つのリストに含まれる数値が互いに近い可能性が非常に高くなります。もう1つのintは抽象IDを表し、値が完全にランダムになるわけではありませんが、値が近くなる可能性は低くなります。ダブルはセンサーの読み取り値を表しており、値の間にはある程度の相関関係がありますが、おそらくあまり役​​に立ちません。

4

6 に答える 6

4

「時間」の整数は互いに近い可能性があるため、最初の整数のみを保存し、その後は差を前の整数に保存するようにしてください（デルタコーディング）。2 番目の int についても同じことを試すことができます。

あなたが試みることができるもう一つのことは、データを[int1、int2、double]、[int1、int2、double] ...から[int1、int1 ...]、[int2、int2 ...]、[double]に再編成することです、ダブル...]。

結果の圧縮範囲を調べるには、データをファイルに書き込んで、ここから Christian Martelock からコンプレッサー CCM をダウンロードします。このようなデータ収集に非常に適していることがわかりました。非常に高速なコンテキスト混合アルゴリズムを使用します。また、WinZIP などの他の圧縮プログラムと比較したり、zLib などの圧縮ライブラリを使用して、努力する価値があるかどうかを確認したりすることもできます。

于 2008-11-10T09:39:49.973 に答える
2

すでに提案されているように並べ替えてから、保存します

（最初のint）（2番目のint）（doubles）

転置行列。次に圧縮

于 2008-11-10T10:30:46.440 に答える
2

質問を正しく読んでいれば、データを効率的に保存したいだけです。明らかに、圧縮された xml のような単純なオプションは単純ですが、より直接的なバイナリ シリアル化方法があります。思い浮かぶのは、Google のプロトコル バッファです。

たとえば、C# でprotobuf-netを使用すると、データを保持するクラスを簡単に作成できます。

[ProtoContract]
public class Foo {
    [ProtoMember(1)]
    public int Value1 {get;set;}
    [ProtoMember(2)]
    public int Value2 {get;set;}
    [ProtoMember(3)]
    public double Value3 {get;set;}
}

次に、ProtoBuf.Serializer クラスを介して List や Foo[] などを [de]serialize します。

私はそれがあなた自身のものを転がすのと同じくらいスペース効率が良いと主張しているわけではありませんが、かなり近いものになるでしょう. プロトコル バッファの仕様は、スペースをかなり有効に使用します (たとえば、整数に base-128 を使用して、小さい数値がスペースを節約できるようにします)。しかし、すべてのシリアライゼーション コードを自分で書かなくても、簡単に試すことができます。

このアプローチは、実装が簡単であるだけでなく、さまざまな言語用のプロトコル バッファの実装があるため、他のアーキテクチャから簡単に使用できるという利点もあります。また、通常の [解凍] 圧縮 (GZip/DEFLATE/etc) や xml ベースのシリアル化よりもはるかに少ない CPU を使用します。

于 2008-11-10T09:42:25.040 に答える
2

ほとんどの圧縮アルゴリズムは、そのようなデータに対して同様にうまく機能しません。ただし、データを gzip や deflate のようなアルゴリズムに送る前に、データの圧縮率を高めるためにできること (「前処理」) がいくつかあります。次のことを試してください。

まず、可能であれば、タプルを昇順にソートします。最初に抽象 ID を使用し、次にタイムスタンプを使用します。同じセンサーから多くの読み取り値があると仮定すると、同様の ID が近くに配置されます。

次に、測定が定期的に行われる場合は、タイムスタンプを以前のタイムスタンプとの差に置き換えます (もちろん、センサーの最初のタプルは除きます)。たとえば、すべての測定が 5 分間隔で行われる場合、 2 つのタイムスタンプ間の差分は、通常 300 秒近くになります。したがって、タイムスタンプ フィールドは、ほとんどの値が等しいため、はるかに圧縮可能になります。

次に、測定値が時間的に安定していると仮定して、すべての読み取り値を同じセンサーの以前の読み取り値からのデルタに置き換えます。繰り返しますが、ほとんどの値はゼロに近いため、より圧縮可能になります。

また、浮動小数点値は、その内部表現のために、圧縮の候補としては非常に不適切です。それらを整数に変換してみてください。たとえば、温度の読み取り値は、ほとんどの場合、小数点以下 2 桁を超える必要はありません。値に 100 を掛けて、最も近い整数に丸めます。

于 2008-11-10T09:47:37.087 に答える
2

以下は、ほとんどの検索エンジンで使用される一般的なスキームです。値のデルタを格納し、可変バイト エンコーディング スキームを使用してデルタをエンコードします。つまり、デルタが 128 未満の場合、1 バイトだけでエンコードできます。詳細については、Lucene および Protocol バッファーの vint を参照してください。

これにより、最適な圧縮率が得られるわけではありませんが、通常はエンコード/デコードのスループットが最速になります。

于 2008-11-10T09:51:26.940 に答える
0

素晴らしい答えです。記録として、私が支持したものを最終的に使用しているアプローチにマージします。

  1. 同様の数字が隣り合うようにデータを並べ替えて再編成します。つまり、最初にIDで並べ替え、次にタイムスタンプで並べ替え、からからから(<int1>, <int2>, <double>), ...に並べ替えます（ schnaaderとStephan Leclercq([<int1>, <int1> ...], [<int2>, <int2> ... ], [<double>, <double> ...])が提案したよう に）

  2. schnaaderとididakによって提案されているように、タイムスタンプ (およびおそらく他の値) でデルタ エンコーディングを使用します。

  3. プロトコル バッファを使用してシリアル化します (いずれにしてもアプリケーションで使用するので、依存関係などは追加されません)。指摘してくれたMarc Gravellに感謝します。

于 2008-11-10T10:35:35.540 に答える