Re:The mathematics of compression in database systems
by codeismightier on Saturday February 14, 2026 @09:50PM
(#47020598)
Intriguing claim! At first I was skeptical, thinking that there would be an issue with leading zeros being discarded. However, with some piloting, I was able to use Claude and ChatGPT to construct a proof of your claim.
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!
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.