11

「圧縮配列」/「圧縮ベクトル」クラス (詳細は後述) を作成したいと考えています。これにより、多かれ少なかれ一定時間でランダム データ アクセスが可能になります。

「ほぼ一定の時間」とは、要素のアクセス時間は一定ではありませんが、配列の特定のポイントに近づいても増加し続けるべきではないことを意味します。つまり、コンテナーは、1 つの要素を取得するために、大幅に多くの計算を行うべきではありません (「最後の要素を取得するためにもう一度すべてを解凍する」、「最初の要素を取得するためにほとんど何もしない」など)。おそらく、配列を圧縮データのチャンクに分割することで実現できます。つまり、1 つの要素にアクセスするには、「averageTime」+- 偏差が必要です。最良のアクセス時間と最悪のアクセス時間を平均アクセス時間に比較的近づけたいと言えます。

私のオプションは何ですか (適切なアルゴリズム/既に利用可能なコンテナー - 存在する場合)?

コンテナの詳細:

  1. コンテナーは、同一の要素 (std::vector など) の線形配列として機能します。
  2. コンテナーが初期化されると、データは一定になり、変更されることはありません。コンテナは読み取り専用アクセスを提供する必要があります。
  3. コンテナーは array/std::vector のように動作する必要があります。つまり、値は operator[] を介してアクセスされ、.size() などがあります。
  4. テンプレートクラスとして作れたらいいのに。
  5. データへのアクセスは、多かれ少なかれ一定時間である必要があります。すべての要素に同じアクセス時間は必要ありませんが、最後の要素を取得するためにすべてを解凍する必要はありません。

使用例：
データの二分探索。

データの詳細:
1. データは、大部分が float といくつかの int で構成される構造体です。int よりも float の方が多い。文字列はありません。
2. 配列に同一の要素が多数存在する可能性は低いため、単純にデータのインデックスを作成することはできません。
3. 1 つの要素のサイズが 100 バイト未満です。
4. コンテナーあたりの合計データ サイズは、数キロバイトから数メガバイトです。
5. データはまばらではありません。要素の連続ブロックであり、すべてが割り当てられており、「空のスロット」はありません。

圧縮の目的は、圧縮されていない配列としての表現と比較して、ブロックが使用する RAM の量を減らすことですが、ある程度妥当な読み取りアクセス パフォーマンスを維持し、要素を配列としてランダムにアクセスできるようにすることです。つまり、データは圧縮された形式で内部的に保存され、std::vector または同様のコンテナーであるかのように (読み取り専用で) アクセスできる必要があります。

アイデア/意見?

4

5 に答える 5

11

メモリ使用量を最小限に抑えるために、要素がバニラではなく圧縮された配列が必要だと思います。

圧縮に関しては、データの構造に関する特別な洞察がないため、ある種の標準的なエントロピー エンコーディングで問題ありません。理想的には、アレイ全体で GZIP を実行して処理を完了したいのですが、そうすると O(1) アクセスが失われるため、これは非常に重要です。

解決策は、インデックス テーブルと一緒にハフマン コーディングを使用することです。

ハフマン コーディングは、ストリーム全体での発生頻度に応じて、各入力シンボル (ASCII バイトなど) を可変ビット長の別のシンボルに置き換えることによって機能します。たとえば、この文字Eは非常に頻繁に出現するため、短いビット シーケンスを取得しますが、'W' はめったに出現せず、長いビット シーケンスを取得します。

E -> 0b10
W -> 0b11110

次に、この方法で配列全体を圧縮します。残念ながら、出力シンボルは可変長であるため、以前のようにデータにインデックスを付けることができなくなりました。項目番号 15 は ではなくなりましたstream[15*sizeof(item)]。

さいわい、この問題は、圧縮ストリーム内の各項目の開始位置を格納する追加のインデックス テーブル を使用することで解決できます。indexつまり、アイテム 15 の圧縮データはstream[index[15]];にあります。インデックス テーブルは可変出力長を累積します。

したがって、アイテム 15 を取得するには、単純に でバイトの解凍を開始しますstream[index[15]]。これが機能するのは、ハフマン コーディングが出力に凝った処理を行わず、新しいコード ワードを連結するだけであり、以前のすべての項目をデコードしなくてもストリーム内でデコードを開始できるためです。

もちろん、インデックス テーブルによって多少のオーバーヘッドが追加されます。compressed data + index table粒度を微調整して、よりもさらに小さくしたい場合がありますoriginal data。

于 2010-08-06T14:13:01.977 に答える
4

組み込みシステム用にコーディングしていますか、またはこれらのコンテナを何百または何千も持っていますか? そうでない場合、これは興味深い理論的質問だと思いますが (+1)、解凍を行った結果としての速度低下は自明ではなく、 use a を使用する方がよいと思いますstd::vector。

次に、保存しているデータが十分に冗長であり、その小さなブロックが実際に圧縮可能であると確信していますか? さまざまなサイズ (おそらく 2 の累乗) のブロックを保存して、演習として gzip で実行してみましたか? 解凍アルゴリズムを支援するために必要な余分なデータ (アプローチによって異なります) があると、この種の圧縮コンテナーを実行することによるスペースの利点が減少する可能性があります。

それでも圧縮を行うことが合理的であると判断した場合は、少なくともいくつかの可能性がありますが、事前に作成されたものはありません。個々の要素を圧縮して、圧縮されたデータ チャンクへのポインターを格納できます。その後、インデックスへのアクセスは一定のままで、実際のデータを解凍する必要があるだけです。プロキシ オブジェクトを使用すると、実際のデータ圧縮解除がより簡単かつ透過的に行われる可能性があります (さらにstd::vector、基になるコンテナーとして使用できるようになる場合もあります)。

または、std::dequeデータをすでにチャンクに格納しているため、ここでも同様のアプローチを使用できます。たとえばstd::vector<compressed_data_chunk>、各チャンクが保持する場所は、基になるコンテナーとして一緒に圧縮された 10 個のアイテムとします。その後、必要なチャンクに直接インデックスを付けて解凍し、解凍されたデータからアイテムを返すことができます。必要に応じて、包含オブジェクト ( を保持するvector) は、連続したアクセスでパフォーマンスを向上させるために、最近解凍されたチャンクを 1 つまたは 2 つキャッシュすることもできます (ただし、これはバイナリ検索にはまったく役立ちません)。

于 2010-08-06T14:09:11.627 に答える
3

私はこれについてしばらく考えてきました。理論的な観点から、私は 2 つの可能性を特定しました。

  • このパターンでは繰り返しを減らすことができるため、フライウェイト。
  • シリアライゼーション (圧縮はシリアライゼーションの一種です)

1つ目は純粋にオブジェクト指向であり、一般的にうまく適合すると思います。たとえば、ポインターを台無しにするという欠点はありません。

2 番目の方法は、ここではより適しているように見えますが、一般的にはわずかな欠点があります: ポインターの無効化 + ポインターのエンコード/デコード、仮想テーブルなどに関する問題。インデックスの。

いくつかの「ハフマン コーディング」ソリューションを見てきましたが、これは、構造ごとに圧縮アルゴリズムを提供する必要があることを意味します。一般化するのは簡単ではありません。

だから私は逆に、'zlib' のような圧縮ライブラリを使って、例えば lzo のような高速なアルゴリズムを選びたいと思っています。

  • たとえば1001のように、ノードごとに多数のアイテムを持つB *ツリー（またはバリアント）（移動しないため）。各ノードには、アイテムの配列の圧縮表現が含まれています。インデックスは圧縮されません。
  • おそらく：cache_view最後の5つ（またはそれくらい）の解凍されたノードなどを保存しながらコンテナにアクセスするため。もう 1 つの方法は、参照カウントを実装し、誰かがノード内の項目の 1 つを処理できる限り、データを圧縮しないようにすることです。

いくつかのコメント:

  • ノードごとに多数のアイテム/キーが必要な場合、ほぼ一定のアクセス時間があります。たとえば、1001 の場合、格納するアイテムが 100 万個未満である限り、2 レベルの間接化しかないことを意味します。億など…
  • このような構造を持つ読み取り/書き込み可能なコンテナーを構築できます。ノードの書き込みが完了してからのみ再圧縮するようにします。
于 2010-08-09T11:35:15.650 に答える
0

さて、私の理解では、あなたが望むのはある種のアクセサーテンプレートです。基本的には、ポインタ、blob へのインデックスなどを介して内部的にアクセスする要素タイプの 1 つを引数として持つテンプレート アダプタを作成します。アダプタをポインタのようにします。

const T &operator->(void) const;

参照アダプターよりもポインターアダプターを作成する方が簡単だからです (ただし、それらの 1 つを記述する方法を知りたい場合は vector を参照してください)。ガイドラインに従って、このアクセサーを定数にしたことに注意してください。次に、ブロブがロード/圧縮されたときにオフセットを事前に計算し、テンプレート化されたアダプター クラスをベクターに入力します。これは理にかなっていますか？詳細が必要な場合は、喜んで提供いたします。

圧縮アルゴリズムについては、ブロブ内のバイトの頻度分析を行うだけで、圧縮されていないブロブをハードコーディングされたハフマン エンコーディング (多かれ少なかれ以前に提案されたように) を介して実行し、各要素のオフセットをキャプチャして保存することをお勧めします。それはあなたの配列の要素であるプロキシアダプタにあります。実際、最初からベクターにコピーバック挿入できる要素を圧縮して生成する圧縮クラスの一部にすることができます。繰り返しますが、サンプル コードが必要な場合は返信してください。

于 2010-08-06T13:43:19.790 に答える
0

「ファイルのランダムな読み取り/書き込みを可能にする最適な圧縮アルゴリズムは何ですか?」に対するいくつかの回答はありますか? インメモリデータに適応する必要がありますか?

于 2010-09-13T03:01:29.857 に答える