词典压缩:减小词典的内存占用
好的压缩算法:压缩率,压缩速度,解压速度(最重要)
一元编码
Elias Gamma:
x=2^e+d
e+1:一元编码
d:二元编码
Elias Delta:
x=2^e+d
e+1:再使用Elias Gamma编码一次
d:二元编码
Golomb & Rice
因子1=(X-1)/b,因子1+1,一元编码
因子2=(X-1) mod b,使用二元编码,编码宽度在log(b)
Golomb: b=0.69*Avg(序列平均值)
Rice:2的整数次幂,所有小于Avg中最接近Avg的数值
变长压缩算法SimpleX
Simple9: 32位比特位,4个比特为管理数据存储区,28个比特压缩数据存储区
Simple9的28位有9种表示形式
Simple16: 28位有16种表示形式,并且通过非当项完全固定长度,解决数据区有浪费位的情况
PForDelta:目前解压速度最快的一种倒排文件压缩算法
1,对待编码的连续K个数值(一般为128),确定10%的大数数值,根据70%小数确定夺取的比特宽度,确定整个序列
2,对原始数据遍历,将大数放置到尾端,并转换成链表结构的序列
3、将所有数字压缩到队列中
文档编号重排序
网页的文档ID+单词词频信息,文档ID使用D-Gap进行编码
将内容越相似的网页,在编排文档号时越相邻
海量数据文本聚类速度较慢,将URL相似的网页聚合在一起,假设同一个网站的很多页面表达的主题内容是近似的
静态索引裁剪:主动抛弃一部分不重要的信息(索引项)来达到数据压缩的效果
以单词为中心的索引裁剪:
判断单词与文档的相似性,每个词典中的单词,其对应的倒排排列中至少保留K个索引项,还要保留若干富余项目
实验证明,如果首先对所有索引项的原始得分减去得分最低索引项的得分,再采取(对K个项进行折扣,乘一个折扣因子,得出阈值a,剩下的大于a保留)方法进行裁剪,效果会大大提升
因为
索引项得分分差相关不大,比较集中在某个区间,所以减掉得分最低项
以文档为中心的索引裁剪:更为常用
在建立索引之前进行数据预处理,把与文档主题表达不相关的单词抛弃,如停用词
posted on 2013-11-04 12:56
胡满超 阅读(774)
评论(0) 编辑 收藏 引用 所属分类:
搜索引擎