5 ms·

I just found the following paper on "random access compression". They do claim constant time lookup. https://pdfs.semanticscholar.org/1511/11c0c6dec6104bbf70d6

• joosters 9y ago
  Interesting paper, but I'm not sure that I understand its claims sufficiently. In section 3.1, it seems to talk about a table that is effectively an index into the compressed data. So to find the position of codeword 'i' you can look it up in the table select(D,i) This could be practical if the codes being compressed were large, because the index has a chance of being smaller than the original data. The original article is discussing a bitmap, so the codewords are 1 bit long and there is no chance that an index of positions of individual bits could ever be smaller than the original data.