注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

古诗压缩  

2011-02-18 20:25:21|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
我从灵石岛的古诗库上用程序搜集了1100万字左右的中国古诗(各个朝代都有,23090406 字节)
我曾经想过为这些文本开发一个查询系统,不过,因为文件还是太小,直接用vim的查找功能查找的速度都接近打字速度了,所以意义不是很重大。于是,我萌发了另一个想法:探索针对古诗的文本压缩算法。

用zip和rar这两种格式压缩这个文本(用winrar,默认的参数),得到的结果如下:

text.txt: 23090406 Byte
text.zip:14722837 Byte   (63.8%)
text.rar:12844514 Byte   (55.6%)

可见,rar还是比zip的压缩效果好一些的。(速度也慢一点)

我想设计一种能够超越zip的压缩算法。
话说回来,zip是一种很优秀的压缩算法,想超越它似乎有难度。不过,zip设计的目标是要为各种文件(文本、图片、程序。。。)提供压缩,而我要设计的是针对这一个古诗文本的压缩算法,因此,我获得了多得多的信息,就有了超越的可能。

先分析一下这个庞大的古诗文本的特点。一眼望去,我看到了几个特点:
1.由汉字组成(也有一点标点符号)
2.每一行都比较短,并且很多行的格式是十分工整的。(要不然就是散文了)
除此以外,似乎没有更多的信息。因为古诗不同于现代文,它使用了众多的非常用字,所以好像没有更多能够压缩的地方。

我统计出这个古诗文本中一共出现了11365个不同的字符。
出现次数前5名的是:
。(句号)     746032次
,(逗号)     685568次
换行符(10)     482776次
换行符(13)     482776次
不                    84026次
可以看到,前四个非汉字的字符和后面的字符的出现频率有一个极大的鸿沟。
于是,我萌生了一个想法:先将。,10、13分离出来,再压缩其他的字符。
windows下的换行符永远是13后面跟着一个10,所以可以把10和13看做一个整体,只用记录一遍。
我统计出了所有换行符的位置,发现有很多连续的段形成等差数列(这是显然的,因为很多古诗都是7言或者5言)。
于是,对原数列计算二阶差分,就出现了一大堆的0。我对其进行Huffman编码,压缩到272K左右。
不过,这个方法对句号和逗号的效果不明显。为什么呢?主要是因为某些句子内部的句号和逗号的排列比较混乱。
于是,我采取了一个方法:把换行符编码之后统统剔除,将逗号和句号视作相同,对其位置进行编码,之后再对每个位置到底是逗号还是句号(标点的样式)进行编码。
对逗号和句号的位置计算二阶差分,出现一大堆0,Huffman编码得到的结果是536K左右。
对于标点的样式,它其实就是一个十分有规律的01串。其中有大片的连续的01交错以及连续的0.我先采用了一种比较朴素的压缩方法:每8个连续的位看做一个字节,之后Huffman编码。这样,能够压缩到99K左右。
至此,对逗号句号换行符的初步分析完成了,得到了一个用了0.9M完成了编码的算法。(注意到这4种字符在原文件中占了2.4M)

于是,可以开始看看汉字的部分了。
我发现,古诗中没有能够在出现次数上“秒杀全场”的字,不像现代文5%以上的字都是“的”。
对剩余的文本进行朴素的Hufman编码,压缩到了12.87M。
这样,压缩的文件加起来13.8M左右,已经能够超越zip了。

我想看看能否超越rar。
为了进一步压缩,我打算从汉字部分这个“大头”下手。
因为古诗中没有特别明显的”词语“的概念,所以相邻的”词语“的位置一般相距很远很远。这个表明只能以字为单位进行压缩。
我先尝试一种类似memcached的策略:
建立一个队列。每次编码一个字的时候先查找它是否在队列中,如果是用它在队列里的位置做编码,否则用它本身做编码。之后将这个字插入到队列尾(如果已经在队列中就把它移动到队列尾),如果队列的大小超过了一个限定值就删除队列头的元素。
不过,因为古诗中相同的汉字也离的很远,我经过调参之后发现最佳的队列大小是10,命中率很低(4%左右),导致优化效果极其不明显。
怎么办呢?
我想起马尔科夫链了。虽然相邻的词语差着很远,不过相邻的字之间还是有一些关系的。
例如,”不“后面跟的比较多的是”能“、”得“等等。我萌生了一个想法:
对”不“后面的字进行单独的Huffman编码。这个有一定的效果,文件大小能够减小几个K.
于是,我再接再厉,对出现次数比较的字(例如一、人)后面的字都单独进行Huffman编码,文件大小又下去了。
一不做二不休,我对于所有出现次数超过100的字后面跟的字都试图进行单独的Huffman编码,对于导致文件体积反而膨胀的字我就排除它,这样搞一通之后,汉字部分的体积降低到11.5M了。

现在,对标点符号的编码反而成为瓶颈。
我发现,对标点符号的位置进行一阶差分之后数字的出现比较有规律(例如一大堆8,因为7言诗很多),二阶差分之后反而出现了比较混乱的情况。我采取了一个策略来综合这两者:
对数列计算一阶差分。之后如果一个数和它前面的数相同就将它修改为0。对数列进行Huffman编码,换行符和逗号句号的体积分别下降到了247K和456K左右。
现在,文件的总体积已经是12.3M左右了,离rar只有一步只遥。不过,优化的难度陡然增大了。哪里还能再挤出一点体积呢?

我发现,标点符号的样式的压缩方式似乎比较粗糙。我试图使用RunLenth对其进行编码,每两个位合成一个整体,调参之后发现,效果还不如8个位合成一个Byte的Huffman呢。怎么办呢?
把序列二阶差分,出现了大片的0,之后再进行RunLenth编码,只编码连续的0的个数,文件体积就又下降了20K。

折腾到底之后,总的文件大小大约能压缩到12.27M,离rar的12.24M还是差了20多个K。看来rar真是一种神奇的压缩格式,超越它比较有难度。

哪里还能再挤出一点空间呢?我发现,Huffman编码是一种粗糙的编码方式,它需要存储一个字典,同时无法充分利用字出现的频率之间细微的差别。而改善这个的方式就是算术编码。它可以用实数的二进制位数来对一个符号进行编码,同时,可以利用自适应的方式避免存储字典。经过计算,如果把所有的Huffman编码换成算术编码,文件体积还可以再下降30K左右。这样,就能够和rar比肩了。

不过,我至今还没有理解算术编码该怎么写。。。
  评论这张
 
阅读(912)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017