I'm experimenting with building a data-structure optimized for a very specific use-case. Essentially, I am trying to build a compressed bitset of a constant size, and obviously for that use-case, two operations exist: read the value of a bit or write the value of a bit.
The best case scenario would be to be able to read a byte and write a byte in-place in constant time, but I can't imagine that it would be possible to write to an arbitrary byte without making changes to the rest of the compressed chunk of memory. However, it might be possible to read an arbitrary byte in an amount of time that tends toward O(1).
I have been reading Wikipedia articles, and I'm familiar with LZO, but is there a table somewhere which describes the various features and tradeoffs that various compression systems provide? I'd like a moderate level of compression, and I'm mainly wanting to optimize around memory holes, e.g. large gaps of bytes which are zeroes.
Assuming that you are doing many of these random accesses, you can build an index (once) to a compressed stream to get O(1). Here is an example for gzip streams.