百科问答小站 logo
百科问答小站 font logo



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

  

user avatar   ruan-xing-zhi 网友的相关建议: 
      

不可行。


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

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


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

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


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

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

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

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



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

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


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

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

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


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


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

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

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


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


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


user avatar   liukeming1991 网友的相关建议: 
      

额,你会发现,后期你用来保存存位置的“索引”(比如你那个100)才是数据源。




  

相关话题

  如何看待《中国学生所谓的数学牛逼》这篇文章? 
  工程上存在那么多不确定情况,为什么计算机不能利用它们产生真随机数,而只能根据逻辑产生伪随机数? 
  闭区间上的导函数f'有界,是否可以在闭区间上取到最大值,最小值? 
  摩尔定律是正确的么? 
  这题怎么写?急!? 
  如何评价 Michael Francis Atiyah? 
  在机器学习模型的训练期间,大概几十分钟到几小时不等,大家都会在等实验的时候做什么? 
  含有√ax+b的积分,除了将∨ax+b直接替换成t还有其他的做法吗? 
  Cauchy定理的证明是否依赖于Jordan曲线定理? 
  c++怎么在1到n这些数中随机产生k(k<n)个?当然,k个数互不相等。有什么比较好的写法吗? 

前一个讨论
酒爵上为何有两个小铜柱?
下一个讨论
日本傍晚五点的时候都会放音乐,有什么意义吗?





© 2025-05-29 - tinynew.org. All Rights Reserved.
© 2025-05-29 - tinynew.org. 保留所有权利