MG--索引-阿里云开发者社区

开发者社区> 人工智能> 正文

MG--索引

简介:

在这个信息爆炸的年代, 信息索引的重要性不言而喻。现在主要的索引结构就是倒排索引,又称为记录文件(posting file),词汇索引(concordance)。其他的还有签名文件(signature file), 和 位图(bitmap)。

倒排索引 
倒排索引在结构上分为,倒排列表(inverted list)和字典, 倒排列表就是记录一列指针, 每个指针表示了术语所在的文档的编号,甚至是在文档中的位置。
而字典就是记录了术语和倒排列表的对应关系。
举个例子,cold (2;1,4)表示cold这个词出现了2次,分别在第1和第4号文档里面。
那么索引有个粒度的问题,上面的例子的索引的粒度是文档级的, 也可以把索引的粒度细化到单词级的.
那么索引列表就是这个形式,cold(2;(1;6,7,10),(4;8)), 这边可以看出单词级索引要比文档级索引占的空间要大的多.
那么无论什么粒度的倒排索引,还是要占比较大的空间的,索引本身能不能压缩了?
看这样一个倒排索引(8;3,5,20,21,23,76,77,78),倒排序列以升序序列存放,这个是压缩的关键。
那么我们可以通过存储第一个文档号,和文档间的gap来实现压缩。那么上面的倒排索引被压缩成,
(8;3,2,15,1,2,53,1,1), 其实单纯的用gap替换文档号并不能实现压缩,因为对于N个文档的文档集,仍需要logN位去编码。
但对于文档号序列,每个文档号只会出现一次, 而对于gap的序列,会出现高概率的gap,和低概率的gap。
所以对于文档号序列我们必须用logN来表示每个文档号,而对于gap序列就可以对高概率的gap用较短的位,对低概率的gap用较长的位来表示,从而实现了压缩。
那么这可以说是个符号方法的压缩问题,所以这个问题的核心就是文档间隔大小的概率分布模型 及相应的编码方法 的问题。

对于一个有N个文档的文档集,那么gap可能值应该也是N个,如果每个gap平均出现, 即每个gap出现的概率是Pr[x]= 1/N , 根据香农公式理想的编码长度位-logPr[x], 那么编码长度为-log(1/N)= logN, 这个就是不压缩的情况,二进制编码 。

那么事实情况,gap不可能是平均概率出现, 往往比较小的gap出现的频率会比较高, 这个是比较直观的,那么我们就可以采用一种重视小值的概率模型,

Pr[x]=2(-x) , 即假设gap出现的概率随着gap的变大成指数级衰减。
那么理想的编码长度就是-log2(-x) = x
对于这样的概率模型的编码方法就是简单的一元编码 ,把x>=1的整数,编码为x-1个1比特连接一个0比特。如3, 编为110,4就是,1110
这个编码还是比较简单易懂的, 他的缺点就是随着gap的变大,概率可能衰减的太快了。
那么假设Pr[x]=1/2x2 , 即假设gap出现的概率随着gap的变大成平方级衰减。
那么理想的编码长度就是1+ 2logx
对于这样的概率模型的编码方法就是r编码 , 首先对1+logx进行一元编码,然后用logx比特长度对x-2logx进行二进制编码,然后将两部分编码拼接。 如9的编码为1110 001

上面这些概率模型都是主观假设的,如果能根据实际的情况来建立概率模型,也许会有更好的压缩效果。
那就来看看全局贝努里模型 
N为文档数, n为对立索引词数,那么如果每个索引词在每个文档里都出现的话,倒排文件中的指针数应该是N×n,这个就是指针数的上限。
f为倒排文件中指针数的实际值,那么f/N*n表示指针的真实密度,即可以认为是随机的一个索引词在随即的文档中出现的概率,这里假定每个单词均匀分布在每个文档里。(显然这个假定是不合理的) 
那么假设文档中出现一个词概率p
Pr[x]= (1-p)x-1 p , 间隔为x表示前x-1个文档都没有出现这个词,第x个文档出现了
那么现在这个x的概率模型就是建立在p这个客观的参数上,称为’几何分布 ‘。
那么这个概率模型怎么编码了, 当然可以用算术编码, 但是南加州大学的solomon golomb提出了golomb编码 ,可以有效的以哈夫曼编码替代算术编码。
这个编码比较复杂,门外汉不明白这个怎么能想出来的,不过和上面的r编码思路比较象。
即对于任意的参数b,x可以分为两部分,q=(x-1)/b, r = x -qb -1, 那么对q+1进行一元编码,对r进行logb长度的哈夫曼编码。
如取b=6,对9进行编码,q=1,r=2
q的一元编码为10
b=6,所以r的值域为[0,5]6个数, 对这6个数进行前缀编码(可以看成哈夫曼编码)为00,01,100,101,110,111
所以r的编码为100
整个编码为10100
至于这个b值怎么选有个公式可以取算的,就不详细说了,因为不知其所以然。总之是p越大就是指针密度越大,那么b就越小。
从某种意义上来讲,golomb的构造方法是计算特定无限概率集合的哈夫曼编码的单步法(one-step method)
我的理解是哈夫曼树的构造必须是正对一个有限的概率集合, 对于一个无限的集合就没办法构建哈夫曼树。
因为这边我们要压缩文档间隔的是一个数字,除以一个参数b,得到的余数r一定是个有限集合,所以可以采用哈夫曼编码。

那么上面谈到的都是全局的概率模型,全局贝努里模型也仅仅比其他全局模型稍好一些。
贝努里模型的压缩效果和b的选取有很大关系,因为b越大哈夫曼编码需要的位数就越多,对于全局贝努里模型,b是由全局索引词的指针密度p算出的。这样是基于一个假设,就是每个索引词的指针密度是平均的,都差不多的。
但是实际情况往往不是这样的,会有高频词,低频词,这样拿这个全局的b去进行编码就效果比较差。
那么为了改善这一情况, 就有了局部贝努里模型 ,
很简单就是根据每个索引词实际的指针密度来计算局部的b值,那么这样就可以高词频的用较小b值编码,低词频用较大的b值编码,相对比较合理了。
在TREC文档集合中,对于‘hapax legomena’仅出现一次,那么就用b=50000编码,长度是20bit左右。对于在10%的文档中都出现的常用词,用b=7进行编码,那么文档间隔1,只需要3bit编码。
那么如果采用之前的全局贝努里模型的话,全局最优b=2036, 那么文档间隔1也要11bit去编码。
由于对于不同的索引词要用不同的b值,所以要额外的为每个索引词去存储指针密度f,用来算出b,不过这个开销很小。
对于局部贝努里模型,没有考虑到词的成簇性cluster,所以又有‘有偏贝努里模型’,就不具体讲了。

倒排索引基本差不多了,在大概了解一下签名文件(signature file), 和 位图(bitmap)两种索引方法,这两种方法基本已经属于被淘汰的技术。
签名文件 
顾名思义,就是文档的一个签名(signature), 或称为‘描述符’(discriptor). 其实就是一个比特串,从某种程度上表示了文档的内容。
这个签名怎么生成了, 举个例子,
要为文档建立一个16bit的签名,那么首先为文档中的每个索引词建立个16bit的签名。
索引词的16bit的签名很容易建,找3个不同的hash函数在1~16中算出3个hash值,然后把16bit中这3个hash值的位置置1(这儿有可能会冲突,不同的hash函数算出同样的值)
然后把所有索引词的16bit的签名求’或‘,就得到整个文档的签名。这个签名索引必须足够的长,才能有比较好的效果。
这种索引其实只能查出某个索引词是不是不在该文档中出现,而没办法确定一个词一定出现在一个文档中, 需要做错配的检查, 这个效率就低了。
位片(bitslicing)签名文件 
这个其实很容易理解,如果你时按文档签名来存储这个签名文件, 比如你要查哪些文档中包含cold这个词,你必须读出所有的文档的签名文件,一个一个去判断。
这样你要从磁盘上读出所有文档签名索引,比较低效。
那么换个思路,我们想象着上面那个文档签名的签名文件是个矩阵,每行代表了这个文档的签名,一般的就是这么一行行的读出所有索引。
我们现在按这个列去存储,一列就是一个位片,代表了所有文件在这个bit上的情况,按位片去存储的好处是什么了?
比如cold这个词hash得到1,11,14这3个hash值,那么要找那些文档里包含cold这个词,我们只需要读出1,11,14这3个位片数据进行合取,就可以知道那些文档可能包含cold。
这样就不用读出所有的索引文件, 比较高效的方法。

位图 

这是个十分简单的索引结构,就是为字典中每个索引词建个和文档总数等长bit串,索引词出现在这个文档中, 那该文档的bit位置1,否则置0。可想而知,这个索引非常耗空间的。


本文章摘自博客园,原文发布日期:2011-07-04

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章