Paradoxe du compresseur
Un compresseur de données informatiques parfait ne peut exister : pour compresser tous les messages de moins de n bits inclus, il faut 2n messages de moins de n bits (strictement). Or le nombre de messages de strictement moins de n bits est 2n-1. Ainsi, quelle que soit la méthode, un compresseur ne peut compresser tous les messages.
Cependant, il est rare que tous les messages possibles soient utilisés, et les compresseurs actuels se servent de cette particularité. Des compresseurs seront alors très bons avec certains types de données, et moins bons avec d'autres. Ainsi pour ces types de compresseurs spécialisés, l'information fournie par le contexte est utilisée pour la compression (voir théorie de l'information).