小さな範囲に n 個の整数のシーケンスがあり[0,k)、すべての整数の頻度は同じfです (したがって、シーケンスのサイズは ですn=f∗k)。私が今やろうとしているのは、ランダムアクセスを提供しながらこのシーケンスを圧縮することです(i 番目の整数は何ですか)。ランダム アクセスを達成する時間は O(1) である必要はありません。私は、より高いランダム アクセス時間を犠牲にして高圧縮を実現することに関心があります。
ハフマンコーディングは周波数に基づいてコードを割り当てるため、試したことはありません（私の周波数はすべて同じです）。おそらく、この特定のケースの単純なエンコーディングが欠けているのでしょう。
ヘルプやポインタをいただければ幸いです。
前もって感謝します。
PS: cs.stackexchange で既に質問されていますが、ここでもより良いカバレッジを求めています。申し訳ありません。
すべての整数の頻度が同じである場合、最適な圧縮の公正な近似ceil(log2(k))値は整数あたりのビット数になります。これらのビット配列に一定時間でアクセスできます。
kが非常に小さい場合(3 のように)、上記の方法はかなりの量のスペースを浪費する可能性があります。ただし、固定数の小さい整数を基数に結合することで、kより効率的に固定数のビットに収まるようにすることができます (結果を標準サイズのワードにうまく収めることもできます)。いずれにせよ、一定時間でこのコーディングにアクセスすることもできます。
整数の周波数が同じでない場合、最適な圧縮によって入力のさまざまな部分から可変ビット レートが生成される可能性があるため、単純な配列アクセスは機能しません。その場合、良好なランダム アクセス パフォーマンスにはインデックス構造が必要です。圧縮データを便利なサイズのチャンクに分割し、それぞれを順次解凍できますが、この時間はチャンク サイズによって制限されます。
各数値の頻度がまったく同じである場合、これを利用してスペースを節約できる可能性がありますが、それだけでは十分ではない可能性があります。
n範囲内の乱数のエントロピーは[0,k)ですn log2(k)。これはlog2(k)数値あたりのビット数です。これは、正確な周波数を利用せずに数値をエンコードするのに必要なビット数です。
各要素のfコピーの区別可能な順列のエントロピー(ここで) は次のとおりです。kn=f*k
log2( n!/(f!)^k ) = log2(n!) - k * log2(f!)
スターリングの近似 (ここではnとfが大きい場合にのみ有効) を適用すると、次の結果が得られます。
~ n log2(n) - n log2(e) - k ( f log2(f) - f log2(e) )
= n log2(n) - n log2(e) - n log2(f) + n log2(e)
= n ( log2(n) - log2(f) )
= n log2(n/f)
= n log2(k)
これが意味することは、nが大きくkが小さい場合、入力の正確な周波数を利用しても大きなスペースを獲得できないということです。
上記のスターリング近似からの総誤差はO(log2(n) + k log2(f))で、これはO(log2(n)/n + log2(f)/f)エンコードされた数値ごとです。これは、 your が小さすぎkて yourfが小さい場合 (つまり、それぞれの個別の数値のコピー数が少ない場合)、巧妙なエンコーディングでスペースを節約できる可能性があることを意味します。ただし、質問kは、それが実際には小さいことを示しています。
可能なさまざまな組み合わせの数を計算し、その対数を底 2 にすると、可能な限り最良の圧縮を見つけることができますが、あなたの場合はそれほど素晴らしいとは思いません。周波数 1 の 16 の番号で、可能なメッセージの数は 16 です! そして、Excel は 16 の 2 を底とする対数を教えてくれます! 44.25 ですが、4 ビット コードとして格納すると 64 ビットしか必要ありません。(必要な種類が複数ある場合http://mathworld.wolfram.com/MultinomialCoefficient.html )
あなたが持っている唯一の情報は、シーケンス全体で各タイプの要素の固定数があるということであるため、これにランダムアクセスを混在させると問題が発生すると思います。これは、シーケンス全体の情報としてはそれほど多くはありません。また、シーケンスの前半については、単独ではほとんど何も語っていません。