The mathematics of compression in database systems(bitsxpages.com) |
The mathematics of compression in database systems(bitsxpages.com) |
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 representations of integers and even floating point values), without the need to decompress data until that decompressed strings are needed.
Another view: strings are compared by memcmp as if they are mantissas with the base 256. "hi!" is 'h'(1/256)+'i'(1/256)^2+'!'(1/256)^3+0(1/256)^4 and then there are zeroes to the infinity. Arithmetic encoding represents encoded strings as mantissas where base is 2. Range coding can utilize other bases such as 256.
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) <= I(t), then enc(s) <= enc(t).
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!
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 fundamentally at odds with each other.
Your argument explains correctly that "encrypt then compress" is not an option, because in this order compress will do nothing, except wasting time and energy.
On the other hand "compress then encrypt" is more secure then simple encryption, because even a weak encryption method may be difficult to break when applied only to compressed data, because this use is similar to encrypting random numbers, i.e. the statistical properties of the plaintext have already been hidden.
The only disadvantage of "compress then encrypt" is in the less frequent cases when you are more concerned with deceiving traffic analysis of the amount of data sent than with saving resources, when you will pad anyway your useful data with irrelevant junk, to hide the real length of the data.
If you send data that is highly compressible, even if you want to hide the length it may be advantageous to first compress the data, and then pad it with junk before encryption, to hide the length.
Thus, you might e.g. compress the data 8 times, then double the length by padding and still send less data than without compression, while also masking the true length.
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 load production test with desired parameters to find the best tuning is an option but is also very difficult.
Also read this previously which I find similar.
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