lecture4-indexconstruction-信息检索导论-王斌-PPT-课件-第4章

IntroductiontoInformationRetrieval现代信息检索中科院研究生院2011年秋季课程《现代信息检索》更新时间：ModernInformationRetrieval授课人：王斌~wangbin*改编自”AnintroductiontoInformationretrieval”网上公开的课件，地址第4讲索引构建Indexconstruction12011/9/18提纲2❶上一讲回顾❷简介❸BSBI算法❹SPIMI算法❺分布式索引构建❻动态索引构建提纲3❶上一讲回顾❷简介❸BSBI算法❹SPIMI算法❺分布式索引构建❻动态索引构建现代信息检索上一讲内容词典的数据结构：哈希表vs.树结构容错式检索(Tolerantretrieval):通配查询：包含通配符*的查询轮排索引vs.k-gram索引拼写校正：编辑距离vs.k-gram相似度词独立校正法vs.上下文敏感校正法Soundex算法4现代信息检索5采用定长数组法存储词典5空间消耗:20字节4字节4字节现代信息检索支持词典查找的两种数据结构哈希表：定位速度快，常数时间不宜支持动态变化的词典不支持前缀查询树结构：二叉树、B-树等等定位速度为指数时间二叉(平衡)树支持动态变化，但是重排代价大。B-树能否缓解上述问题支持前缀查询6现代信息检索7基于B-树的词典查找7现代信息检索8基于轮排索引的通配查询处理8查询:对X,查找X$对X*,查找X*$对*X,查找X$*对*X*,查找X*对X*Y,查找Y$X*现代信息检索基于k-gram索引的通配查询处理比轮排索引空间开销要小枚举一个词项中所有连读的k个字符构成的k-gram。2-gram称为二元组(bigram)例子:fromAprilisthecruelestmonthwegetthebigrams:$aapprriill$$iiss$$tthhee$$ccrruueelleesstt$$mmoonnth$同前面一样，$是一个特殊字符构建一个倒排索引，此时词典部分是所有的2-gram，倒排记录表部分是包含某个2-gram的所有词项相当于对词项再构建一个倒排索引(二级索引)9现代信息检索10Levenshtein距离计算10现代信息检索基于编辑距离的拼写校正给定查询词，穷举词汇表中和该查询的编辑距离(或带权重的编辑聚类)低于某个预定值的所有单词求上述结果和给定的某个“正确”词表之间的交集将交集结果推荐给用户代价很大，实际当中往往通过启发式策略提高查找效率(如：保证两者之间具有较长公共子串)11现代信息检索12基于k-gram索引的拼写校正：bordroom12现代信息检索13本讲内容两种索引构建算法:BSBI(简单)和SPIMI(更符合实际情况)分布式索引构建:MapReduce动态索引构建:如何随着文档集变化更新索引13提纲14❶上一讲回顾❷简介❸BSBI算法❹SPIMI算法❺分布式索引构建❻动态索引构建现代信息检索15硬件基础知识信息检索系统中的很多设计上的决策取决于硬件限制首先简单介绍本课程中需要用到的硬件知识15现代信息检索16硬件基础知识在内存中访问数据会比从硬盘访问数据快很多(大概10倍左右的差距)硬盘寻道时间是闲置时间：磁头在定位时不发生数据传输为优化从磁盘到内存的传送时间，一个大(连续)块的传输会比多个小块(非连续)的传输速度快硬盘I/O是基于块的:读写时是整块进行的。块大小：8KB到256KB不等IR系统的服务器的典型配置是几个GB的内存，有时内存可能达到几十GB，数百G或者上T的硬盘。容错处理的代价非常昂贵：采用多台普通机器会比一台提供容错的机器的价格更便宜16现代信息检索17一些统计数据(ca.2008)17符号含义值sbP平均寻道时间每个字节的传输时间处理器时钟频率底层操作时间(e.g.,如word的比较和交换)内存大小磁盘大小5ms=5×10−3s0.02μs=2×10−8s109s−10.01μs=10−8s几GB1TB或更多现代信息检索18ReutersRCV1语料库《莎士比亚全集》规模较小，用来构建索引不能说明问题本讲使用ReutersRCV1文档集来介绍可扩展的索引构建技术路透社1995到1996年一年的英语新闻报道18现代信息检索19一篇ReutersRCV1文档的样例19现代信息检索20ReutersRCV1语料库的统计信息课堂练习:(1)一个词项的平均出现次数是多少？即一个词项平均对应几个词条？(2)每个词条字节数为4.5vs.每个词项平均字节数7.5，为什么有这样的区别？(3)带位置信息索引的倒排记录数目是多少？20NLMT文档数目每篇文档的词条数目词项数目(=词类数目)每个词条的字节数(含空格和标点)每个词条的字节数(不含空格和标点)每个词项的字节数无位置信息索引中的倒排记录数目800,000200400,00064.57.5100,000,000提纲21❶上一讲回顾❷简介❸BSBI算法❹SPIMI算法❺分布式索引构建❻动态索引构建现代信息检索22目标:构建倒排索引22词典倒排记录表现代信息检索23第一讲中介绍的索引构建:在内存中对倒排记录表进行排序(基于排序的索引构建方法)23现代信息检索24基于排序的索引构建方法在构建索引时，每次分析一篇文档对于每个词项而言，其倒排记录表不到最后一篇文档都是不完整的。那么能否在最后排序之前将前面产生的倒排记录表全部放在内存中？答案显然是否定的，特别是对大规模的文档集来说如果每条倒排记录占10–12个字节，那么对于大规模语料，需要更大的存储空间以RCV1为例，T=100,000,000，这些倒排记录表倒是可以放在2010年的一台典型配置的计算机的内存中但是这种基于内存的索引构建方法显然无法扩展到大规模文档集上因此，需要在磁盘上存储中间结果24现代信息检索25是否在磁盘上采用同样的算法？能否使用前面同样的算法，但是是在磁盘而不是内存中完成排序?不可能，这是因为对T=100,000,000条记录在磁盘上进行那个排序需要太多的磁盘寻道过程.需要一个外部排序算法25现代信息检索26外部排序算法中磁盘寻道次数很少需要对T=100,000,000条无位置信息的倒排记录进行排序每条倒排记录需要12字节(4+4+4:termID,docID,df)定义一个能够包含10,000,000条上述倒排记录的数据块这个数据块很容易放入内存中(12*10M=120M)对于RCV1有10个数据块算法的基本思路:对每个块:(i)倒排记录累积到10,000,000条,(ii)在内存中排序,(iii)写回磁盘最后将所有的块合并成一个大的有序的倒排索引26现代信息检索27两个块的合并过程27现代信息检索28基于块的排序索引构建算法BSBI（BlockedSort-BasedIndexing）该算法中有一个关键决策就是确定块的大小28提纲29❶上一讲回顾❷简介❸BSBI算法❹SPIMI算法❺分布式索引构建❻动态索引构建现代信息检索30基于排序的索引构建算法的问题假定词典可以在内存中放下通常需要一部词典(动态增长)来将term映射成termID实际上，倒排记录表可以直接采用term,docID方式而不是termID,docID方式......但是此时中间文件将会变得很大30现代信息检索31内存式单遍扫描索引构建算法ＳＰＩＭＩSingle-passin-memoryindexing关键思想1:对每个块都产生一个独立的词典–不需要在块之间进行term-termID的映射关键思想2:对倒排记录表不排序，按照他们出现的先后顺序排列基础上述思想可以对每个块生成一个完整的倒排索引这些独立的索引最后合并一个大索引31现代信息检索32SPIMI-Invert算法32现代信息检索33SPIMI:压缩如果使用压缩，SPIMI将更加高效词项的压缩倒排记录表的压缩参见下一讲33现代信息检索34课堂练习:计算1台机器下采用BSBI方法对Google级规模数据构建索引的时间34提纲35❶上一讲回顾❷简介❸BSBI算法❹SPIMI算法❺分布式索引构建❻动态索引构建现代信息检索36分布式索引构建对于Web数据级别的数据建立索引(don’ttrythisathome!):必须使用分布式计算机集群单台机器都是有可能出现故障的可能突然慢下来或者失效，不可事先预知如何使用一批机器?36现代信息检索37Google数据中心(2007estimates;Gartner)Google数据中心主要都是普通机器数据中心均采用分布式架构，在世界各地分布100万台服务器，300个处理器/核Google每15分钟装入100,000个服务器.每年的支出大概是每年2-2.5亿美元这可能是世界上计算能力的10%!在一个1000个节点组成的无容错系统中，每个节点的正常运行概率为99.9%，那么整个系统的正常运行概率是多少？答案:63%假定一台服务器3年后会失效，那么对于100万台服务器，机器失效的平均间隔大概是多少？答案:不到2分钟37现代信息检索38分布式索引构建维持一台主机(Master)来指挥索引构建任务-这台主机被认为是安全的将索引划分成多组并行任务主机将把每个任务分配给某个缓冲池中的空闲机器来执行38现代信息检索39并行任务两类并行任务分配给两类机器：分析器(Parser)倒排器(Inverter)将输入的文档集分片(split)(对应于BSBI/SPIMI算法中的块)每个数据片都是一个文档子集39现代信息检索40分析器（Parser）主节点将一个数据片分配给一台空闲的分析器分析器一次读一篇文档然后输出(term,docID)-对分析器将这些对又分成j个词项分区每个分区按照词项首字母进行划分E.g.,a-f,g-p,q-z(这里j=3)40现代信息检索41倒排器(Inverter)倒排器收集对应某一term分区(e.g.,a-f分区)所有的(term,docID)对(即倒排记录表)排序并写进倒排记录表41现代信息检索42数据流42现代信息检索43MapReduce刚才介绍的索引构建过程实际上是MapReduce的一个实例MapReduce是一个鲁棒的简单分布式计算框架......不一定需要在分布式处理的部分编写代码Google索引构建系统(ca.2002)由多个步骤组成，每个步骤都采用MapReduce实现索引构建只是一个步骤另一个步骤：将按词项分割索引转换成按文档分割的索引43现代信息检索44基于MapReduce的索引构建44现代信息检索45课堂练习主节点机传给分析器的任务描述包含什么信息？任务完成后，分析器给主节点机的回传报告中会包含哪些信息？主节点机传给倒排器的任务描述包含什么信息？任务完成后，倒排器给主节点机的回传报告中会包含哪些信息？45提纲46❶上一讲回顾❷简介❸BSBI算法❹SPIMI算法❺分布式索引构建❻动态索引构建现代信息检索47动态索引构建到目前为止，我们都假定文档集是静态的。实际中假设很少成立：文档会增加、删除和修改。这也意味着词典和倒排记录表必须要动态更新。47现代信息检索48动态索引构建:最简单的方法在磁盘上维护一个大的主索引(Mainindex)新文档放入内存中较小的辅助索引（Auxiliaryindex）中同时搜索两个索引，然后合并结果定期将辅助索引合并到主索引中删除的处理：采用无效位向量(Invalidationbit-vector)来表示删除的文档利用该维向量过滤返回的结果，以去掉已删除文档48现代信息检索49主辅索引合并中的问题合并过于频繁合并时如果正好在搜索，那么搜索的性能将很低实际上:如果每个倒排记录表都采用一个单