I don't know much about Java, so I guess my solution will HAVE to be general :)
1. Compact the lists
Since Booleans are inefficient, each List<Boolean>
should be compacted into a List<Byte>
, it's easy, just grab them 8 at a time.
The last "byte" may be incomplete, so you need to store how many bits have been encoded of course.
2. Serializing a list of elements
You have 2 ways to proceed: either you encode the number of items of the list, either you use a pattern to mark an end. I would recommend encoding the number of items, the pattern approach requires escaping and it's creepy, plus it's more difficult with packed bits.
To encode the length you can use a variable scheme: ie the number of bytes necessary to encode a length should be proportional to the length, one I already used. You can indicate how many bytes are used to encode the length itself by using a prefix on the first byte:
0... .... > this byte encodes the number of items (7 bits of effective)
10.. .... / .... .... > 2 bytes
110. .... / .... .... / .... .... > 3 bytes
It's quite space efficient, and decoding occurs on whole bytes, so not too difficult. One could remark it's very similar to the UTF8 scheme :)
3. Apply recursively
List< List< Boolean > >
becomes [Length Item ... Item]
where each Item
is itself the representation of a List<Boolean>
4. Zip
I suppose there is a zlib
library available for Java, or anything else like deflate
or lcw
. Pass it your buffer and make sure to precise you wish as much compression as possible, whatever the time it takes.
If there is any repetitive pattern (even ones you did not see) in your representation it should be able to compress it. Don't trust it dumbly though and DO check that the "compressed" form is lighter than the "uncompressed" one, it's not always the case.
5. Examples
Where one notices that keeping track of the edge of the lists is space consuming :)
// 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. Space consumption
Suppose we have a List<Boolean>
of n
booleans, the space consumed to encode it is:
booleans = ceil( n / 8 )
To encode the number of bits (n
), we need:
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 ;)
Thus to fully encode a list:
bytes =
if n == 0: 1
else : ceil( log(n) / 7 ) + ceil( n / 8 )
7. Small Lists
There is one corner case though: the low end of the spectrum (ie almost empty list).
For n == 1
, bytes
is evaluated to 2
, which may indeed seem wasteful. I would not however try to guess what will happen once the compression kicks in.
You may wish though to pack even more. It's possible if we abandon the idea of preserving whole bytes...
- Keep the length encoding as is (on whole bytes), but do not "pad" the
List<Boolean>
. A one element list becomes 0000 0001 x
(9 bits)
- Try to 'pack' the length encoding as well
The second point is more difficult, we are effectively down to a double length encoding:
- Indicates how many bits encode the length
- Actually encode the length on these bits
For example:
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)
It works pretty well for very small lists, but quickly degenerate:
# Original scheme
length = ceil( ( log(n) / 7)
# New scheme
length = 2 * ceil( log(n) )
The breaking point ? 8
Yep, you read it right, it's only better for list with less than 8 elements... and only better by "bits".
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!
And of course, once the compression kicks in, chances are it won't really matter.
I understand you may appreciate recursive
's algorithm, but I would still advise to compute the figures of the actual space consumption or even better to actually test it with archiving applied on real test sets.
8. Recursive / Variable coding
I have read with interest TheDon
's answer, and the link he submitted to Elias Omega Coding.
They are sound answers, in the theoretical domain. Unfortunately they are quite unpractical. The main issue is that they have extremely interesting asymptotic behaviors, but when do we actually need to encode a Gigabyte worth of data ? Rarely if ever.
A recent study of memory usage at work suggested that most containers were used for a dozen items (or a few dozens). Only in some very rare case do we reach the thousand. Of course for your particular problem the best way would be to actually examine your own data and see the distribution of values, but from experience I would say you cannot just concentrate on the high end of the spectrum, because your data lay in the low end.
An example of TheDon
's algorithm. Say I have a list [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
Let's make a small table, with various 'tresholds' to stop the recursion. It represents the number of bits of overhead for various ranges of 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
To be fair, I concentrated on the low end, and my proposal is suited for this task. I wanted to underline that it's not so clear cut though. Especially because near 1
, the log
function is almost linear, and thus the recursion loses its charm. The treshold helps tremendously and 3
seems to be a good candidate...
As for Elias omega coding
, it's even worse. From the wikipedia article:
17 -> '10 100 10001 0'
That's it, a whooping 11 bits.
Moral: You cannot chose an encoding scheme without considering the data at hand.
So, unless your List<Boolean>
have a length in the hundreds, don't bother and stick to my little proposal.