13

最小から最大の順に並べ替えられたランダムな整数の大きなシーケンスがあります。数値は 1 ビットから始まり、45 ビット近くで終わります。リストの先頭には、4、20、23、40、66 という非常に近い数字があります。しかし、数字が大きくなり始めると、それらの間の距離も少し高くなります (実際には、それらの間の距離は偶然です)。 ）。重複した番号はありません。

スペースを節約するためにビットパッキングを使用しています。それにもかかわらず、このファイルは非常に大きくなる可能性があります。

この状況で使用できる圧縮アルゴリズムの種類、またはできるだけ多くのスペースを節約するための他の手法を知りたいです。

ありがとうございました。

4

6 に答える 6

10

データの実際の分布がわかっている場合は、最適に圧縮できます。各整数の確率分布を提供できる場合は、算術符号化または他のエントロピー符号化手法を使用して、理論上の最小サイズに圧縮できます。

秘訣は正確に予測することです。

まず、統計ステートメントを作成できるため、数値間の距離を圧縮する必要があります。数値を直接圧縮する場合、それらは1回しか発生しないため、モデル化するのに苦労します。

次に、次の距離を予測するための非常に単純なモデルの構築を試みることができます。以前に見たすべての距離のヒストグラムを保持し、頻度から確率を計算します。

おそらく欠落している値を考慮する必要がありますが（表現できないため、明らかに0の確率を割り当てることはできません）、次の距離をビットごとにエンコードして各ビットを個別に予測するなど、ヒューリスティックを使用できます。上位ビットはほとんどの場合0であり、エントロピーエンコーディングによって最適化されるため、上位ビットにはほとんど何も支払う必要がありません。

分布を知っていれば、これはすべてはるかに簡単です。例：距離の理論的分布を知っているすべての素数のリストを圧縮しているのは、そのための公式があるからです。だからあなたはすでに完璧なモデルを持っています。

于 2012-09-30T20:09:17.650 に答える
9

既知の範囲でソートされた整数に使用できる、非常に単純でかなり効果的な圧縮手法があります。ほとんどの圧縮スキームと同様に、シリアル アクセス用に最適化されていますが、必要に応じてインデックスを作成してランダム アクセスを高速化できます。

これはデルタ エンコーディングの一種であり (つまり、各数値は前の数値からの距離で表されます)、次のいずれかのコードのベクトルで構成されます。

  • 次のコードでデルタに追加される2 kのデルタを表す単一の 1 ビット、または

  • 0 ビットの後に k ビットのデルタが続き、次の数値が前の数値から指定されたデルタであることを示します。

たとえば、k が 4 の場合、シーケンスは次のようになります。

00011 1 1 00000 1 00001

3 つの数字をコードします。最初の 4 ビット エンコーディング (3) は最初のデルタであり、初期値 0 から取得されるため、最初の数は 3 です。次の 2 つの孤立した 1 は 2·2 4または 32 のデルタに累積され、これが加算されます。次の 0000 のデルタまで、合計で 32 です。したがって、2 番目の数値は 3+32=35 です。最後に、最後のデルタは単一の 2 4プラス 1、合計 17 であり、3 番目の数値は 35+17=52 です。

1 ビットは、次のデルタを 2 kだけインクリメントする必要があることを示します(または、より一般的には、各デルタは、直前の 1 ビットの数の2 k倍だけインクリメントされます)。

これを考えるもう 1 つの、おそらくより良い方法は、各デルタが可変長ビット シーケンスとしてコード化されることです。1 i 0(1|0) kは、i・2 k + [k ビット サフィックス] のデルタを表します。しかし、最初のプレゼンテーションは、最適性の証明とよりよく一致しています。

各「1」コードは 2 kの増分を表すため、m/2 kを超えるコードは存在できません。ここで、m は圧縮されるセット内の最大数です。残りのコードはすべて数字に対応し、合計の長さは n・(k + 1) です。ここで、n はセットのサイズです。k の最適値はおおよそ log 2 m/n で、この場合は 7 または 8 になります。

最適化について心配することなく、アルゴリズムの概念の簡単な証明を行いました。それでもかなり高速です。ランダム サンプルの並べ替えは、圧縮/解凍よりもはるかに時間がかかります。[0, 4,000,000,000) の値の範囲で 16,400,000 から 31,000,000 までのいくつかの異なるシードとベクトル サイズで試してみました。データ値ごとに使用されるビットは、8.59 (n=31000000) から 9.45 (n=16400000) の範囲でした。すべてのテストは、7 ビットのサフィックスを使用して行われました。log 2 m/n は 7.01 (n=31000000) から 7.93 (n=16400000) まで変化します。6 ビットと 8 ビットのサフィックスを試しました。n=31000000 の場合を除き、6 ビットのサフィックスがわずかに小さく、7 ビットのサフィックスが常に最適でした。したがって、最適な k は正確に floor(log 2 m/n)ではないと思いますが、それほど離れていません。

圧縮コード:

void Compress(std::ostream& os,
              const std::vector<unsigned long>& v,
              unsigned long k = 0) {
  BitOut out(os);
  out.put(v.size(), 64);
  if (v.size()) {
    unsigned long twok;
    if (k == 0) {
      unsigned long ratio = v.back() / v.size();
      for (twok = 1; twok <= ratio / 2; ++k, twok *= 2) { }
    } else {
      twok = 1 << k;
    }
    out.put(k, 32);

    unsigned long prev = 0;
    for (unsigned long val : v) {
      while (val - prev >= twok) { out.put(1); prev += twok; }
      out.put(0);
      out.put(val - prev, k);
      prev = val;
    }
  }
  out.flush(1);
}

減圧：

std::vector<unsigned long> Decompress(std::istream& is) {
  BitIn in(is);
  unsigned long size = in.get(64);
  if (size) {
    unsigned long k = in.get(32);
    unsigned long twok = 1 << k;

    std::vector<unsigned long> v;
    v.reserve(size);
    unsigned long prev = 0;
    for (; size; --size) {
      while (in.get()) prev += twok;
      prev += in.get(k);
      v.push_back(prev);
    }
  }
  return v;
}

可変長エンコーディングを使用するのは少し厄介です。別の方法は、各コードの最初のビット (1 または 0) をビット ベクトルに格納し、k ビットのサフィックスを別のベクトルに格納することです。これは、k が 8 の場合に特に便利です。

わずかに長いファイルになりますが、インデックスを作成するのが少し簡単なバリアントは、1 ビットのみをデルタとして使用することです。その場合、デルタは常に、いくつかの a に対して a・2 kであり、場合によっては 0 です。ここで、a はサフィックス コードに先行する連続する 1 ビットの数です。インデックスは、ビット ベクトルの N番目ごとの1 ビットの位置と、対応するサフィックス ベクトルのインデックス (つまり、ビット ベクトルの次の 0 に対応するサフィックスのインデックス) で構成されます。

于 2012-09-30T20:35:35.813 に答える
5

過去に私にとってうまくいったオプションの 1 つは、64 ビット整数のリストを 8 ビット値の 8 つの異なるリストとして保存することでした。数値の上位 8 ビットを格納し、次に次の 8 ビットを格納します。たとえば、次の 32 ビット数値があるとします。

0x12345678
0x12349785
0x13111111
0x13444444

格納されるデータは次のようになります (16 進数):

12,12,13,13
34,34,11,44
56,97,11,44
78,85,11,44

次に、それをデフレート コンプレッサーに通しました。

これで達成できた圧縮率は覚えていませんが、数値自体を圧縮するよりもはるかに優れていました。

于 2012-09-30T22:04:17.600 に答える
5

最も簡単な解決策で別の回答を追加したい：

  1. 前に説明したように、数値をデルタに変換します
  2. 7-zip LZMA2 アルゴリズムを実行します。マルチコアにも対応

距離は単純な分布を持つため、これはあなたの場合にほぼ完璧な結果をもたらすと思います。7-zipで受け取り可能です。

于 2012-09-30T22:09:42.133 に答える
3

あなたのシーケンスが典型的なデジタルコンピュータによって生成されるような疑似乱数で構成されている場合、表現を簡潔にするために、ジェネレーターなどのコードを保存するだけの圧縮スキームが勝るとは思いません初期状態を定義するために必要なパラメーター。

シーケンスが非決定論的な方法で生成された真の乱数で構成されている場合、既に投稿されている他の回答はさまざまな適切なアドバイスを提供します。

于 2012-10-01T06:10:41.607 に答える