Ein universeller verlustfreier Kompressor kann nicht existieren. Genauer gesagt ist für jeden verlustfreien Kompressor Folgendes sicher:
Diese Eigenschaften werden unten gezeigt. Sie beeinträchtigen jedoch nicht den Vorteil verlustfreier Kompressoren. In der Praxis sind die Wörter, Nachrichten oder Dateien, die komprimiert werden sollen, nicht willkürlich und werden zufällig aus allen möglichen Wörtern, Nachrichten oder Dateien ausgewählt. Kompressoren nutzen ihre Besonderheiten. Kompressoren sind dann bei einigen Datentypen sehr gut und bei anderen sehr schlecht.
Damit für diese Art von spezialisierten Kompressoren, die Information durch den Kontext zur Verfügung gestellt für die Kompression verwendet wird (siehe Informationstheorie ).
Diese Unmöglichkeit kann leicht experimentell überprüft werden. Hier ist ein Shell- Skript , das eine Datei erstellt, die das 100-fache der Zeile "blabla" enthält. Anschließend werden 100 aufeinanderfolgende Komprimierungen dieser Datei mit dem gzip- Kompressor ausgeführt und schließlich die erhaltenen aufeinander folgenden Größen angezeigt:
for i in `seq 1 100`; do echo "blabla" >> toto001; done for i in `seq 1 100`; do gzip -c "toto`printf "%03d" $i`" > "toto`printf "%03d" $((i+1))`"; done wc -c toto*In der Praxis wird häufig überprüft, dass eine Datei, die bereits das Ergebnis einer Komprimierung ist, durch Anwenden des Kompressors schlecht komprimiert oder sogar vergrößert wird. Darüber hinaus weigert sich gzip standardmäßig, Dateien mit der Erweiterung ".gz" zu komprimieren, was ein Zeichen für eine frühere Anwendung dieses Kompressors ist.
Ein verlustfreier Kompressor kann als Injektion von Wörtern in Wörter gesehen werden, d. H. Als eine Funktion wie
impliziert .Es ist dann leicht zu überprüfen, ob für jedes Wort einer der beiden folgenden Fälle überprüft wird:
Dies zeigt die dritte Eigenschaft der oben genannten Unmöglichkeit. Die ersten beiden leiten sich daraus ab, weil, wenn es eine strikte Komprimierung gibt, d. H. Wenn es ein Wort gibt, das größer als seine komprimierte Version ist , dann:
Wir können auch feststellen, dass es unmöglich ist, alle Wörter einer bestimmten Größe streng zu komprimieren : Tatsächlich gibt es Größenwörter für ein Buchstabenalphabet und nur Wörter mit streng weniger Buchstaben.