11–18 of 18 posts
Really interesting. I was trying to implement a compression algorithm selection heuristic in some file format code I am developing. I found this to be too hard for me to reason about so basically gave up on it. Feels like this blog post is getting there but there could be a more detailed sets of equations that actually calculate this based on some other parameters. Having the code completely flexible and doing a full…
Arithmetic coding of a single bit preserves ordering of encoded bits, if CDF(1) > CDF(0). If byte's encoding process is going from higher bits to lower bits, arithmetic coding (even with dynamic model) will preserve ordering of individual bytes. In the end, arithmetic coding preserves ordering of encoded strings. Thus, comparison operations can be performed on the compressed representation of strings (and big-endian…
Sketch of the argument:
First, an arithmetic coder maps strings to non-overlapping subintervals of [0, 1) that respect lexicographic order.
Second, the process of emitting the final encoding preserves this. If enc(s) ∈ I(s), enc(t) ∈ I(t), and I(s) Finally, binary fractions compared left-to-right bitwise yield the same order as their numerical values — this is just memcmp.
Thus, we have a proof of your claim that arithmetic coding preserves lexicographic order! Nice result!
My mistake was in thinking that leading zeros are discarded -- it is tailing zeros that are discarded!
Then there is this eternal conversation about whether on should encrypt and then compress or compress and then encrypt. Encrypted data will not compress well because encryption needs to remove patterns and patterns are what one exploits for compression. If you compress and then encrypt, yes you can leak information through the file sizes, but there isn't really a way out of this. Encryption and compression are fundam…
Really interesting. I was trying to implement a compression algorithm selection heuristic in some file format code I am developing. I found this to be too hard for me to reason about so basically gave up on it. Feels like this blog post is getting there but there could be a more detailed sets of equations that actually calculate this based on some other parameters. Having the code completely flexible and doing a full…
the compression algorithm you select for your data is quite dependent on the dataset you have. the equations in this blog post don't help you choose which compression to use, but rather "how much" and when to compress. I would be curious to formalize the math for different compression algorithms though... might be a good follow up post!
But it is hard to decide how to judge the cpu vs disk/network tradeoff like you explain in the article.
I was a bit curios if I could make an API so on the top level user enters some parameters and the system can adjust this calculation according to that.
But had some issues with this because the hardware budget used by all parts of the system, not only by the compression code.
As an example network is mega fast in data center but can be slow and expensive when connecting to a user. The application can know which case it is executing but it is hard to connect that part of the code into the compression selection stuff cleanly.
Also on network case. It might make sense to keep data large but cpu time low until I hit the limit but nothing matters when I hit the limit.
Would be cool to have a mathematical framework to put some numbers in and be able to reason about the whole picture