紧缩的故事

先来讲个有关紧缩的故事，外星人拜访地球，看中了大年夜英百科全书，想要把这套书带归去。但这套书太大年夜，飞船放不下。于是外星人根据飞船的长度，在飞船上画了一个点。如许外星人心知足足的返回了本身的星球，因为这个点就存储了全部大年夜英百科全书。

再来答复两个宏不雅的问题，赞助我们熟悉在紧缩这件事上哪些是我们能做的，哪些是不克不及做的。

用反证法可以做个快速的证实。假设存在通用的紧缩算法，也就是说有个紧缩算法，对于长度为 n 的字符串，总能紧缩到长度小于 n 的字符串。总共有 2^n 个长度为 n 的不合字符串；但却只有 2^n-1 个长度小于 n 的字符串。那么必定存在两个长度为 n 的字符串 A,B，经由紧缩获得同一个字符串。如许解紧缩算法没有办法精确的解压。所以假设缺点，并不存在通用的紧缩算法。

无损紧缩

第二个问题：是否能写出一个函数，输入字符串，可以获得这个字符串最短表示的长度。谜底也是否定的，也就是说我们无法证实某个算法是最好的算法。柯尔莫哥洛夫复杂性的弗成枷⒚鹪解释的就是这个问题。用的也是反证法，有兴趣的同伙可以自行百度懂得（注 1）。

　　推荐阅读

　　WannaCry爆发的根源原来是它？

比来的WannaCry大年夜爆发仍是个谜。我们知道什么是勒索软件，也知道不受支撑/没打补丁的Windows体系是怎么被马脚应用的，但我们不知道是谁在把持WannaCry，又为什么要搞出那么大年夜阵仗>>>详细阅读

本文标题：深入浅出时序数据库之压缩篇

地址：http://www.17bianji.com/lsqh/35600.html

 1/2    1