Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

You need both index and length, I guess. If concatenating both value is not enough to gain sufficient size shrink, you can always prefix a "number of times still needed to recursively de-index (repeat,start-point-index,size) concatenated triplets", and repeat until you match a desired size or lower.

I don’t know if there would be any logical issue with this approach. The only logistical difficulty I can figure out is computing enough decimals and search the pattern in it, but I guess that such a voluminous pre-computed approximation can greatly help.



No invertible function can map every non-negative integer to a lower or equal non-negative integer (no perfect compression), but you can have functions that compress everything we care about at the cost of increasing the size of things we don't care about. So the recursive de-indexing strategy has to sometimes fail and increase the cost (once you account for storing the prefix).


Is there some inductive proof of that? Or is that some conjuncture?

Actually any resources related to that point could be fun to explore


It's a classic application of the pigeonhole principle, the first on in this list:

https://en.wikipedia.org/wiki/Pigeonhole_principle#Uses_and_...




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: