利用无理数压缩数据是否可行？ 第1页

不可行。

无法造出某种压缩方式，使得可以压缩所有数据。

现有的各种压缩方式，都是由于数据有特殊性质，因此可以压缩。

例如，AAAAABBBBB，我们可以写成“5A5B”，这是因为“AAAAABBBBB”是很有规则的。但是我们压缩成的“5A5B”，却非常无序。

这是类似于熵的东西。我们以无序来换有序，借此节约空间，实现“压缩”。如果题主实现过哈夫曼编码，应该对这件事有切身的体会。

现在来证明为什么通用压缩是不可能的：

假设我们有某种手段，对于任意输入的二进制串，都压缩成一个更小的二进制串输出，且通过输出文件能还原出输入文件。

那么我们给定A，把它压缩成B，然后把B压缩成C……由于B比A小，C比B小，这样操作下去，我们最终可以得到一个长度为1的二进制串（不是0就是1）。

最终得到的二进制串只有两种，但输入的情况有无穷多种，无法一一对应，违反了我们的假设。

最后，无论是哪个学科都不存在天上掉馅饼的事情。一切都在于交换，你得到了什么东西，就必须为此付出代价——例如把有序变得无序。

通用压缩和永动机是一样的想法。关于永动机的研究，可以去百度贴吧民科吧一睹风采。

----------------------------------分割线---------------------------------------------

题目描述里的做法，现在已经有一个实现，在 http://www.angio.net/pi/piquery 。这个网站很有意思，它会从pi的前两亿位里面寻找你给定的字符串。

例如，“19260817”最先出现在pi的小数点后69943588位。（为了方便讨论，在下面的分析中，我们把“从第 位开始匹配”简称为“在第 位匹配”。）

不过上面这个例子，“69943588”已经和“19260817”一样长了。现在我们来分析一下用无理数来压缩数据是否可行。为了直观一些，下面的讨论都在十进制下进行。

我不知道pi是不是正规数，但是我知道 是正规数。因此，的任何一位，出现0~9的概率是均等的。

假设我们要匹配长度为 的串。那么，对于任意一个 ，在第 位匹配的概率是 。因此，在 位内都 不匹配 的概率是 。

换言之，在 位内可以匹配的概率是 。

假设我们要编码一个长度为100的串，那么根据上面的式子，即使，在 位以内匹配成功的概率也极为渺茫。也就是说，我们为了编码100位数字，要付出远大于100000000位的代价来存下它出现的位置。

因此这个问题的答案就很明确了：得不偿失。