Hacker News new | past | comments | ask | show | jobs | submit
I wonder if it might make more sense to come at it from the opposite angle. Take pi as a sequence you want to compress with. But pi, being random, has redundancies in it that make it less than optimal. So instead, for a given size of block you want to look up, design the optimal number to use for compression. For instance, if you want to compress "594" in the digits of pi, the sequence 253 appears before it twice, which means any attempt to "compress" any three-digit sequence that only first appears after the second 253 is costing you more to get past the second 253, and "pi, but with all the 253s removed after the first one" is clearly a more efficient encoder for 3-digit numbers than pi itself.

So, instead of using pi, design an optimal number to encode with.

What you'll find is that the optimal sequence ends up being equally efficient as listing the blocks in order and indexing by block number itself. There are a number of other solutions; you could use superpermutations to get "all possible subsequences" with fewer digits in your target number, but you'll end up needing to provide the encoder and decoder a table of where the digit sequences appear since they are no longer regular and indexing into that table will cost exactly the same as just writing your number as the concatenation of all the blocks and its efficient method for indexing into them by indexing on the block rather than the digit number.

This actually has some natural overlap with the "normal numbers" in that one of the earlier normal numbers was: https://en.wikipedia.org/wiki/Champernowne_constant I'm not sure whether this is necessarily optimal for an arbitrary block size. (My quick intuitive check suggests it may be, but "my quick intuitive check" in the time of an HN post is not something I'd count on.) In this scheme, you can include the fact that the person using this constant to encode knows the nature of the constant, so they know that if you give index 0-9, it's single digit, and if you index into the two-length blocks, it must have a length of two. Since the encoder and decoder know that, they can also skip the middle of the block and just index into "the n'th number"... which degenerates into "the index of number N is N", which means this is not a compression scheme.

To put all that in a nutshell, if you want to deeply understand why this compression scheme doesn't work, I think you can attain a deep understanding of why by optimizing it.