数据压缩的基本常识

[AlexiaChen]

---

title: 数据压缩的基本常识
date: 2014-03-05 11:41:52
tags:
- 数据压缩

首先解释一个原理：就无损压缩来说，如果一个算法能压缩一个文件，就必然存在另一个文件是压缩之后比原文件还要大的，这个原理还想不通的话可以参考抽屉原理。

于是，设计一个压缩算法，首先就要考虑什么文件是能压缩的，什么文件是不能压缩的。对通用压缩算法来说，我们通常只会做一个基本的假设：在文件中如果出现了一个串Sx，那么其它地方出现Sx的概率相对会比别的串概率要高。

就目前来说，ZIP/RAR这一类算法都是基于这个原理，所以它们也无一例外不能压缩完全随机生成的文件。

于是给出两个命题：

• 如果你设计的一个压缩算法不是出于对重复串的建模，那么它基本不可能成为通用的压缩算法。
• 如果你设计的算法〔能压缩任何文件〕，那么一定不存在有效的解压算法。