话说压缩软件.或许可以再好点.

泡不烂的凉粉 发布于 2012/10/30 21:29
阅读 224
收藏 0

在这里不是比较压缩软件所应用的算法. 也没有深入压缩软件对与内部细节算法之类的研究,只是浅显的讨论一下. "压缩" 这个目的.

此文的由来:
之前去一个站点下载源码. 发现源码被整理成 N多个包, 有讲合并成单一源文件的 压缩包.也有直接从仓库里倒出来的源文件压缩包. 还有附带编译脚本以及测试脚本的压缩包.和一些编译好的文件压缩包. 更有所有文件的压缩包.
换句话说. 如果我把这些压缩包全部下载回来. 并且全部解压开, 就会有80%上上的文件是完全相同.
我想当然的以为,如果我将所有包解开,并重新压缩成一个包, 大小会远远小于 这些压缩包不解压,直接压缩在一个包的体积大小.  

当然,我的想法太天真的.我错了.由此我重新做了一个尝试:
 我将一个任意文件压缩成一个压缩包, 大小约为1M, 之后我复制了几次,产生了大约5个同样大小的文件. 这5个文件内容应该是一模一样的. 之后我讲这5个文件重新压缩打包成一个. 结果很让人失望. 4M多, 接近5M .  尝试用 ZIP 以及 RAR 结果都是远远大于任何1个文件大小很多.

由此想到. 压缩软件在特定环境下, 或许可以牺牲一点点的时间, 换取更大的压缩率. ------很明显,5个完全一样的文件压缩后大小不应该超过单独文件很多. 

所以... 楼下的给点补充... 我想大家应该知道我想说什么了.     改进......... 如何入手?

加载中
0
mallon
mallon
了解一下维纳的信息论吧
0
七液
七液

嗯好吧自己来扯一点自己知道的。

1.压缩包采用的压缩方式其实都是。文件单一压缩,而不是将所有文件都读到内存里进行一次性压缩。那样压缩效果自然很好。你可以做个试验把五个文件合并成一个。再进行压缩,就绝对比单独五个文件要小得多了。

分开压缩的好处是其中一个损坏了其他的也可以用。而且程序设计容易管理文件方便。解压就更方便了。你完全不用重新建立字典就可以解压了。

2.如果第一条不变的情况下。你最好是采用专用算法压缩。压缩算法一般分为

通用压缩算法和专用压缩算法。大部分压缩软件压缩算法原理无外乎

LZ,Huffman,数学压缩。就算有一些算法也都是根据这三种算法进行改进的。比如LZMA,xt之类的算法。也无非就是重新设定了字典排序方式。如果基于这个思路不变的话。只能采用现有专用压缩算法来处理各种不同类型的数据了。

比如有的时候适当的加入RLE算法可以提高压缩比。衣服BMP图片你用RLE压缩后再用通用压缩算法处理。你会惊奇的发现压缩速度快了一倍多。压缩后的体积还小了20%左右。或者是采用文件XOR来减小重复数据。消除过多的重复数据再进行压缩。其他的方法成本太大。特别是自己研究一种算法

数学算法不到万不得已别用。解压代价很大。通用软件最好不用。某些极端的数学算法号称可以把地球上所有数据压缩成四个字节。当然了这只是理论上。实际开发中还是得自己想办法来处理各种重复数据的问题。因地制宜吧。

压缩后再压缩是没有压缩比的。信息熵概念看一下你就知道为什么压缩包压缩为什么没有压缩比了。还有压缩视频为什么没有压缩比。但是转码后效果就好很多。

0
岛
记录一下文件的哈希值  一样的哈希就索引一下呗,反正我自己写游戏数据包就是这样做的  
七液
七液
你这样不是和通用压缩算法一样么?比如LZ算法。数据一块一块都HASH了。存储HASH到时候根据这个HASH来解压。最后还是回到原来的话题。如何增大压缩比。
0
泡不烂的凉粉
泡不烂的凉粉
改进,并非 推倒重来, 比如压缩软件对多个文件压缩的时候. 都对每个文件记录一个CRC32值.

这个是已经存在的, 如果压缩软件在稍微多做点工作, 就会发现,新加入的文件CRC32数值,和之前包内存在的一致. 之后重新用第二种算法匹配一下结果. 答案一致, 可认定新加入数据和之前已经存储数据一致, 一个简单的数据结构就可以节约N多存储空间.

依据就是, 内容相同的文件,在压缩字典相同的情况下,压缩后的内容一致.  压缩软件只要稍微匹配一下新加入的内容是否以前已经存在了就可以确定是否需要节约这部分存储空间. 并且这点改进对压缩文件结构不会产生任何副作用. 也不会改变原有软件压缩算法. 只需要将原来文件存储结构稍微改变一点点,  另外多做一个CRC32比较. 这个比较应该是O(n),相对于压缩,这个开销与节约的存储空间比较,是可以接受的.   小改进节约大空间.

Y
YsykZheng
回复 @看能不能改个名 : 照你的说法数据字典如何确定,不可能1M的,10M,100M的个算个的
七液
七液
回复 @看能不能改个名 : 你说的这个就是最简单的游程压缩的思路。我知道你的意思。所以我早就回你了。谁会压缩两个完全相同的文件呢?更何况十个
泡不烂的凉粉
泡不烂的凉粉
回复 @七液 : 这么看来,你真的不知道我在说什么了. 我说的 "压缩" 并非是让一个大文件变成一个小文件, 而是让10个相同的文件,变成一个1个,并且体积不会明显膨胀很多. 你可以尝试一下将一个文件复制成10个,然后用压缩软件压缩这个文件, 结果与一个一个文件,压缩成压缩文件的结果大小是否相差很多.
七液
七液
而且。谁会压缩两个完全一样的文件?部分相同差不多,那样的话你还是回到原来的话题上。两个文件都要重新合起来计算字典了
七液
七液
首先你说的CRC算法来匹配。压缩算法内部已经这么做了。 你想要新加入的文件可以再次进行压缩。只能从头来。数据本质已经决定这样的压缩方式了。字典的建立不可能两个文件用一个压缩字典前面和后面的文件居然不是一样的结果和数据分布。 所以你只能把第一个文件的数据也算进来重新计算字典
0
Y
YsykZheng

我记得有一个压缩算法只能处理2G大小的文件。就是把文件全部读到内存,在压缩,这个算法压缩的文件远远小于7z,rar,zip,gz,bz2等

Y
YsykZheng
回复 @七液 : 不知道呀,有时间去看看
七液
七液
回复 @YsykZheng : ACG游戏 70%是H的嘿嘿
Y
YsykZheng
回复 @七液 : acg没怎么玩,就是那些色色的游戏解压时看到的
七液
七液
回复 @YsykZheng : 特别是岛国的ACG游戏吧。那些CG图片几乎都是这么压缩的。。:D
Y
YsykZheng
回复 @七液 : 对,这个以前在玩游戏的时候看到过,很多游戏都是用个算法的工具去压缩的。
下一页
0
宝石骑士
宝石骑士
完全相同的文件,有必要都保留吗,存一个不就行了。这种需求根本就不存在。
返回顶部
顶部