Editing Lossless compression (section)

=== Mathematical background ===
Abstractly, a [[compression algorithm]] can be viewed as a [[Function (mathematics)|function]] on sequences (normally of octets). Compression is successful if the resulting sequence is shorter than the original sequence (and the instructions for the decompression map). For a compression algorithm to be [[lossless]], the compression map must form an [[Injective function|injection]] from "plain" to "compressed" bit sequences. The pigeonhole principle prohibits a bijection between the collection of sequences of length ''N'' and any subset of the collection of sequences of length ''N''−1. Therefore, it is not possible to produce a lossless algorithm that reduces the size of every possible input sequence.<ref>{{cite book |doi=10.1007/978-3-319-16250-8_3 |chapter=The Pigeonhole Principle |title=Proof Patterns |date=2015 |last1=Joshi |first1=Mark |pages=19–23 |isbn=978-3-319-16249-2 }}</ref>