Data Compression and the Limits of Compressibility across Types of Data

Abstract

ABSTRACT Storing and transmitting data costs space and bandwidth, and data compression reduces both by representing the same information in fewer bits, but how much a file can be compressed is not the same for all data: some kinds shrink greatly while others barely shrink at all, because compression works by removing redundancy, and different data contain different amounts of it. This study examines data compression and the limits of compressibility across types of data. The compression ratio, the factor by which a file's size is reduced, was examined for several kinds of data, from highly redundant to already dense, so that the wide variation in how much different data can be compressed, and the reason for it, could be seen. The compression ratio varied widely with the kind of data: text, source code, and log files compressed greatly, shrinking to a fraction of their size, because they contain much redundancy, repeated words, patterns, and predictable structure, that compression can remove; whereas already-compressed or encrypted data hardly compressed at all, since they contain little or no redundancy left to remove, and media such as photographs and audio compressed only modestly when compressed without loss, their content being already fairly dense. The amount a file can be losslessly compressed is therefore set by how much redundancy it contains, which differs greatly between kinds of data, and there is a limit beyond which no lossless method can go. For media, much greater compression is possible if some loss of fidelity is accepted, discarding detail the senses barely notice, which is how images and audio are usually compressed. The study shows that compressibility depends on the redundancy in the data and is bounded by it, and it discusses the implications for compressing different kinds of data.

KEYWORDS: Data compression, Compression ratio, Redundancy, Lossless compression, Lossy compression, Entropy, Information theory, Data storage, File formats