http://roaringbitmap.org/
+1 to this. OP is using the wrong flavor of compression for the task at hand. OP, look up sparse bitmaps.
Bitpacking and Compression of Sparse Datasets
11–16 of 16 posts
Re: Bitpacking and Compression of Sparse Datasets
#12Regarding the benefits of knowing your data on compression: rearranging the dimensions of a dataset can also yield interesting increases in compressibility.
For example, you can store your position records arr[T][X,Y] as arr[X,Y][T]: that is, sequences of bits representing how each point on the grid evolves over time, rather than sequences of bits representing boards. These single-position time-series should both be more internally predictable (lower entropy), and more isotropic (having similarity with other features, allowing secondary compressibility) than the original ones, and you should be able to repopulate the in-memory 3D array from the serialized representations in roughly the same time (ignoring caching effects, because a 19x19x28 array is a very small array.)
Of course, this doesn't always work: the same magic could be applied to videos... but decompressed videos do not fit easily into memory, let alone are they small enough to ignore cache-coherency during reads/writes, so actually doing the dimensional transforms is a bit implausible. (But if we really needed a video squeezed 10x more than we do today, and were willing to spend hours on both ends doing so, it'd certainly be possible.)
Re: Bitpacking and Compression of Sparse Datasets
#13http://roaringbitmap.org/
+1 to this. OP is using the wrong flavor of compression for the task at hand. OP, look up sparse bitmaps.
Are these really sparse? He is working with Go boards. Go games are usually hundreds of moves and by the end of the game, most of the board will be populated with stones, so on average somewhere under half of all recorded intersections will have stones (the crowded late game positions balance the empty early game positions). Sparse matrix representations usually require a lot of sparsity to shine, I was under the impression.
Re: Bitpacking and Compression of Sparse Datasets
#14I recently used LZ4 compression to save RAM used by infrequency accessed data in my app.
LZ4 is 1.5 times faster than Snappy, the compression however is better:
https://www.percona.com/blog/2016/04/13/evaluating-database-...
Re: Bitpacking and Compression of Sparse Datasets
#15Earlier quoted context omitted.
Not quite; I would describe it as moving the complexity into the algorithm. For example, even though the bitpacking from the post achieves fast good compression, it is unable to compress floats in general; merely 1.0 and 0.0. The knowledge of that correspondence has been moved into the algorithm.
> For example, even though the bitpacking from the post achieves fast good compression, it is unable to compress floats in general; merely 1.0 and 0.0. Fewer bits does not always mean better compression, particularly if the data has other patterns which is destroyed by the packing. With Apache ORC, I found out that if you bit-pack data to say 7bits vs leaving it as 8 bits, the 8 bits version compressed much more with…
Your comment, particularly the degradation in byte alignment leading to worse subsequent compression, reminds me of the following Hacker News comment by NelsonMinar from then end of November 2016:
https://news.ycombinator.com/item?id=13049894
>It's crucial to evaluate encoding space usage in the context of compression. For instance gzip(base16(data)) is often smaller than gzip(base64(data)) for practical data. Even though base64 is more efficient than base16, it breaks up data across byte boundaries which then makes gzip significantly less efficient.
Re: Bitpacking and Compression of Sparse Datasets
#16> If you know the structure of your data, you can easily do a better and faster job of compressing than a generic compression algorithm. I'd change this to: the ease of doing a better and faster job of compressing than a generic compression algorithm will be a function of the data's Kolmogorov Complexity. You can easily know your data's structure (e.g. strings no larger than N bytes containing natural language in a l…
Not quite; I would describe it as moving the complexity into the algorithm. For example, even though the bitpacking from the post achieves fast good compression, it is unable to compress floats in general; merely 1.0 and 0.0. The knowledge of that correspondence has been moved into the algorithm.
Ah, hate I missed this at the time of comment (got on a flight right after I posted and forgot to check back :/).
What you're describing (moving complexity into the algorithm) _is_ an increase in Komogorov Complexity, though... so I think we're saying the same thing?
i.e. Kolmogorov complexity K(x|y) (x, given y) is the length of the shortest program that on input y, outputs x.
So, when you say "move complexity into the algorithm", this is an increase the length of the shortest program that given input outputs .
Or have I missed or misunderstood your point?