该系列文章是《An Introduce to
Information Retrieval》Chapter 4 的读书笔记。
对于大规模数据的信息检索,倒排索引的建立其实并没有想象中的那么简单。在实际应用中,倒排索引的建立算法必须考虑到硬件的约束。可以这样说:计算机硬件的参数性能是促动IR系统的设计发展的决定因素。
索引创建(Index construction)
要点:(1) 介绍 BSBI 算法建立大规模数据的倒排索引
(2) 分布式索引的建立算法
4.1 硬件基础介绍
下图是2007年典型计算机的系能参数:
参数符号 性能指标 统计值
s 磁盘数据定位时间 5ms=5*10^(-3)s
(在磁盘中查找数据所在的位置)
b 每字节数据传输时间 0.02us=2*10^(-8)s
(从磁盘传入1字节数据进内存)
CPU时钟周期 10^(-9)s
p 内存大小 several GB
磁盘大小 1TB or more
(1) 内存中读取数据远比磁盘中读取数据要快的多。
从内存中读取1byte数据只需要几个CPU时钟周期(大概5*10^(-9)s),而从磁盘中读入1byte数据需要2*10^(-8)s。因此,我们要尽可能的让更多的数据保存在内存中,特别是使用频率高的数据。
将使用频率高的磁盘数据保存在内存中的技术叫做
缓存(caching)。
(2) 磁盘数据读取的代价主要花费在磁盘数据定位的时间上(5*10^(-3)s)。而磁盘每次定位到一个磁盘存储块(详见《外部存储器——磁盘
》)。定位1byte数据和定位一个磁盘存储块(可能是8,16,32或64KB)的时间是一样。因此,需要一起读取的数据块应该连续存储在磁盘上。这样,我们把一整块磁盘存储块数据读入内存中的连续空间叫做缓冲区(buffer)。
举个例子:假设我们要读入磁盘中的10M数据,这些数据连续存储在100个磁盘存储块中。那么所花费的时间代价:
从磁盘中读入内存中的时间: t1=10^(7)*2*10^*(-8)=0.2s
在磁盘中定位数据的时间: t2=100*(5*10^(-3))=0.5s
总代价为: t=t1+t2=0.7s
当然,如果10M数据分散存储在1W个存储块中(而且这些存储块分散在杂乱无章的磁道和柱面上),那么可能要多付出几个数量级的t2代价。
(3) 现代服务器的内存大小少则几个GB,多则几十个GB。磁盘要多几个数量级。
4.2 基本倒排索引建立算法
这里先回忆一下《布尔检索模型》
中基本的倒排索引建立算法:
(1) 将所有文档解析成Term-DocID pair的集合。
(2) 把所有pairs存储在内存中,并根据Term关键字排序。
(3) 将Term相同, DocID不同的pair合并成一个Term - posting list 结构。其中posting就是一个DocID。并计算Term frequence(Term在单篇文档中出现次数) 和 Document frequence(一共出现Term的文档数)。
假如我们有1GB的文档集合(80W篇)、大概1亿词元(token)、40万词语(term),因此Token-DocID有1亿个,而词语是规范化,词干化的词元。因此term-DocID最多也有1亿个。每个Term平均7.5bytes,每个DocID需要4bytes。全部Term-DocID存储共需要1.15G大小。
如果内存没有1.15G,那么把这些pairs全部加入内存进行排序是不现实的。我们看看下面的BSBI和SPIMI算法。
4
.3 块排序索引算法 (Blocked sort-based indexing)
BSBI算法首先把每一个term对应一个唯一的TermID,这样每对TermID-DocID平均需要4bytes,共0.8G。这样所有的pairs就被压缩了近0.35G。
BSBI算法伪代码:
BSBI()
n ←0
while(all documents have not been processed)
do n←n+1
block←PARSENEXTBLOCK()
BSBI-INVERT(block)
WRITEBLOCKTODISK(block,fn)
MERGEBLOCKS(f1,...,fn;f merged)
核心思想:假设内存所能容纳的pairs大小为一个block。(这个大小允许pairs在内存中进行快排)
(1) 把Document集合中的文档一篇一篇的解析成TermID- DocID pairs,并保存在内存中。直到这些pairs存满了一个blocked的大小。(上述算法第5行PARSENEXTBlOCK())
(2) 对内存block中的所有pairs进行排序,并整理成Term - posting list结构(倒排索引结构)。(上述算法第6行INVERT(block))
(3) 把内存中建立好的block大小的索引结构存储在磁盘中间文件 fn 中(每一个block的中间文件不同)。然后清空内存,循环执行第一步继续解析剩下的文档,直到文档集合中所有文档被解析完毕为止。
(4) 合并中间文件f1 .... fn ,形成最后的倒排索引文件f
其实BSBI算法的核心思想类似于外部排序算法。
4.4 分布式索引的建立 (Distributed indexing)
对于World Wide Web的海量数据,我们不可能用一台计算机高效的建立索引。事实上,我们需要一大群计算机(large computer clusters)来一起建立具有任何可能大小的Web索引。现代的Web搜索引擎,在建立索引的阶段都使用了分布式索引算法(distributed indexing algorithms)。
整个索引的建立被分配由若干台计算机来完成。既有根据词语(term)来划分的,也有根据文档(document)来划分的。下面我们将介绍根据term来划分的分布式索引算法。其实绝大多数Web搜索引擎都是根据document划分的,其基本原理和根据term划分类似。
分布式索引算法使用了一种分布式计算中很普遍的计算模型:MapReduce
。这种模型用于大规模数据集(大于1TB)的并行运算。其基本思想就是把巨大的计算工作量(computing job)分成若干块(chunks),这些块能够被普通计算机在短时间内处理。
MapReduce模型有两个基本阶段:Map(映射)和
Reduce(化简)
。下图是基于MapReduce模型的分布式索引建立的示例图:
基于MapReduce模型的根据词语划分的分布式索引算法:
(1) 将输入数据(web page collection) 分成n个splits。也就是将大工作量划分成若干个小工作量。
每个splits的大小要尽可能确保工作能够被平均且高效的分配。这些splits并没有预先制定由哪台计算机完成,而是由主机依照一定的原则进行分配: 如果一台计算机完成了splits的处理任务,那么它将得到主机分配给它的下一个splits。如果该计算机死机或者由硬件故障变的很慢。那么主机会把在这台计算机上正在运行的split重新分配给其他计算机。
(2) 如上图MapReduce的映射阶段(Map):把每个要完成的splits映射成Term - DocID pairs。
这一过程由parser完成。一个parser可以看做一台执行文档解析的计算机。每一个parser都会把解析好的pairs写入本地的中间文件中。而这些中间文件都是根据词语划分好的 segment files(如上图a-f,g-p,q-z 三类)。
(3) 如上图MapReduce的化简阶段(Reduce): 把每一类segment files中间文件丢给不同的inverter建立索引。
每个inverter也可以看成是一台计算机。不同的inverter可能建立不同词语类的索引。比如上图,第一个inverter专门对所有parser计算机的本地segment files中a-z类的term建立索引。事实上,要考虑到inverter的工作量,所以每次建立索引的任务都限制在r个segment files。
4.5 动态索引的建立
(Dynamic indexing)
到目前位置,BSBI索引算法和分布式索引算法所考虑的文档集合都是静态的。也就是一开始工作量的大小都是确定的。但实际上,Web搜索引擎所面临的web page集合是随着文档的增加,删除,修改而不停的变化的。
如果文档集合的变化频率很小而且对新变化的查询实时性要求很低,那么完全可以采用一种很简单的方法:每隔一段时间重新建立索引。
但如果新文档的获取速度很快,比如Web search,怎么办呢?
我们可以考虑这种解决方法:维持两个索引。一是大规模的主索引(main index)
,另外一个就是刚刚发生新加入文档的辅助索引(auxiliary index)
。辅助索引的大小可以限制,并存放在内存中,如果一旦辅助索引的大小操作了限制,就立刻和主索引合并存储在磁盘上。搜索的时候可以同时查找两个索引并返回合并后的结果。
插入操作:对新文档所解析的pairs全部加入到内存中的辅助索引中。
删除操作:对已经删除的文档标记在一个类似垃圾站的位向量中,在检索结果返回之前首先过滤掉这些垃圾站中的文件。
更新操作:删除操作+插入操作。
分享到:
相关推荐
教材introduce to java programming 9th英文版,pdf,欢迎下载
Introduce to Algorithms, A Creative Approach .英文版
introduce to linux.html
目前为止找到的最详细的NS2说明文档 比官网的ns manual 还要详细
包括 Introduce to Java Programming 8th的全部课后习题答案(偶数以及奇数习题),还包括课本讲述过程中的习题。欢迎下载。
龙书 9~15章 的代码,"" 需加 L"", d3dutility.cpp 文件中需加 winmm.lib
IR Remote Control introduce and protocol
LINUX INTRODUCE
team introduce.key
EIB的控制网络及协议介绍,通过此文档可以理解EIB控制网络及布局,理解EIB协议设计的基本知识
线性优化讲义 introduction to linear optimization ,
这是对设计模式的简单简绍,希望对大家有用
Introduction to Lens Design
中文翻译Introduction to Linear Algebra, 5th Edition 5.2节(仅供交流学习)
computer book
This book is meant to be an overview of the Tornado web server, and will walk readers through the basics of the framework, some sample applications, and best practices for use in the real world....
最详细的 MIT 线性代数 公开课笔记 结合 MIT线性代数+《Introduce to linear algebra》书籍的详细中文翻译
Gilbert Strang's textbooks have changed the entire approach to learning linear algebra -- away from abstract vector spaces to specific examples of the four fundamental subspaces: the column space and ...
Fuel_Gauge_introduce
SST_MCU_Introduce选型!!!!!!!!!!