2 ms·
Palindromes can be compressed 50% by using their symmetry. Representing a number as 3 palindromes would "compress" a number to 1.5 times the original size in th
by yorwba 8y ago
Palindromes can be compressed 50% by using their symmetry. Representing a number as 3 palindromes would "compress" a number to 1.5 times the original size in the worst case. Obviously not an improvement.
If the number itself happens to be a palindrome, you can get down to 50%, but that's completely unrelated to this trick.
In general, it's impossible for a compression algorithm to losslessly compress all numbers to a shorter representation, it can only make some numbers shorter and others longer. (Pigeonhole principle: there are not enough short codes, so if you assign a shorter code to all numbers, some will get the same code, making the compression not lossless.)
Practical uses of compression are all about reducing the average length given a nonuniform probability distribution, so a palindrome-based compression scheme would only be useful if you could expect most numbers you're dealing with to be palindromes.