压缩的理论（它与算法信息论密切相关）以及率失真理论，这个领域的研究工作主要是由美國學者克劳德·香农（Claude Elwood Shannon）奠定的，他在二十世纪四十年代末期及五十年代早期发表了这方面的基础性的论文。Doyle和Carlson在2000年写到数据压缩“是所有的工程领域最简单、最优美的设计理论之一”。密码学与编码理论也是密切相关的学科，数据压缩的思想与统计推断也有很深的渊源。
许多无损数据压缩系统都可以看作是四步模型，有损数据压缩系统通常包含更多的步骤，例如它包括预测、频率变换以及量化。
Lempel-Ziv（LZ）压缩方法是流行的无损存储算法之一。DEFLATE是LZ的一个变体，它针对解压速度与压缩率进行了优化，虽然它的压缩速度可能非常缓慢，PKZIP、gzip以及PNG都在使用DEFLATE。LZW（Lempel-Ziv-Welch）是Unisys的专利，直到2003年6月专利到期限，这种方法用于GIF图像。另外值得一提的是LZR （LZ-Renau） 方法，它是Zip方法的基础。LZ方法使用基于表格的压缩模型，其中表格中的条目用重复的数据串替换。对于大多数的LZ方法来说，这个表格是从最初的输入数据动态生成的。这个表格经常采用霍夫曼编码维护（例如SHRI、LZX）。
目前一个性能良好基于LZ的编码机制是LZX，它用于微软公司的CAB格式。
最好的压缩工具将概率模型预测结果用于算术编码。算术编码由芬蘭信息理論學家Jorma Rissanen发明，并且由Witten、Neal以及Cleary将它转变成一个实用的方法。这种方法能够实现比众人皆知的哈夫曼算法更好的压缩，并且它本身非常适合于自适应数据压缩，自适应数据压缩的预测与上下文密切相关。算术编码已经用于二值图像压缩标准JBIG、文档压缩标准DejaVu。文本输入系统Dasher是一个逆算术编码器。