私はJavaについてあまり知らないので、私の解決策は一般的でなければならないと思います:)
1.リストを圧縮します
ブール値は非効率的であるため、それぞれList<Boolean>をに圧縮する必要がありますList<Byte>。簡単です。一度に8つ取得するだけです。
最後の「バイト」は不完全である可能性があるため、もちろんエンコードされたビット数を保存する必要があります。
2.要素のリストをシリアル化する
続行するには2つの方法があります。リストの項目数をエンコードするか、パターンを使用して終了をマークするかです。アイテムの数をエンコードすることをお勧めします。パターンアプローチではエスケープが必要で、不気味です。さらに、パックされたビットではより困難です。
長さをエンコードするには、可変スキームを使用できます。つまり、長さをエンコードするために必要なバイト数は、すでに使用した長さに比例する必要があります。最初のバイトにプレフィックスを使用することで、長さ自体をエンコードするために使用されるバイト数を指定できます。
0... .... > this byte encodes the number of items (7 bits of effective)
10.. .... / .... .... > 2 bytes
110. .... / .... .... / .... .... > 3 bytes
スペース効率が非常に高く、デコードはバイト全体で行われるため、それほど難しくはありません。これはUTF8スキームと非常によく似ていると言えます:)
3.再帰的に適用します
List< List< Boolean > >[Length Item ... Item]それぞれItemがそれ自体である場所になりますList<Boolean>
4.ジップ
zlibJava、またはまたはのような他のライブラリで利用できるライブラリdeflateがあると思いますlcw。それをあなたのバッファに渡し、それがかかる時間に関係なく、あなたができるだけ多くの圧縮を望むことを正確にすることを確認してください。
表現に繰り返しパターンがある場合（表示されていないパターンでも）、それを圧縮できるはずです。しかし、それをばかげて信用しないでください。「圧縮された」形式が「圧縮されていない」形式よりも軽いことを確認してください。常にそうであるとは限りません。
5.例
リストの端を追跡するのはスペースを消費することに気づいたところ:)
// Tricky here, we indicate how many bits are used, but they are packed into bytes ;)
List<Boolean> list = [false,false,true,true,false,false,true,true]
encode(list) == [0x08, 0x33] // [00001000, 00110011] (2 bytes)
// Easier: the length actually indicates the number of elements
List<List<Boolean>> super = [list,list]
encode(super) == [0x02, 0x08, 0x33, 0x08, 0x33] // [00000010, ...] (5 bytes)
6.スペース消費
ブール値がありList<Boolean>、nそれをエンコードするために消費されるスペースは次のとおりです。
booleans = ceil( n / 8 )
ビット数（n）をエンコードするには、次のものが必要です。
length = 1 for 0 <= n < 2^7 ~ 128
length = 2 for 2^7 <= n < 2^14 ~ 16384
length = 3 for 2^14 <= n < 2^21 ~ 2097152
...
length = ceil( log(n) / 7 ) # for n != 0 ;)
したがって、リストを完全にエンコードするには、次のようにします。
bytes =
if n == 0: 1
else : ceil( log(n) / 7 ) + ceil( n / 8 )
7.小さなリスト
ただし、1つのコーナーケースがあります。それは、スペクトルの下限（つまり、ほとんど空のリスト）です。
についてはn == 1、bytesに評価されますが2、これは実際には無駄に思えるかもしれません。ただし、圧縮が開始されるとどうなるかを推測しようとはしません。
さらに詰めたいと思うかもしれません。バイト全体を保持するという考えを放棄すれば可能です...
- 長さのエンコーディングを（バイト全体で）そのままにしますが、を「パディング」しないでください
List<Boolean>。1要素リストは0000 0001 x（9ビット）になります
- 長さのエンコーディングも「パック」してみてください
2番目のポイントはもっと難しく、事実上2倍の長さのエンコーディングになります。
- 長さをエンコードするビット数を示します
- 実際にこれらのビットの長さをエンコードします
例えば：
0 -> 0 0
1 -> 0 1
2 -> 10 10
3 -> 10 11
4 -> 110 100
5 -> 110 101
8 -> 1110 1000
16 -> 11110 10000 (=> 1 byte and 2 bits)
非常に小さなリストではかなりうまく機能しますが、すぐに縮退します。
# Original scheme
length = ceil( ( log(n) / 7)
# New scheme
length = 2 * ceil( log(n) )
限界点？8
うん、あなたはそれを正しく読んでいます、それは8要素未満のリストにのみ良いです...そして「ビット」によってのみ良いです。
n -> bits spared
[0,1] -> 6
[2,3] -> 4
[4,7] -> 2
[8,15] -> 0 # Turn point
[16,31] -> -2
[32,63] -> -4
[64,127] -> -6
[128,255] -> 0 # Interesting eh ? That's the whole byte effect!
そしてもちろん、圧縮が開始されると、それは実際には問題にならない可能性があります。
のアルゴリズムに感謝するかもしれませんがrecursive、実際のスペース消費量の数値を計算するか、実際のテストセットにアーカイブを適用して実際にテストすることをお勧めします。
8.再帰的/変数コーディング
私は興味を持って答えを読み、彼がエリアスオメガコーディングTheDonに提出したリンクを読みました。
それらは、理論的な領域では、正しい答えです。残念ながら、それらは非常に実用的ではありません。主な問題は、それらが非常に興味深い漸近的な振る舞いをすることですが、実際にギガバイト相当のデータをエンコードする必要があるのはいつですか？まれに。
職場でのメモリ使用量に関する最近の調査では、ほとんどのコンテナが1ダース（または数十）のアイテムに使用されていることが示唆されています。非常にまれなケースでのみ、1000に到達します。もちろん、特定の問題については、実際に自分のデータを調べて値の分布を確認するのが最善の方法ですが、経験から、データはローエンドにあるため、スペクトルのハイエンドだけに集中することはできません。 。
TheDonのアルゴリズムの例。私がリストを持っていると言う[0,1,0,1,0,1,0,1]
len('01010101') = 8 -> 1000
len('1000') = 4 -> 100
len('100') = 3 -> 11
len('11') = 2 -> 10
encode('01010101') = '10' '0' '11' '0' '100' '0' '1000' '1' '01010101'
len(encode('01010101')) = 2 + 1 + 2 + 1 + 3 + 1 + 4 + 1 + 8 = 23
再帰を停止するためのさまざまな「しきい値」を備えた小さなテーブルを作成しましょう。のさまざまな範囲のオーバーヘッドのビット数を表しますn。
threshold 2 3 4 5 My proposal
-----------------------------------------------
[0,3] -> 3 4 5 6 8
[4,7] -> 10 4 5 6 8
[8,15] -> 15 9 5 6 8
[16,31] -> 16 10 5 6 8
[32,63] -> 17 11 12 6 8
[64,127] -> 18 12 13 14 8
[128,255]-> 19 13 14 15 16
公平を期すために、私はローエンドに集中しました、そして私の提案はこのタスクに適しています。しかし、それはそれほど明確ではないことを強調したかったのです。特に、に近いため1、log関数はほぼ線形であり、再帰はその魅力を失います。しきい値は非常に役立ち3、良い候補のようです...
に関してはElias omega coding、それはさらに悪いです。ウィキペディアの記事から：
17 -> '10 100 10001 0'
それだけです、11ビットの大騒ぎ。
道徳：手元のデータを考慮せずにエンコード方式を選択することはできません。
だから、あなたList<Boolean>が数百の長さを持っていない限り、わざわざ私の小さな提案に固執しないでください。