《海量信息处理-索引.ppt》由会员分享，可在线阅读，更多相关《海量信息处理-索引.ppt（32页珍藏版）》请在三一办公上搜索。
1、海量信息处理索引,彭卫华,1,ICRC学术讲座第2期,内容,一、索引介绍二、索引构造三、Q&A四、部分参考文献,2,索引介绍,1.为什么使用索引2.索引什么3.索引机制4.索引压缩,3,为什么使用索引,什么是索引？索引是一种找出给定术语在文本中位置的机制。使用原因？信息如何组织才能方便高效地查询数据相关部分如何才能快速地抽取？若文档是图片被索引的词汇可能是图片的若干描述词,4,索引什么,使用文档中出现的每个单词？利：有利于扩大术语集合的词汇量（出现的不重复术语的数量）增加了索引中文档识别符的数量弊：影响系统的存储空间分解查询请求时，更多潜在的查询术语将会被分解出来，恶化了查询结果,5,索引什么
2、(cont.),（针对英文）1.大小写折叠(case folding)ACT actact act问题？,6,索引什么(cont.),（针对英文）2.词根化(stemming)compression compresscompressed compress问题？,7,索引什么(cont.),3.去除停用词(stop word)问题？同形异义,8,索引机制,1.倒排文件(inverted file)2.签名文件(signature file)3.位图(bitmap),9,倒排文件,倒排索引包含字典中的每个术语倒排列表(也叫记录列表，posting list)中存储了一列指针(也叫“记录”,post
3、ing)，每个指针都表示了术语在文本中的全部出现对于每个指针来说，它存放的值其实就是术语出现的文档号,10,倒排文件(cont.),索引粒度：表示标识术语精确度的一个概念 粗粒度索引：标识一个文本组(block of text)中等粒度索引：存储文档号的位置 细粒度索引：标识句子或者单词的序号,11,倒排文件(cont.),一般选择文档粒度，式样：使用粗粒度索引，在多术语查询的场合下更可能造成错配；另一个极端，单词级索引增加存储空间。单词级索引式样：,12,签名文件,签名文件是一种面向索引文本的概率方法。每个文档都有一个关联签名(associated signature)，或称为描述符(des
4、criptor)。为了创建文档的描述符，首先每个文档中的术语都需要被用来生成多个哈希值，然后将术语哈希值置1的比特位也为相应的文档签名的比特位置1即可。,13,签名文件(cont.),检测一个查询术语是否在给定的文档中出现，需要计算该术语的各个哈希值。如果所对应的比特位在某个文档描述符中置位，则该术语可能出现在这个文档中。弊端：错配检查！签名文件索引只能排除文档，永远不能确定地选出文档。,14,位图,位图是十分简单的索引结构，字典中的每个术语都需要存储成比特向量的形式，每比特位对应一个文档。位图不仅快，而且易于使用，但是极其耗费存储空间。（从TREC数据库看，一个位图索引比索引的文本本身还要大
5、20倍）,15,索引压缩,主要针对倒排文件索引,16,索引构造,1.什么是索引构造2.索引构造方法3.动态文档集合,17,什么是索引构造,(针对倒排文件索引)索引构造的过程即通常所说的文本倒排(inversion)。一种显而见的创建倒排索引的方法是在内存中创建一个转置的频率矩阵。,18,索引构造方法,链接列表（基于内存）链接列表（基于磁盘）基于排序基于排序且压缩基于排序且多路归并基于排序且多路原地归并内存内压缩基于字典，无额外磁盘消耗基于字典，需要额外磁盘空间基于文本的切分,19,链接列表（基于内存）,20,链接列表（基于内存）(cont.),21,链接列表（基于内存）(cont.),链接表方
6、法并不适合于GB级别以上的文档集合。它要么需要大量的内存，要么需要大量的时间开销。,22,基于排序,23,基于排序(cont.),24,基于排序(cont.),必须使用两个临时文件。为什么？需要巨大的磁盘空间,25,基于排序且多路归并,使用R路归并，共需要ceil(logR num_of_sortedrun)趟归并 需要借助类似于Heap数据结构的优先队列,26,基于排序且多路原地归并,27,基于排序且多路原地归并(cont.),(a)归并段创建后(b)归并后(c)重排后(d)缩减后,28,动态文档集合,一个动态集合可以有两种状态：插入操作和编辑操作插入操作允许在现有的文档集合后追加新的文档，
7、但不修改目前已有的任何文档。编辑操作允许变更现有文档，并且有可能将其删除。,29,动态文档集合(cont.),文本扩展 简单的“追加”操作 改进？索引扩展 将累积的更新存放在“号外”(stop-press)。当“号外”变得太大或其它类似情况，重建？块结构。自由空间,30,Q&A,？,31,部分参考文献,1 Ian H.Witten,Alistair Moffat,Timothy C.Bell.深入搜索引擎海量信息的压缩、索引和查询M.电子工业出版社,2009.2 李晓明.搜索引擎:原理、技术与系统M.科学出版社,2004.3 刘挺,秦兵,张宇,车万翔.信息检索系统导论M.机械工业出版社,2008.4 Bruce Croft,Donald metzler,Trevor Strohman.Search Engines:Information Retrieval in PracticeM.机械工业出版社,2009.,32,
