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