I'm looking for a fast (especially fast on the decompression side) way to compress sets with small domains. Let me be more concrete: I'd like to compress a set representing some fixed size subset of all bytes. For example, 64 values out of the 256 possible bit values. You can think of as a set of 64 single-byte characters.

A simple uncompressed representation would be a 256-bit (32 byte) bitmap, one bit for each possible byte. I think this is optimal already for randomly distributed sets of size 128, since in that case every bit has value 1 with probability 0.5. For smaller values like 64 or 32 elements, however, it seems like we could do better. Even for 64 randomly distributed elements, it seems like the entropy per symbol is still ~0.81 bits, so 256 * 0.811 = ~208 is the best we can do? In that case it doesn't seem like there is much low hanging fruit here.

Set Delta

So then then the other thing I'm interested in is compressing aseriesof such sets, where the sets are very likely to be similar. Consider, for example, the sets induced by breaking enwik9 into 8 KB chunks and for each chunk creating the set of the most frequent 64 characters in that : on average only ~7.25 elements change from one set to the next. Said another, the xor of the bitmaps for one set compared to the next generally have only 7.25 * 2 = ~14.5 bits set. Working from the bitmap representation, what's a good way to compress such a bitmap of mostly zeros without using per-bit arithmetic coding or anything per-bit, really?

I could also abandon the bitmap representation and just explicitly store the list of indexes that were added and removed, which I guess would be ~14.5 bytes for the indexes and a couple more bytes to store the sizes of the lists. Another option would be some kind of bit-wise RLE encoding, encoding runs of zeros?