整数のリストを圧縮しようとしています。ここで:
「出現」統計は次のとおりです。
ですから、この種のデータを圧縮する最良の方法を教えてください (推定圧縮率 - 可能であれば - は高く評価されます)。
この種の分布(a)では、おそらく Huffman などの可変長エンコーディング スキームを調べたいと思うでしょう。これにより、固定の 5 ビット サイズよりもはるかに優れた圧縮が得られます。それらは、より一般的な値を示すために少ないビットを使用して (そして一般的でない値を表すために多くのビットを使用して)、平均ビット幅を下げることによって機能します。
単純なケースを取り上げて、ビットが数字の 1 を表し、他のすべての数字が現在の 5 ビット スキームに続くビット0で表されるとしましょう。1
つまり、1 つの値ごとに 4 ビット (1,242,149 x 4 = 4,968,596 ビット) を節約し、他のすべての値 (1,239,964 ビット) に対して 1 ビットを「浪費」し、正味で 370 万ビットを節約します。
これは、特定のデータ セットの「ハードコードされた」ハフマン スキームであり、それがどのように機能するかを示すためのものです。おそらく、任意のデータ セットにもう少し適応したいと思うでしょう。
そして、より大きな量を含むようにそれを拡張すると、追加の改善が行われます. 最上位の値の節約は既にわかっています。
Bit pattern Value Quantity Saved bits
0 1 1,242,149 4,968,596 (4 per)
1xxxxx >1 1,239,964 1,239,964- (1 per)
---------
Net saving 3,728,632 (extra return 3,728,632)
上位 2 つの値:
Bit pattern Value Quantity Saved bits
0 1 1,242,149 4,968,596 (4 per)
10 2 620,038 1,860,114 (3 per)
11xxxxx >2 619,926 1,239,852- (2 per)
---------
Net saving 5,588,858 (extra return 1,860,226)
上位 3 つは次のとおりです。
Bit pattern Value Quantity Saved bits
0 1 1,242,149 4,968,596 (4 per)
10 2 620,038 1,860,114 (3 per)
110 3 309,399 618,798 (2 per)
111xxxxx >3 310,527 931,581- (3 per)
---------
Net saving 6,515,927 (extra return 927,069)
上位 4 人については、次のとおりです。
Bit pattern Value Quantity Saved bits
0 1 1,242,149 4,968,596 (4 per)
10 2 620,038 1,860,114 (3 per)
110 3 309,399 618,798 (2 per)
1110 4 154,983 154,983 (1 per)
1111xxxxx >4 155,544 622,176- (4 per)
---------
Net saving 6,980,315 (extra return 464,388)
このレベルでは、数値ごとに固定の 5 ビットを使用するスキームは、12,410,565 ビットになります。正味 6,980,315 ビットの節約により、合計圧縮サイズは 5,430,250 ビットになり、固定ビット サイズの方法よりも約 56 ビット節約できます。
より多くの価値が追加されるにつれて、追加の投資収益率がかなり急速に減少することがわかります。上位 4 つの値を超えると、このハードコードされたスキームでは何も保存されません。これは、アイテムごとのビット節約がゼロ (その後はマイナス) になるためです。真の適応エンコーディングは、(xxxxxビットの最適化も行うため) より多くの節約をもたらしますが、おそらくそれほど多くはありません。
(a)見た目からして非常に不自然なディストリビューション。各量は前の量の約半分であるため、可変長エンコーディングは理想的なソリューションです。
ハフマンコーディングを見てください。頭のてっぺんからの正確な詳細はわかりませんが、基本的な原則は、必要に応じて、より一般的な数値に少ないビットを割り当て、一般的でない数値に多くのビットを割り当てることです。これにより、全体として、数値あたりの平均ビット数が少なくなります。均一な分布に期待するよりも (1 文字あたり最大 5 ビット)
情報の圧縮については、 http://en.wikipedia.org/wiki/Huffman_codingを参照してください。
リスト内のほとんどのアイテムの頻度は、リスト内の頻度の低いすべてのアイテムの頻度の合計よりも高いため、実際にはアイテムあたり約 2 ビットの効率が得られます。
正確な圧縮では、シンボルあたり平均 2.00915 ビットが提供されます。以下の計算は、私が選択したエンコーディングを明らかにします。
(1242149 + 2 * 620038 + 3 * 309399 + 4 * 154983 + 5 * 77816 + 6 * 38601 + 7 * 19651 + 8 * 9790 + 9 * 4830 + 10 * 2447 + 11 * 1253 + 12 * 597 + 13 * 303 + 14 * 130 + 15 * 73 + 16 * 23 + 17 * 17 * 18 * 4 + 19 * 4 * 20 * 2 + 21 * 1 + 22 * (1+1)) / 2482113.0
周波数は常に 2 の逆べき乗に近いとは限らないため、http://en.wikipedia.org/wiki/Arithmetic_codingの方がわずかに圧縮率が高くなる可能性があることに注意してください。