3 ms·
You can make that more concise too. An ideal compressor would be able to map every string of length n to a string of length m<n and back. Since a bijection requ
by Kliment 17y ago
You can make that more concise too. An ideal compressor would be able to map every string of length n to a string of length m<n and back. Since a bijection requires that its source and target sets are of the same cardinality, and there are more strings of length m than length n, this compressor cannot be a bijection. Or even more concisely: you can't fit 10 pigeons into 9 pigeonholes unless one pigeon shares.
- Ariens 17y agoIsn't it the opposite? there are more strings of length n than the number of string with length m < n. There are b^n strings of length n, but only (b^n - 1)/(b - 1) strings of length m < n, where b is the number of possible characters
- Kliment 17y agoOops, indeed, it was meant the other way around. Past the edit window now though. Thanks for pointing it out.