• /  32
  • 下载费用: 14.90积分  

海量信息处理--索引

'海量信息处理--索引'
ICRC学术讲座第2期 海量信息处理—索引 彭卫华 2009.11.23 1 内容一、索引介绍二、索引构造三、Q & A四、部分参考文献 2 索引介绍1. 为什么使用索引2. 索引什么3. 索引机制4. 索引压缩 3 为什么使用索引 什么是索引? Ø 索引是一种找出给定术语在文本中位置的机制。 使用原因? Ø 信息如何组织才能方便高效地查询 Ø 数据相关部分如何才能快速地抽取???若文档是图片—被索引的词汇可能是图片的若干描述词 4 索引什么使用文档中出现的每个单词?利:Ø有利于扩大术语集合的词汇量(出现的不重复术语的数量)Ø增加了索引中文档识别符的数量弊:Ø影响系统的存储空间Ø分解查询请求时,更多潜在的查询术语将会被分解出来,恶化了查询 结果 5 索引什么(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)中存储了一列指针(也叫 “记录”, posting),每个指针都表示了术语在文本中的全部出现Ø对于每个指针来说,它存放的值其实就是术语出现的文档号 10 倒排文件(cont.)索引粒度:表示标识术语精确度的一个概念Ø 粗粒度索引:标识一个文本组(block of text)Ø 中等粒度索引:存储文档号的位置Ø 细粒度索引:标识句子或者单词的序号 11 倒排文件(cont.)一般选择文档粒度,式样:<term, <num_of_doc; docid1,docid2,…>>使用粗粒度索引,在多术语查询的场合下更可能造成错配;另一个极端,单词级索引增加存储空间。单词级索引式样: <term,<num_of_doc;(docid1;pos_of_word1,pos_of_word2,…),…>> 12 签名文件 签名文件是一种面向索引文本的概率方法。每个文档都有一个关联签名(associated signature),或称为描述符(descriptor)。 为了创建文档的描述符,首先每个文档中的术语都需要被用来生成多个哈希值,然后将术语哈希值置1的比特位也为相应的文档签名的比特位置1即可。 13 签名文件(cont.) 检测一个查询术语是否在给定的文档中出现,需要计算该术语的各个哈希值。如果所对应的比特位在某个文档描述符中置位,则该术语可能出现在这个文档中。 弊端:错配检查! 签名文件索引只能排除文档,永远不能确定地选出文档。 14 位图 位图是十分简单的索引结构,字典中的每个术语都需要存储成比特向量的形式,每比特位对应一个文档。 位图不仅快,而且易于使用,但是极其耗费存储空间。(从TREC数据库看,一个位图索引比索引的文本本身还要大20倍) 15 索引压缩主要针对倒排文件索引 16 索引构造1. 什么是索引构造2. 索引构造方法3. 动态文档集合 17 什么是索引构造(针对倒排文件索引)索引构造的过程即通常所说的文本倒排(inversion)。一种显而见的创建倒排索引的方法是在内存中创建一个转置的频率矩阵。 18 索引构造方法Ø链接列表(基于内存)Ø链接列表(基于磁盘)Ø基于排序Ø基于排序且压缩Ø基于排序且多路归并Ø基于排序且多路原地归并Ø内存内压缩Ø基于字典,无额外磁盘消耗Ø基于字典,需要额外磁盘空间Ø基于文本的切分 19 链接列表(基于内存)20链接列表(基于内存)(cont.) 21 链接列表(基于内存)(cont.)链接表方法并不适合于GB级别以上的文档集合。它要么需要大量的内存,要么需要大量的时间开销。 22 基于排序23 基于排序(cont.)24 基于排序(cont.)Ø 必须使用两个临时文件。为什么?Ø 需要巨大的磁盘空间 25 基于排序且多路归并Ø 使用R路归并,共需要ceil(logR num_of_sortedrun)趟归并Ø 需要借助类似于Heap数据结构的优先队列 26 基于排序且多路原地归并27基于排序且多路原地归并(cont.) (a)归并段创建后 (b)归并后 (c)重排后 (d)缩减后 28 动态文档集合一个动态集合可以有两种状态:插入操作和编辑操作Ø插入操作允许在现有的文档集合后追加新的文档,但不修改目 前已有的任何文档。Ø编辑操作允许变更现有文档,并且有可能将其删除。 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 Practice[M]. 机械工业 出版社, 2009. 32ICRC学术讲座第2期 海量信息处理—索引 彭卫华 2009.11.23 1 内容一、索引介绍二、索引构造三、Q & A四、部分参考文献 2 索引介绍1. 为什么使用索引2. 索引什么3. 索引机制4. 索引压缩 3 为什么使用索引 什么是索引? Ø 索引是一种找出给定术语在文本中位置的机制。 使用原因? Ø 信息如何组织才能方便高效地查询 Ø 数据相关部分如何才能快速地抽取???若文档是图片—被索引的词汇可能是图片的若干描述词 4 索引什么使用文档中出现的每个单词?利:Ø有利于扩大术语集合的词汇量(出现的不重复术语的数量)Ø增加了索引中文档识别符的数量弊:Ø影响系统的存储空间Ø分解查询请求时,更多潜在的查询术语将会被分解出来,恶化了查询 结果 5 索引什么(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)中存储了一列指针(也叫 “记录”, posting),每个指针都表示了术语在文本中的全部出现Ø对于每个指针来说,它存放的值其实就是术语出现的文档号 10 倒排文件(cont.)索引粒度:表示标识术语精确度的一个概念Ø 粗粒度索引:标识一个文本组(block of text)Ø 中等粒度索引:存储文档号的位置Ø 细粒度索引:标识句子或者单词的序号 11 倒排文件(cont.)一般选择文档粒度,式样:<term, <num_of_doc; docid1,docid2,…>>使用粗粒度索引,在多术语查询的场合下更可能造成错配;另一个极端,单词级索引增加存储空间。单词级索引式样: <term,<num_of_doc;(docid1;pos_of_word1,pos_of_word2,…),…>> 12 签名文件 签名文件是一种面向索引文本的概率方法。每个文档都有一个关联签名(associated signature),或称为描述符(descriptor)。 为了创建文档的描述符,首先每个文档中的术语都需要被用来生成多个哈希值,然后将术语哈希值置1的比特位也为相应的文档签名的比特位置1即可。 13 签名文件(cont.) 检测一个查询术语是否在给定的文档中出现,需要计算该术语的各个哈希值。如果所对应的比特位在某个文档描述符中置位,则该术语可能出现在这个文档中。 弊端:错配检查! 签名文件索引只能排除文档,永远不能确定地选出文档。 14 位图 位图是十分简单的索引结构,字典中的每个术语都需要存储成比特向量的形式,每比特位对应一个文档。 位图不仅快,而且易于使用,但是极其耗费存储空间。(从TREC数据库看,一个位图索引比索引的文本本身还要大20倍) 15 索引压缩主要针对倒排文件索引 16 索引构造1. 什么是索引构造2. 索引构造方法3. 动态文档集合 17 什么是索引构造(针对倒排文件索引)索引构造的过程即通常所说的文本倒排(inversion)。一种显而见的创建倒排索引的方法是在内存中创建一个转置的频率矩阵。 18 索引构造方法Ø链接列表(基于内存)Ø链接列表(基于磁盘)Ø基于排序Ø基于排序且压缩Ø基于排序且多路归并Ø基于排序且多路原地归并Ø内存内压缩Ø基于字典,无额外磁盘消耗Ø基于字典,需要额外磁盘空间Ø基于文本的切分 19 链接列表(基于内存)20链接列表(基于内存)(cont.) 21 链接列表(基于内存)(cont.)链接表方法并不适合于GB级别以上的文档集合。它要么需要大量的内存,要么需要大量的时间开销。 22 基于排序23 基于排序(cont.)24 基于排序(cont.)Ø 必须使用两个临时文件。为什么?Ø 需要巨大的磁盘空间 25 基于排序且多路归并Ø 使用R路归并,共需要ceil(logR num_of_sortedrun)趟归并Ø 需要借助类似于Heap数据结构的优先队列 26 基于排序且多路原地归并27基于排序且多路原地归并(cont.) (a)归并段创建后 (b)归并后 (c)重排后 (d)缩减后 28 动态文档集合一个动态集合可以有两种状态:插入操作和编辑操作Ø插入操作允许在现有的文档集合后追加新的文档,但不修改目 前已有的任何文档。Ø编辑操作允许变更现有文档,并且有可能将其删除。 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 Practice[M]. 机械工业 出版社, 2009. 32ICRC学术讲座第2期 海量信息处理—索引 彭卫华 2009.11.23 1 内容一、索引介绍二、索引构造三、Q & A四、部分参考文献 2 索引介绍1. 为什么使用索引2. 索引什么3. 索引机制4. 索引压缩 3 为什么使用索引 什么是索引? Ø 索引是一种找出给定术语在文本中位置的机制。 使用原因? Ø 信息如何组织才能方便高效地查询 Ø 数据相关部分如何才能快速地抽取???若文档是图片—被索引的词汇可能是图片的若干描述词 4 索引什么使用文档中出现的每个单词?利:Ø有利于扩大术语集合的词汇量(出现的不重复术语的数量)Ø增加了索引中文档识别符的数量弊:Ø影响系统的存储空间Ø分解查询请求时,更多潜在的查询术语将会被分解出来,恶化了查询 结果 5 索引什么(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)中存储了一列指针(也叫 “记录”, posting),每个指针都表示了术语在文本中的全部出现Ø对于每个指针来说,它存放的值其实就是术语出现的文档号 10 倒排文件(cont.)索引粒度:表示标识术语精确度的一个概念Ø 粗粒度索引:标识一个文本组(block of text)Ø 中等粒度索引:存储文档号的位置Ø 细粒度索引:标识句子或者单词的序号 11 倒排文件(cont.)一般选择文档粒度,式样:<term, <num_of_doc; docid1,docid2,…>>使用粗粒度索引,在多术语查询的场合下更可能造成错配;另一个极端,单词级索引增加存储空间。单词级索引式样: <term,<num_of_doc;(docid1;pos_of_word1,pos_of_word2,…),…>> 12 签名文件 签名文件是一种面向索引文本的概率方法。每个文档都有一个关联签名(associated signature),或称为描述符(descriptor)。 为了创建文档的描述符,首先每个文档中的术语都需要被用来生成多个哈希值,然后将术语哈希值置1的比特位也为相应的文档签名的比特位置1即可。 13 签名文件(cont.) 检测一个查询术语是否在给定的文档中出现,需要计算该术语的各个哈希值。如果所对应的比特位在某个文档描述符中置位,则该术语可能出现在这个文档中。 弊端:错配检查! 签名文件索引只能排除文档,永远不能确定地选出文档。 14 位图 位图是十分简单的索引结构,字典中的每个术语都需要存储成比特向量的形式,每比特位对应一个文档。 位图不仅快,而且易于使用,但是极其耗费存储空间。(从TREC数据库看,一个位图索引比索引的文本本身还要大20倍) 15 索引压缩主要针对倒排文件索引 16 索引构造1. 什么是索引构造2. 索引构造方法3. 动态文档集合 17 什么是索引构造(针对倒排文件索引)索引构造的过程即通常所说的文本倒排(inversion)。一种显而见的创建倒排索引的方法是在内存中创建一个转置的频率矩阵。 18 索引构造方法Ø链接列表(基于内存)Ø链接列表(基于磁盘)Ø基于排序Ø基于排序且压缩Ø基于排序且多路归并Ø基于排序且多路原地归并Ø内存内压缩Ø基于字典,无额外磁盘消耗Ø基于字典,需要额外磁盘空间Ø基于文本的切分 19 链接列表(基于内存)20链接列表(基于内存)(cont.) 21 链接列表(基于内存)(cont.)链接表方法并不适合于GB级别以上的文档集合。它要么需要大量的内存,要么需要大量的时间开销。 22 基于排序23 基于排序(cont.)24 基于排序(cont.)Ø 必须使用两个临时文件。为什么?Ø 需要巨大的磁盘空间 25 基于排序且多路归并Ø 使用R路归并,共需要ceil(logR num_of_sortedrun)趟归并Ø 需要借助类似于Heap数据结构的优先队列 26 基于排序且多路原地归并27基于排序且多路原地归并(cont.) (a)归并段创建后 (b)归并后 (c)重排后 (d)缩减后 28 动态文档集合一个动态集合可以有两种状态:插入操作和编辑操作Ø插入操作允许在现有的文档集合后追加新的文档,但不修改目 前已有的任何文档。Ø编辑操作允许变更现有文档,并且有可能将其删除。 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 Practice[M]. 机械工业 出版社, 2009. 32ICRC学术讲座第2期 海量信息处理—索引 彭卫华 2009.11.23 1 内容一、索引介绍二、索引构造三、Q & A四、部分参考文献 2 索引介绍1. 为什么使用索引2. 索引什么3. 索引机制4. 索引压缩 3 为什么使用索引 什么是索引? Ø 索引是一种找出给定术语在文本中位置的机制。 使用原因? Ø 信息如何组织才能方便高效地查询 Ø 数据相关部分如何才能快速地抽取???若文档是图片—被索引的词汇可能是图片的若干描述词 4 索引什么使用文档中出现的每个单词?利:Ø有利于扩大术语集合的词汇量(出现的不重复术语的数量)Ø增加了索引中文档识别符的数量弊:Ø影响系统的存储空间Ø分解查询请求时,更多潜在的查询术语将会被分解出来,恶化了查询 结果 5 索引什么(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)中存储了一列指针(也叫 “记录”, posting),每个指针都表示了术语在文本中的全部出现Ø对于每个指针来说,它存放的值其实就是术语出现的文档号 10 倒排文件(cont.)索引粒度:表示标识术语精确度的一个概念Ø 粗粒度索引:标识一个文本组(block of text)Ø 中等粒度索引:存储文档号的位置Ø 细粒度索引:标识句子或者单词的序号 11 倒排文件(cont.)一般选择文档粒度,式样:<term, <num_of_doc; docid1,docid2,…>>使用粗粒度索引,在多术语查询的场合下更可能造成错配;另一个极端,单词级索引增加存储空间。单词级索引式样: <term,<num_of_doc;(docid1;pos_of_word1,pos_of_word2,…),…>> 12 签名文件 签名文件是一种面向索引文本的概率方法。每个文档都有一个关联签名(associated signature),或称为描述符(descriptor)。 为了创建文档的描述符,首先每个文档中的术语都需要被用来生成多个哈希值,然后将术语哈希值置1的比特位也为相应的文档签名的比特位置1即可。 13 签名文件(cont.) 检测一个查询术语是否在给定的文档中出现,需要计算该术语的各个哈希值。如果所对应的比特位在某个文档描述符中置位,则该术语可能出现在这个文档中。 弊端:错配检查! 签名文件索引只能排除文档,永远不能确定地选出文档。 14 位图 位图是十分简单的索引结构,字典中的每个术语都需要存储成比特向量的形式,每比特位对应一个文档。 位图不仅快,而且易于使用,但是极其耗费存储空间。(从TREC数据库看,一个位图索引比索引的文本本身还要大20倍) 15 索引压缩主要针对倒排文件索引 16 索引构造1. 什么是索引构造2. 索引构造方法3. 动态文档集合 17 什么是索引构造(针对倒排文件索引)索引构造的过程即通常所说的文本倒排(inversion)。一种显而见的创建倒排索引的方法是在内存中创建一个转置的频率矩阵。 18 索引构造方法Ø链接列表(基于内存)Ø链接列表(基于磁盘)Ø基于排序Ø基于排序且压缩Ø基于排序且多路归并Ø基于排序且多路原地归并Ø内存内压缩Ø基于字典,无额外磁盘消耗Ø基于字典,需要额外磁盘空间Ø基于文本的切分 19 链接列表(基于内存)20链接列表(基于内存)(cont.) 21 链接列表(基于内存)(cont.)链接表方法并不适合于GB级别以上的文档集合。它要么需要大量的内存,要么需要大量的时间开销。 22 基于排序23 基于排序(cont.)24 基于排序(cont.)Ø 必须使用两个临时文件。为什么?Ø 需要巨大的磁盘空间 25 基于排序且多路归并Ø 使用R路归并,共需要ceil(logR num_of_sortedrun)趟归并Ø 需要借助类似于Heap数据结构的优先队列 26 基于排序且多路原地归并27基于排序且多路原地归并(cont.) (a)归并段创建后 (b)归并后 (c)重排后 (d)缩减后 28 动态文档集合一个动态集合可以有两种状态:插入操作和编辑操作Ø插入操作允许在现有的文档集合后追加新的文档,但不修改目 前已有的任何文档。Ø编辑操作允许变更现有文档,并且有可能将其删除。 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 Practice[M]. 机械工业 出版社, 2009. 32ICRC学术讲座第2期 海量信息处理—索引 彭卫华 2009.11.23 1 内容一、索引介绍二、索引构造三、Q & A四、部分参考文献 2 索引介绍1. 为什么使用索引2. 索引什么3. 索引机制4. 索引压缩 3 为什么使用索引 什么是索引? Ø 索引是一种找出给定术语在文本中位置的机制。 使用原因? Ø 信息如何组织才能方便高效地查询 Ø 数据相关部分如何才能快速地抽取???若文档是图片—被索引的词汇可能是图片的若干描述词 4 索引什么使用文档中出现的每个单词?利:Ø有利于扩大术语集合的词汇量(出现的不重复术语的数量)Ø增加了索引中文档识别符的数量弊:Ø影响系统的存储空间Ø分解查询请求时,更多潜在的查询术语将会被分解出来,恶化了查询 结果 5 索引什么(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)中存储了一列指针(也叫 “记录”, posting)
关 键 词:
海量信息处理--索引 ppt、pptx格式 免费阅读 下载 天天文库
 天天文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
本文标题:海量信息处理--索引
链接地址: https://www.wenku365.com/p-39814446.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服点击这里,给天天文库发消息,QQ:1290478887 - 联系我们

本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】。本站是网络服务平台方,若您的权利被侵害,侵权客服QQ:1290478887 欢迎举报。

1290478887@qq.com 2017-2027 https://www.wenku365.com 网站版权所有

粤ICP备19057495号 

收起
展开