文本压缩的思考

Time: 十二月 7, 2009
Category: Programming practices

最近断断续续花了很多时间在研究文本压缩领域,没有说是数据而是文本,是因为文本在特定的场合和环境可以有更大的改进和性能提升,比如基于 ASCII码和Unicode的就可以设计得截然不同,仅用一种方案来对不同的场景产生应用,是要付出一定的代价的比如性能。而且,不同的语言又会有不一 样的表现形式,这对垂直式的压缩技术来说是一种新的挑战。

因为业务需要,我希望可以实现一种更快的压缩算法,尤其是在解码方面要有不俗的速度表现。

我尝试过对哈夫曼编码进行一些细节上的改进,但是效果不太明显,哈夫曼编码的特点就是即使极限情况下也是能够保证绝对的压缩,当然能压缩多少倒是不 一定。编码过程比较块,难点就是对于这种比特流的存储方式,解码时必须单个比特地亦步进行,耗时特别长,是我不能接受的。研究算法远不是纸上谈兵那么简 单,不是随便在纸上画一棵二叉树就能解决问题领悟到信息论的奥秘。离开实际的应用研究不存在太大的意义,所以我们要清楚面临的需求以及对算法作出何种改进

 

lz77算法比传统的范式哈夫曼可能花费的时间更长一些,毕竟哈夫曼编码只需执行一次遍历就可以统计出编码模型而lz77则需要花费更多的时间在建 立字典和回溯检索上面。不过,lz77最大的特色就是解码特别的快,与其他编码相比解码速度完全不在一个数量级上面。lz77及其变种大部分的实现都是等 长编码,是建立在字节级别上的,不是比特流,本质上速度就有很大的优势。更重要的是,lz77每解码一个字符只需向前查看一次滑动缓冲区,总的时间复杂度 是Θ(n),线性

Gzip就是lz77很成功的一个例子,不过,网上说的那点也太简单了简直不值一谈,Gzip精妙的地方在于对算法做了很多有利的改进,我猜的,因为不管我怎么设计,以及优化,总是赶不上gzip的速度,事实证明,gzip真的很优秀

在滑动窗口也就是字典的设计上,我没有使用哈稀表而是用了一个二维数组来对任意字符进行索引,一方面我懒得搞那么复杂,而且二维数组似乎更加直观因为我主要基于单字。数组保存了对在滑动窗口里出现的所有字符的索引,而且采用了插入排序来改善查询的性能

到目前为止,整个实现最值得探讨的问题,在于滑动窗口的大小以及设计能够匹配的最大的长度,是关乎压缩效果最重要的一方面

从语言的角度来看,中文又不同于英文,英文里最常见的字符如 the,of,to,and 等在极短的滑动窗口里也可以有很好的匹配效果,但是中文就不一样了,还要取决于不同字符集的实现,滑动窗口要更大一些。这里就回出现一个性能项瓶的问题, 窗口规模与匹配的最大长度是成线性比例关系的,如果滑动窗口设计的太大,即使能匹配到好的长度,程序也要花费太多的时间在Match上面,而且大量的数据 可以表明,不是所有的字符串都能够找到最优匹配的,很多情况是,在小的窗口模式下,比如31或者63,能匹配成功的平均长度是1到2位左右,也就是说,2 个比特就足以完成保存匹配长度的工作,默认我设置了3bit,是因为我发现3bit的长度和31的窗口更有压缩上的优势

最终的测试结果是,相比较gzip的实现,压缩大约80M的文本语料库,平均时间为 1.413s,解压为 0.248s,压缩率是48.5%,而gzip的测试结果是,平均时间为 0.998s,解压为 0.131s,压缩率达到25%

我一直很好奇gzip是怎么做到的,如果我用多线程的话效果是不是会好一点。

目前所知,硬件层来说使用磁盘阵列可以提高io的效率,对压缩也是有好处的。

Leave a Comment