32 ビット整数のリストと、マルチセット (メンバーの重複を許可するセット) に 32 ビット整数の同じコレクションがあるとします。
Sets は順序を保持しませんが、List は保持するので、リストよりも少ないビット数で Multiset をエンコードできるということですか?
もしそうなら、マルチセットをどのようにエンコードしますか?
これが本当なら、順序を保存する必要のない他の例はビットを保存しますか?
例として 32 ビット整数を使用したことに注意してください。エンコーディングでデータ型は重要ですか? 節約するために、データ型は固定長で比較可能である必要がありますか?
編集
重複が少ないコレクションと重複が多いコレクションでは、どのソリューションもうまく機能するはずです。単純に重複をカウントするだけでマルチセットをエンコードする高重複の明らかな方法は非常に簡単ですが、コレクションに重複がない場合、これはより多くのスペースを必要とします。
マルチセットでは、各エントリは数値のペアになります。整数値と、セット内で使用された回数です。これは、マルチセット内の各値をさらに繰り返しても、保存にコストがかからないことを意味します (カウンターをインクリメントするだけです)。
ただし、(両方の値が int であると仮定すると) これは、各リスト項目が平均で 2 回以上繰り返される場合にのみ、単純なリストよりも効率的なストレージになります。 、格納されている数字の繰り返し。(たとえば、任意の値の繰り返しが 255 回を超えないことがわかっている場合は、int ではなくバイトを使用してカウンターを格納できます)
このアプローチは、各データ項目の繰り返し回数のカウントを保存するだけなので、あらゆるタイプのデータで機能します。各データ項目は比較可能である必要があります (ただし、2 つの項目が同じか異なるかがわかる点まで)。各アイテムが同じ量のストレージを使用する必要はありません。
データ圧縮はかなり複雑な問題であり、圧縮に使用するのが難しいデータには冗長性があります。
一部のデータセットを縮小する非可逆スキーム（入力データを復元できるスキーム）では、他のデータセットを拡大する必要があるため、基本的にアドホックです。繰り返しの多い整数のコレクションは、マルチマップで非常にうまく機能しますが、繰り返しがない場合は、繰り返し回数1で多くのスペースを使用しています。これは、さまざまなファイルで圧縮ユーティリティを実行することでテストできます。テキストファイルには多くの冗長性があり、通常は多くの圧縮が可能です。乱数のファイルは、圧縮すると大きくなる傾向があります。
注文情報を失うことに悪用可能な利点があることを私は知りません。それは、主に重複が多いかどうかにかかわらず、実際の数が何であるかによって異なります。
原則として、これは値をソートし、最初のエントリと後続のエントリ間の順序付けられた差異を格納することと同じです。
言い換えると、まばらに存在するセットの場合、ほとんど節約できませんが、より密集したセット、またはクラスター化されたエントリを持つセットの場合、より大幅な圧縮が可能です (つまり、エントリごとに保存する必要があるビットが少なくなり、場合によっては 1 未満になります)。重複が多い場合）。つまり、圧縮は可能ですが、レベルは実際のデータによって異なります。
並べ替え操作に続いてリスト デルタを実行すると、圧縮しやすいシリアル化された形式になります。
EG [ 2 12 3 9 4 4 0 11 ] -> [ 0 2 3 4 4 9 11 12 ] -> [ 0 2 1 1 0 5 2 1 ] は約半分の重さです。
マルチセットに重複がある場合は、単純なリストよりも小さいサイズに圧縮できます。重複を効率的に保存するために使用できるRun-length encodingをご覧になることをお勧めします(非常に単純なアルゴリズム)。
それがあなたの意図したことであることを願っています...