压缩算法与软件

现今的压缩格式种类繁多，常见的有zip,rar, 不常见的7z，imp，ace，bz2等，多的让人数不过来，今天有兴致研究了一把这些格式的压缩算法。
压缩算法包括有损，无损两种，一般的有损压缩是在执行特定的有损变换后再执行无损压缩，所以这里我们只讨论无损压缩算法。按照一些教材的分类(这些教材可 能偏老，现代的压缩算法不知还能否这样分)，无损压缩一般可分为基于统计模型和基于字典模型的两大类，最早的应用于数据压缩领域的算法应该是基于统计模型 的Huffman算法(1952)，在Unix和Dos的早期版本中都可以找到基于Huffman算法的软件，不过现在已经极少用了。
1977/1978，两个聪明的以色列人提出基于字典模型的算法LZ77，LZ78，这两个经典文献提出的算法成为了当代几乎所有流行压缩软件的算法核 心。1982年, LZSS算法作为LZ77的改良被提出，大量的压缩软件使用了这个算法，如zip,arj,lharc等，1985年，LZ78的改良LZW提出，LZW 也得到广泛的应用，如GIF图像中的压缩算法，Unix下的compress程序。但由于LZW存在专利问题，此后的应用并没有LZSS广泛。
如今大量的新的压缩格式出现，如bzip2，imp，他们都能够提供比前辈们更高的压缩率，这些压缩软件的核心算法则比较新，如PPM，BWT等，也难以查到相关资料。不过有很多网站定期做最新压缩算法的评测，可以做参考http://compression.graphicon.ru/ybs或者http://www.maximumcompression.com/, 看看最新的评测结果，排名靠前的压缩软件有Slim 20，Durilca 0.3，Epm 9，7Zip 3.11，Paq6等, 只有7zip我用过，其它连听都没有听说过！它们大多能提供比WinRar3.3还要小10～20%的压缩结果，只是速度一般比较慢，耗用内存比较多，再 加上用户界面的简陋(大多是命令行界面),所以没有流行起来，其中有些软件还是OpenSource的, 如PAQ, 7zip，厉害。