首页 > 代码库 > 元素递归坍塌压缩算法以及同元素构建压缩算法(中)
元素递归坍塌压缩算法以及同元素构建压缩算法(中)
版权申明:算法的任何权利均归本人所有,但任何开发者或组织或团体可以使用本算法进行开发和研究,如再本算法的基础上研究除新算法,亦只需要申明基础算法来源即可,算法商业化必须要做到无论使用本算法开发什么产品,一旦该产品使用本算法,就必须开发对应的中文版本,中文版本要求为中文显示95%以上.本条款适用与本篇以及上篇和下篇中提到的算法,如果条款有冲突,以本条款为主.
前面我们已经讲清楚了元素递归塌陷压缩算法,实际上,这个算法有点过于理想化,完全依赖于数学,如果能够实现,那么效果也是非常好的,但是,我也讲明白了他的缺点,也算是所有压缩软件的缺点,那就是无论在怎么压缩,到了一定的压缩率就不可能再压缩下去了,信息的压缩是有极限的,因为要包含那么多信息就必须有相应的信息载体,如果载体不足,那么信息就不可能无损。
那么,有没有办法解决这个问题呢,答案是有的,而且也是从本质上入手,既然你需要这么多载体是因为你有这么多信息,那么要解决这个问题我们就要先解决信息的大小的问题,如果我们把信息本身给减少了,那么是不是说信息的载体就可以相应的减少?是的,这个概念很容易理解,所以我们要搞定信息量的问题,把要传输的信息的数量减少,而且还要保证信息的完整性,好吧,我承认这是一个很有意思的命题,因为这要求我们两者兼顾而不是牺牲一边满足另一边,好吧,让我们来解决这个问题。
首先了,我们要清楚一件事,那就是如果已经打包好了,传输过程中我们是不可能进行操作的,因为那样丢掉的信息绝对找不回来了,这就违背了我们的初衷,所以我们只能在压缩之前想办法,想什么办法呢?恩,我们指导,有一门学科叫做密码学,专门研究怎样用最少的载体表达最多的信息或者用大量的载体去隐藏一段信息,后面的部分我们不需要管,我们只需要前面那一部分,对了,就是研究怎样用最少的载体表达最多的信息。影视节目中有一个桥段大家都不陌生,那就是不知道是主角还是反派把杯子往地上一摔,然后就冒出大量的刀斧手,当然,接下来的情景就少儿不宜了。。。。从这个过程我们能分析出什么呢?首先,信息的传递是摔杯子,也就是说我们可以研究信息的传递,但这与本文的主题无关,也许某一天我会取研究,但本文不会。既然不是信息的传递,那么是什么的,在这之前,我先问个问题:刀斧手是怎么知道要出来的呢?很容易把,听到杯子被摔的声音就出来,那么,刀斧手是怎样知道摔杯是叫他们出来呢,上头吩咐的,是的,这就是重点,放到今天来看,也许我们常常会有这样的例子:嘿,哥们,我明天去钓鱼,你去不?好!,美女,我请你吃晚饭怎么样?可以啊;于是,当天晚上有意哥们成功抱得美人归,而第二天又有好多鱼倒霉;看到这里,我们分析一下这三个案例,很明显,他们都有一个共同点,那就是事先约好的,于是,我们看到了今天的重点:约定!通俗的来讲,就是事先说好的,这个约定在密码学中那是时时刻刻都被用到,而具体的约定规则,有个好听的名字,叫做密码本,密码本,归根到底,其实就是许许多多的约定的集合
看到这里,就有疑问了,我研究的是压缩算法,与密码这种东西有什么关系?还别说,是没什么关系,但这次还真能用到,你看啊,密码中的约定是一个字对应一个字的,那么我们压缩算法的目的根本就不是保密而是压缩,是不是可以约定好一个字对应多个字?这样我们用我们的约定去替换,是不是就减小了信息的总体大小?如果约定多了是不是可以大大减小信息的大小,信息本身小了压缩下来是不是体积就会更小?当然,看到这里是不是觉得好zip算法没有区别?如果是,请再仔细看看,这两者之间还是有区别的,特别是实现起来,zip的数据字典是根据文件来自己生成的而我们的约定确是固定的,固定到不管什么文件来做压缩,都是使用同一个约定,这样才不会因为文件被转移而造成无法解压,要知道zip算法生成的数据字典其实是和压缩文件放在一起的,而且人家只是对你的文件重新排序,根本就没有打算从根本上减少信息本身的大小。
那么我们为什么要使用同一个约定呢?很简单,因为我们做的是在减少信息本身的大小,也就是在破坏信息本身的完整性,我们做无损压缩不能把信息本身给破坏了,所以这样的话我们只能使用同一个约定,或者说密码本,当然,如果我们这样做的话某些文件的压缩率可能达不到要求,因为他的大量的信息不在我们的密码本上,我们无法进行替换裁剪,那么这时候我们要做的就是先用zip算法压缩一遍,然后再来干,如果还不行,还有另外的办法,另外的办法本文不会写出来,因为。。。因为下班了,肚子饿了要回家吃饭。。。
好了,写到这里,大家看出来了,我的办法就是弄一个固定的密码本当做数据字典,然后将这个字典分离,不写到文件中去,这样就能更进一步的减少文件体积,当然,这不是一个完整的算法,这只是一个思想,还是一部分思想,因为本文只实现了元素间的替换/压缩,还没有实现构建,而构建,才是算法的重点,本算法中最精彩,最出格的部分。
下班鸟,等有时间再写下篇
元素递归坍塌压缩算法以及同元素构建压缩算法(中)