海量信息处理--索引

《海量信息处理--索引》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、海量信息处理—索引彭卫华2009.11.231ICRC学术讲座第2期内容一、索引介绍二、索引构造三、Q&A四、部分参考文献2索引介绍1.为什么使用索引2.索引什么3.索引机制4.索引压缩3为什么使用索引什么是索引？索引是一种找出给定术语在文本中位置的机制。使用原因？信息如何组织才能方便高效地查询数据相关部分如何才能快速地抽取？？？若文档是图片—被索引的词汇可能是图片的若干描述词4索引什么使用文档中出现的每个单词？利：有利于扩大术语集合的词汇量（出现的不重复术语的数量）增加了索引中文档识别符的数量弊：影响系

2、统的存储空间分解查询请求时，更多潜在的查询术语将会被分解出来，恶化了查询结果5索引什么(cont.)（针对英文）1.大小写折叠(casefolding)ACTactactact问题？6索引什么(cont.)（针对英文）2.词根化(stemming)compressioncompresscompressedcompress问题？7索引什么(cont.)3.去除停用词(stopword)问题？同形异义8索引机制1.倒排文件(invertedfile)2.签名文件(signaturefile)3.位图(

3、bitmap)9倒排文件倒排索引包含字典中的每个术语倒排列表(也叫记录列表，postinglist)中存储了一列指针(也叫“记录”,posting)，每个指针都表示了术语在文本中的全部出现对于每个指针来说，它存放的值其实就是术语出现的文档号10倒排文件(cont.)索引粒度：表示标识术语精确度的一个概念粗粒度索引：标识一个文本组(blockoftext)中等粒度索引：存储文档号的位置细粒度索引：标识句子或者单词的序号11倒排文件(cont.)一般选择文档粒度，式样：

4、cid1,docid2,…>>使用粗粒度索引，在多术语查询的场合下更可能造成错配；另一个极端，单词级索引增加存储空间。单词级索引式样：>12签名文件签名文件是一种面向索引文本的概率方法。每个文档都有一个关联签名(associatedsignature)，或称为描述符(descriptor)。为了创建文档的描述符，首先每个文档中的术语都需要被用来生成多个哈希值，然后将术语哈希值置1的比特位也为相

5、应的文档签名的比特位置1即可。13签名文件(cont.)检测一个查询术语是否在给定的文档中出现，需要计算该术语的各个哈希值。如果所对应的比特位在某个文档描述符中置位，则该术语可能出现在这个文档中。弊端：错配检查！签名文件索引只能排除文档，永远不能确定地选出文档。14位图位图是十分简单的索引结构，字典中的每个术语都需要存储成比特向量的形式，每比特位对应一个文档。位图不仅快，而且易于使用，但是极其耗费存储空间。（从TREC数据库看，一个位图索引比索引的文本本身还要大20倍）15索引压缩主要针对倒排文件索引16

6、索引构造1.什么是索引构造2.索引构造方法3.动态文档集合17什么是索引构造(针对倒排文件索引)索引构造的过程即通常所说的文本倒排(inversion)。一种显而见的创建倒排索引的方法是在内存中创建一个转置的频率矩阵。18索引构造方法链接列表（基于内存）链接列表（基于磁盘）基于排序基于排序且压缩基于排序且多路归并基于排序且多路原地归并内存内压缩基于字典，无额外磁盘消耗基于字典，需要额外磁盘空间基于文本的切分19链接列表（基于内存）20链接列表（基于内存）(cont.)21链接列表（基于内存）(cont.)

7、链接表方法并不适合于GB级别以上的文档集合。它要么需要大量的内存，要么需要大量的时间开销。22基于排序23基于排序(cont.)24基于排序(cont.)必须使用两个临时文件。为什么？需要巨大的磁盘空间25基于排序且多路归并使用R路归并，共需要ceil(logRnum_of_sortedrun)趟归并需要借助类似于Heap数据结构的优先队列26基于排序且多路原地归并27基于排序且多路原地归并(cont.)(a)归并段创建后(b)归并后(c)重排后(d)缩减后28动态文档集合一个动态集合可以有两种状态：插入

8、操作和编辑操作插入操作允许在现有的文档集合后追加新的文档，但不修改目前已有的任何文档。编辑操作允许变更现有文档，并且有可能将其删除。29动态文档集合(cont.)文本扩展简单的“追加”操作改进？索引扩展将累积的更新存放在“号外”(stop-press)。当“号外”变得太大或其它类似情况，重建？块结构。自由空间30Q&A？？？31部分参考文献[1]IanH.Witten,AlistairMoffat,TimothyC.Bell.