前几天一直有人联系我讨论我2年前设计的极限压缩算法，我恨惊讶，作为一个基础类算法，是没有什么盈利空间的，而且我设计完发布到网上两年了居然还有人感兴趣，本着开源精神，现重新整理一下发布上来，版权申明，开源的是算法，并不代表可以商用，个人研究没有问题，但搞成商业化产品还是需要本人授权的，尽管我并不打算换来什么东西，但在天朝，有些东西还是弄明白的好。
讲到压缩算法，大名鼎鼎的应该算是zip算法了，这个算法应该算是应用最为广泛的，哪里都能看到他，但研究一下其核心思想（注意：这里仅仅只研究核心思想，而不是阅读源代码，本文只会讲纯粹的理论，不会讨论如何写代码更加有效率）发现归类的话应该算是同元素归并，比如有一串数据是111111111111111，那么按照zip压缩的话，可能得到的结果就是16个1，然后翻译一下就是116，当然，具体的过程并不是这样，这里只是举例说明，在zip算法中有个核心的东西，叫做数据字典，这个数据字典并不是我们平时玩数据时的数据字典，而是所有在待压缩文件中出现频率比较高的数据的合集（如果这里看不懂，请回去好好翻一下概率论，尽管我也考试不及格，但我看懂了，数据结构中有这个玩意，名字叫啥我忘了，因为我考数据结构是做的小抄。。），是不是有点眼熟？对咯，鼎鼎大名的信息论应该听过吧，关于信息论中数据压缩这块应该听过吧，zip其实就是这些理论的实现。
当然，还有其他的压缩算法，比如Linux下常用的tar，等等，实现算法大同小异，归根结底，其源头都是信息论，这里不得不说信息论的影响深远，但是，关我什么事呢，当然，我并不否定信息论，因为它将讲的基本都是正确的，但是，正确并不代表一定要听他的，这是两回事，信息论给我们在杂乱的信息世界开了一扇窗户，使得我们更加容易看到并使用信息，但这也限制我们只能通过信息论的窗口去接触信息的世界，某些时候，我们其实可以不受限制的。
好了，现在我们抛开信息论，开始接触信息或者说计算机世界的两条基本原理，第一条：计算机什么都不认识，只认识二进制，并且，计算机永远不会考虑过程，只会考虑结果；第二条：所有的储存在计算机上面的信息，归根结底都是二进制串。
可能对着两条有点疑问，我来解释一下：第一条前半段应该好理解，难点是后半条：计算机不会考虑过程，只会考虑结果；量子计算机也许不适合这条规则，但晶体计算机一定适合，（先申明，这条理论是我设计这套算法的基础，也仅仅适合这套算法，其他算法和理论请勿对号入座。）对于文件而言，在计算机读取他前是不会在乎它长什么样的，他只会在乎读取的时候是什么样，甚至还没读取完到底时候前面未读部分长什么样计算机都不会关心，这点那些玩密码的最清楚，灵感来源也是玩密码的，是我翻密码学的时候找出来的。第二条我想更加好理解，二进制什么的接触计算机的人就知道，所以这没什么好说的。
好了，理论基础讲完了就该讲讲干货了（再不讲估计要被扔臭鸡蛋了）请注意，这篇文章会讲两种算法，而且都是新设计的，这篇讲的是元素递归塌陷压缩算法，恩，这里每个字，每个词都能看懂，但是组合到一起就头晕了，这都什么东西啊这是。。。好吧，我一一解释，首先，元素，这个词很好理解，就是基本原子，放在信息论中可能非常好理解，但放在这里可能会有点头晕，木有关系，不会晕的，元素，你可以理解为一个个数据片段；然后是递归，恩，这是个会让人疯掉的词，玩递归玩好了非常省事，玩不好能让你哭，所以不解释了，因为在这里就是字面上的意思；塌陷，这个好理解吧？组合起来就是一个个数据片段通过递归的方式塌陷掉了，没了，干嘛去了了，原来是被压缩了。。。恩，没错，就是这个意思！
好了，我们现在正式讲讲这个算法的过程，首先呢，需要有一份到压缩的文件，然后呢，对这份文件的基本信息记录一下，用来做还原的对比，具体记录的信息我这里不再说明，但无非就是hash值啊什么的，接下来就要开始干活了，怎么干呢，前文我们提到了元素，也就是数据片段，这里的片段可不是随便弄的，是有要求的，当然，对内容没有要求，以为内整个算法直接无视掉了编码问题，是基于二进制层面来的，所以通篇不用考虑编码问题，要求有两点，一点是片段切割长度固定，另外一点是运算完成后的结果仍然长度固定，打个比方，比如说我从文件末尾截下16个长度为8个字节的数据片段，然后我通过运算得到结果，再按照每8个字节作为一个片段来切割，只剩下了15个，而且这15个是一个位不多，一个位不少，这样，我们就干掉了8个字节的数据，然后呢，我们对整个文件这么来一遍，你可以想象，我们“干”掉了多少数据？什么？1/16？你开玩笑呢，1/16能叫递归坍塌吗？递归啊，亲，你难道不会将生成的结果写到文件尾，然后在切割16个元素下来在运算一次啊？浪费点电会死的，电费又不要你交，是公司交。。。于是我们可以看到这样一个结果：经过一晚上的运算，我的文件终于被压缩好了，只是，这1kb大小的是什么玩意啊？说好的高清蓝光原盘怎么就剩下1Kb了？元素递归坍塌压缩算法你到底干了什么？人家快捷方式都不止1kb呢，你忽悠人吧？
额。。确实，我是在忽悠人，因为根据信息传播理论，信息压缩是由上限的，超过这个上限就不能做无损压缩了，具体的上限情况我不知道，因为要根据信息含量的多少和实际使用的情况做对比，当然这里的信息是指所有的信息，而不是有效信息，单单提取有效信息就不是无损压缩了（关于这条，可以多想一下，也许我的认识并不正确）于是，当我们做递归压缩的时候可能会发生一件事，那就是无论怎么计算，我们都无法将16个元素计算成15个元素，这就意味着这16个元素中包含的信息已经达到极限，不可能再包含了，于是，这时我们就要想办法了，什么办法呢？简单，无视掉就可以了，直接将他拿下了，放到另外一个文件上去，做好详细的标记，然后继续递归，遇上无法递归了就又拿下来，直到递归完整个文件，然后我们就可以将递归完的结果与我们记录的结果给合并起来，继续递归估计是不可能了，但可以想想另外的办法，至于另外的办法，我将在下篇讲到。
看到这里，就都知道了这个算法的核心思想，就是怎样将16个元素经过运算变成15个（或者更少）的元素，而且还能够给还原过来，这个算法我没办法解决，因为我高数不太好，年年不及格的那种，不过我相信能搞定它，特别是那群玩密码的，另外，请不要再问格式、编码的问题，因为在本算法中，没有编码，没有格式，所有的数据我全都当做数学数值来计算的，这样就可以用纯粹的数学运算来解决问题，而不是一大堆由格式和编码搞出的莫名其妙的问题，至少哪怕zip算法，对iso问价你的压缩率基本没有超过10，而对于文本文件没有低于过50.。。
关于算法的任何问题，请在下面留言讨论，如果讨论代码问题。。。我只能说上班时间没空，不过，你信吗，反正我信了。
写的比较杂乱，看需求吧，元素递归塌陷压缩算法过于理想化，实现起来比较难，下篇会讲到基于zip算法而修改过来的算法，那个比较容易，不过，同样的，压缩比没有这么高，但实现起来会更加容易，基本上就是信息论+密码学+编码理论
独孤青冥
2014年12月1日
原文：http://my.oschina.net/u/1265071/blog/350809