海量信息处理-索引.ppt

《海量信息处理-索引.ppt》由会员分享，可在线阅读，更多相关《海量信息处理-索引.ppt（32页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

2、符的数量弊：弊：影响系统的存储空间分解查询请求时，更多潜在的查询术语将会被分解出来，恶化了查询结果5索引什么索引什么(cont.)(cont.)（针对英文）1.大小写折叠(case folding)ACT actact act问题？6索引什么索引什么(cont.)(cont.)（针对英文）2.词根化(stemming)compression compresscompressed compress问题？7索引什么索引什么(cont.)(cont.)3.去除停用词(stop word)问题？同形异义8索引机制索引机制1.倒排文件(inverted file)2.签名文件(signature fil

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

4、成错配；另一个极端，单词级索引增加存储空间。单词级索引式样：term,12签名文件签名文件签名文件是一种面向索引文本的概率方法。每个文档都有一个关联签名(associated signature)，或称为描述符(descriptor)。为了创建文档的描述符，首先每个文档中的术语都需要被用来生成多个哈希值，然后将术语哈希值置1的比特位也为相应的文档签名的比特位置1即可。13签名文件签名文件(cont.)(cont.)检测一个查询术语是否在给定的文档中出现，需要计算该术语的各个哈希值。如果所对应的比特位在某个文档描述符中置位，则该术语可能出现在这个文档中。弊端：错配检查！签名文件索引只能排除文档，

5、永远不能确定地选出文档。14位图位图位图是十分简单的索引结构，字典中的每个术语都需要存储成比特向量的形式，每比特位对应一个文档。位图不仅快，而且易于使用，但是极其耗费存储空间。（从TREC数据库看，一个位图索引比索引的文本本身还要大20倍）15索引压缩索引压缩主要针对倒排文件索引16索引构造索引构造1.什么是索引构造2.索引构造方法3.动态文档集合17什么是索引构造什么是索引构造(针对倒排文件索引)索引构造的过程即通常所说的文本倒排(inversion)。一种显而见的创建倒排索引的方法是在内存中创建一个转置的频率矩阵。18索引构造方法索引构造方法链接列表（基于内存）链接列表（基于内存）链接列表

6、（基于磁盘）基于排序基于排序基于排序且压缩基于排序且多路归并基于排序且多路归并基于排序且多路原地归并基于排序且多路原地归并内存内压缩基于字典，无额外磁盘消耗基于字典，需要额外磁盘空间基于文本的切分19链接列表（基于内存）链接列表（基于内存）20链接列表（基于内存）链接列表（基于内存）(cont.)(cont.)21链接列表（基于内存）链接列表（基于内存）(cont.)(cont.)链接表方法并不适合于GB级别以上的文档集合。它要么需要大量的内存，要么需要大量的时间开销。22基于排序基于排序23基于排序基于排序(cont.)(cont.)24基于排序基于排序(cont.)(cont.)必须使用两

7、个临时文件。为什么？需要巨大的磁盘空间25基于排序且多路归并基于排序且多路归并 使用R路归并，共需要ceil(logR num_of_sortedrun)趟归并 需要借助类似于Heap数据结构的优先队列26基于排序且多路原地归并基于排序且多路原地归并27基于排序且多路原地归并基于排序且多路原地归并(cont.)(cont.)(a)归并段创建后 (b)归并后 (c)重排后 (d)缩减后28动态文档集合动态文档集合一个动态集合可以有两种状态：插入操作和编辑操作插入操作允许在现有的文档集合后追加新的文档，但不修改目前已有的任何文档。编辑操作允许变更现有文档，并且有可能将其删除。29动态文档集合动态文

8、档集合(cont.)(cont.)文本扩展文本扩展 简单的简单的“追加追加”操作操作 改进？改进？索引扩展索引扩展 将累积的更新存放在将累积的更新存放在“号外号外”(stop-press)(stop-press)。当。当“号外号外”变得太大或其变得太大或其它类似情况，重建？它类似情况，重建？块结构。自由空间块结构。自由空间30Q&AQ&A？31部分参考文献部分参考文献1 Ian H.Witten,Alistair Moffat,Timothy C.Bell.1 Ian H.Witten,Alistair Moffat,Timothy C.Bell.深入搜索深入搜索引擎引擎海量信息的压缩、索引和

9、查询海量信息的压缩、索引和查询M.M.电子工业出版社电子工业出版社,2009.2009.2 2 李晓明李晓明.搜索引擎搜索引擎:原理、技术与系统原理、技术与系统M.M.科学出版社科学出版社,2004.,2004.3 3 刘挺刘挺,秦兵秦兵,张宇张宇,车万翔车万翔.信息检索系统导论信息检索系统导论M.M.机械工业机械工业出版社出版社,2008.,2008.4 Bruce Croft,Donald metzler,Trevor Strohman.Search 4 Bruce Croft,Donald metzler,Trevor Strohman.Search Engines:Information Retrieval in PracticeM.Engines:Information Retrieval in PracticeM.机械工业机械工业出版社出版社,2009.,2009.32