4 ms·
That's because natural data has low entropy But let's say every paragraph only offers 1 bit of entropy. Then a 160 bit hash gives you fuzzy accuracy up to 160
by __s 5y ago
That's because natural data has low entropy
But let's say every paragraph only offers 1 bit of entropy. Then a 160 bit hash gives you fuzzy accuracy up to 160 paragraphs. After that you'll have to extend the hash with hints to guide which sequence of paragraphs you're looking for, & hints for where the typos are
ofc, 100x compression of English text doesn't require this amount of compute to decompress: https://en.wikipedia.org/wiki/Hutter_Prize https://en.wikipedia.org/wiki/Hutter_Prize
It's also impractical since most compression use cases want to put the work in compression, & have decompression be straight forward
edit: 100x was misreading, it's currently 8.6x http://prize.hutter1.net/#prev http://prize.hutter1.net/#prev
- AnimalMuppet 5y ago"Paragraph" is highly optimistic. IIRC, each English character has about 1 bit of entropy.
- __s 5y agoShannon estimated 0.6 to 1.3: https://cs.fit.edu/~mmahoney/dissertation/entropy1.html https://cs.fit.edu/~mmahoney/dissertation/entropy1.html For the sake of argument I figured I'd be highly optimistic. The linked prize shows practical evidence of 1GB of Wikipedia being compressed below 1 bit per character (& that's with a limit of 50 hours cpu time, 10GB memory, & 100GB disk)
- ganzuul 5y agoThis is very abstract, but I believe that since both input and output are very close in program space compared to the total size of PS, the heuristics to map between them are going to be of a manageable size. This is based on an intuition about a single source for all activity in this universe.