建立索引是搜索引擎核心技术之一,建立索引的目的是能够快速的响应用户的查询。搜索引擎最常用的索引数据结构是倒排文档,倒排文档的原理其实相当简单。
我们拿以下三篇文章作为代表来说明倒排文档,文章内容为:
D1:“张钰小姐代表了中国广大淫民的根本利益”
D2:”宋祖德先生代表了中国八卦文化的前进方向“
D3:“郭敬明代表了中国作家抄袭先进生产力的发展要求”
经过分词,过滤高频词后可以构建如下的倒排文档:
张钰 ->D1,1;
代表->D1,1;D2,1;D3,1;
宋祖德->D2,1;
.....
其中,“张钰”代表一个单词,《D1,1》代表了这个单词在D1文档中出现过1次(TF);为了方便处理,往往会 把单词和文档编号转换为数字形式。
说到倒排文档压缩,首先要问一个问题:为什么要进行索引压缩?
对索引进行压缩有很多好处:比如可以 减少索引占用的磁盘空间和内存;比如可以减少I/O读写量; 比如可以查询响应速度加快;
为了能够增加压缩效果,一般在进行压缩前先改写索引内容,首先把倒排索引的数值按照大小排序,然后用差值而非实际值表示(d-gap);这个是每个压缩算法开展前要做的工作;
目前的压缩方法可以分为固定长度的和变长压缩。
1.固定长度的压缩方法
一个典型的方法是比特对齐压缩,这个方法以Byte为编码单元,不像变长压缩编码一般都以bit为编码单元;
对于要压缩的数字,一般用头两个bits代表长度,其它bit用二进制编码代表数值本身;
数值范围 头两个bit 压缩大小
0-63 00 1byte
64-16k 01 2byte
16k-4M 10 3byte
4M-1G 11 4byte
包括定长的和变长的索引压缩都有一个基本假设,就是:要压缩的大多数数值都比较小,所以压缩后占用空间不会多;
压缩率:10-20% of 原始未压缩索引;
2.变长的压缩方法
a.unary
对于要压缩的数值N来说,用N+1 个bits来表示,其中前N位是1,最后一位是0作为结束标记。
比如:
5:111110
10:11111111110
b.Elias压缩方法(gamma & delta)
对于一个要压缩的数值X,用log2(x)分解为两个数值,一个是N=log2(X),用N个1表示这个部分,另外一个是
剩余部分k=X-2powor((log2(X))),这部分数值k用二进制编码表示(长度等于N),中间用0隔开;
比如对于数值2,其压缩编码为1 0 0,因为log2(2)=1, 剩余为0;中间插入一个分割0;
比如对于数值10
N=log2(10)=3 所以第一个部分是:111
10-2(3)=2 所以第二个部分是:010
中间用0分割,所以是:111 0 010
c.Golomb压缩方法
对于一个要压缩的数值X,用公式分解:X=q*b+r+1; (0=<r<b)
其中,b叫做bucket size,可以根据情况来具体设置。我们假设b=3;
那么对于要压缩的数值10来说:
10=3*3+0+1;(q=3,b=3,r=0);
第一部分是对分解因子q进行编码,其编码方法类似于unary编码;比如对于10=3*3+0+1中,
q=1110;
第二部分是对于剩余因子r进行编码;仍然采用二进制编码,编码长度为log2(b)取上整数或者log2(b)上整数-1;
对于上面r=0; 其编码为0;
Golomb相对于Elias方法的好处就在于那个bucket size,这个值是可以设定的,可以根据索引里面
要压缩的数值的分布来调整bucket size来获得更好的压缩效果;
d.混合使用
一般对于不同的索引域,其数值的分布是不同的,各有其特点,经过分析数值分布属性,可以采取混合压缩策略。比如D-gap使用Golomb压缩,tf使用Gamma压缩。
采用索引压缩能够带来很多好处,所以实用的搜索引擎都会采用索引压缩技术,但是对索引进行压缩也会带来问题,
那就是比不压缩需要更多的计算量。
- 浏览: 72117 次
- 性别:
- 来自: 北京
最新评论
-
thd52java:
0.5的。
Mahout系列之----kmeans 聚类 -
yeelor:
这是用的mahout的哪个版本呢
Mahout系列之----kmeans 聚类 -
hailongshih:
lz用哪个版本jar包,试过3.0.3 3.0.2都不行
实现像百度一样的自动补全功能 -
thd52java:
netkiller.github.com 写道开眼了,不过很多 ...
树的种类
相关推荐
随着技术的发展,倒排索引和索引压缩技术不断进步,出现了更多的压缩算法和数据结构,如Frame of Reference、Patched Frame of Reference、Roaring Bitmaps等。这些技术能够进一步减少索引所占空间,提高检索效率。 ...
这就需要有效的索引压缩机制来减少存储和传输的开销,同时还要保证副本定位的效率。 在此背景下,提出了一个基于大规模分布式副本定位的资源索引分级压缩机制。该机制的关键在于超级节点索引方式的应用。在这一方式...
sql学习 压缩技术2_索引压缩.sql
在ITAS的三项关键技术中,我们重点研究位图索引压缩算法,并在本文中进行了详细的调查。当前最新的位图索引编码方案包括:BBC,WAH,PLWAH,EWAH,PWAH,CONCISE,COMPAX,VLC,DF-WAH和VAL-WAH。基于分段,分块,...
3.4 索引压缩方法的效果 3.5 签名文件和位图 签名文件 位片签名文件(Bitsliced signature files) 签名文件分析 位图 签名文件和位图的压缩 3.6 索引方法的比较 3.7 大小写折叠、词根化和停用词 大小写折叠 词根化 ...
在本项目中,`SPIMI`算法被用来构建倒排索引,同时采用了`Gamma`编码进行数据压缩,以节省存储空间。 首先,让我们详细了解一下`SPIMI`算法。`SPIMI`的核心思想是在倒排列表中引入顺序Posting List,即将同一文档中...
本文介绍的SPLWAH方案,是一种针对档案互联网流量进行搜索的位图索引压缩方案,其核心思想在于通过优化位图索引压缩技术来提高查询效率并减少存储空间的需求。 首先,位图索引技术是档案互联网流量分析中常用的一种...
位图索引压缩中的设计空间仍然是一个富有成果的未知前沿,值得探索。 我们在 FastBit 中引入 PLWAH(位置列表字对齐混合)编码作为测试我们新设计的名为 SECOMPAX 和许多其他位图索引压缩方案的基准。 SECOMPAX ...
面对图数据管理中查询耗时高和空间占比大的难题,提出一种图数据二 级索引压缩算法——GComIdx。该算法利用有序的键值(Key-Value)结构将相关节点和边尽可能地以相邻的方式 存储,并为高效的属性查询和邻居查询分别...
深入搜索引擎--海量信息的压缩、索引和查询中文版(5/6).zip.005深入搜索引擎--海量信息的压缩、索引和查询中文版(5/6).zip.005
- **索引压缩**: 索引压缩可以有效减少存储空间的占用,但在某些操作上可能会增加CPU开销。 综上所述,正确创建和维护索引是Oracle数据库性能调优的重要组成部分。通过遵循上述基本原则,可以根据具体的应用场景...
3. **索引压缩**:为了减少存储空间和提升加载速度,可以对倒排索引进行压缩。常见的压缩技术包括位图压缩、差分编码等,它们能够在保持索引可用性的前提下,大幅减小索引的物理大小。 ### 实现细节 在具体的实现...