2 ms·
How does one work with compressed data directly? If you are dealing with the data in blocks, then your compression is only as good as the repetition in each blo
by chii 8y ago
How does one work with compressed data directly? If you are dealing with the data in blocks, then your compression is only as good as the repetition in each block (perhaps the dictionary can be shared).
But even in this case, you don't deal with compressed data directly, but decompress only 1 block at a time.
- lifthrasiir 8y agoThere are some operations that can be efficiently done over the compressed data itself. Compressed bitmap is a good motivating example (and I really liked Roaring Bitmap [1]). But I guess that such efficiency is very specific to the exact operation and the viability of general compressed operation is unclear; as a related example, fully homomorphic encryption (FHE) that does the same over ciphertexts is still an active research problem. [1] https://github.com/RoaringBitmap/RoaringBitmap https://github.com/RoaringBitmap/RoaringBitmap
- js8 8y agoNo, the quality of the compression depends on what is the probability distribution of your data blocks. If some blocks are much more likely to occur, then you can compress them better (put them in a smaller number of bits). What I mean by "directly" is instead of having to do y = y + c^-1 (x_i) where c(x) is the compression function (and c^-1 is its inverse, decompression), we could define a function f such that z = f(z, x_i) and final y = c^-1(z). This f would entail both the "+" (operation to be done on the data) and c^-1 (the decompression). In general, it's non-trivial to come up with f, but I do believe that it would be in many cases a better approach than to use the first method. Floating-point numbers can be seen as a simple case of this. If we represent numbers in fixed decimal point, then we have a lot of 0s in the numbers (and also lot of digits of very low significance) that we mostly don't need to have there. Therefore, in practice, we use compression - floating-point representation. The operations on FP are more complicated (you have to align the mantissas before you do arithmetic operations), but it's a good trade-off.
- davrosthedalek 8y agoIn most, if not all compression schemes, your "compression function" depends on all x_j with j<i. So it's really a new function for every i.