Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Does an uncompressable string exist? [closed]

I was wondering if there is one or more strings that cannot be losslessy compressed. More formally:

Let String be a string, f(var) a compression function which returns a compressed version of var, g(var) a decompression function such that g(f(var)) = var and strlen(var) a function which returns the length of var,
is there a valid value for String such that strlen(String) < strlen(f(String)) or strlen(String) = strlen(f(String))?

Theoretical answers are welcome, as well as examples in different languages and with different compression algorithms.

like image 336
Giulio Muscarello Avatar asked Jan 01 '13 14:01

Giulio Muscarello


2 Answers

The pigeonhole principle tells us that for any given compression function*, there must always be at least one input string that will be expanded.


* i.e. a function that genuinely compresses at least one input string.
like image 78
Oliver Charlesworth Avatar answered Nov 02 '22 23:11

Oliver Charlesworth


I would expect that this string would fit the bill: ""

like image 27
NYCdotNet Avatar answered Nov 03 '22 00:11

NYCdotNet