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.
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 would expect that this string would fit the bill: ""
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With