版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第三章 基于文本的索引构建技术 2/20本章内容顺序文档索引基于内存单次扫描的索引构建技术基于块的排序索引技术本章小结倒排文档索引3/20概要概要基于文本的检索技术信息检索技术基于内容的检索技术4/20概要概要 顺排文档把记录按照一定顺序完整地组织起来 如:物品数据库依据物品记录号顺序进行建立。顺排文档(Sequential File) 把顺排文档中具有检索属性的项目信息抽取出来,重新排列组织成新的数据文档 如:将物品数据库中的价格数据项抽取出来,依据物品价格有高到低重新建立新的索引文档。倒排文档(Inverted File)5/20 3.1基于块的排序索引技术3.1.1索引文档建立必须考虑的
2、硬件性能6/203.1基于块的排序索引技术 7/20 3.1基于块的排序索引技术v内存调用内存调用:访问内存数据比访问磁访问内存数据比访问磁盘数据盘数据快得多(快得多( 5 5 10 10 9 9s VS 2 s VS 2 10 10 8 8s s),尽可能地把数据放在内存中尽可能地把数据放在内存中。 v连续存放数据块:磁盘的寻道时间平均为连续存放数据块:磁盘的寻道时间平均为4ms-5ms4ms-5ms,连续读取的数据块也应该在磁盘连续读取的数据块也应该在磁盘上连续存放。上连续存放。 8/20 3.1基于块的排序索引技术v利用缓冲区:利用缓冲区:操作系统往往以数据块为单操作系统往往以数据块为单
3、位进行读写。数据块的大小通常为位进行读写。数据块的大小通常为 8 KB 8 KB、16 KB16 KB、32 KB 32 KB 或或 64 KB 64 KB。 v压缩数据:压缩数据:数据从磁盘传输到内存是由系统数据从磁盘传输到内存是由系统总线而不是处理器来实现的,这意味着在磁总线而不是处理器来实现的,这意味着在磁盘盘 I/0 I/0 时处理器仍然可以处理数据。时处理器仍然可以处理数据。9/20 3.1基于块的排序索引技术 v利用磁盘:利用磁盘:系统的服务器往往有数系统的服务器往往有数 GB GB 甚甚至数十至数十 GB GB 的内存的内存,可以利用,可以利用服务器磁盘服务器磁盘空间大小一般比内
4、存大小要高几个数量级:空间大小一般比内存大小要高几个数量级:TB-PBTB-PB。10/20 3.1基于块的排序索引技术 3.1.2 3.1.2 基于块的排序索引方法基于块的排序索引方法 首先扫描一篇文档集合得到所有具有检索意义的词语的“此项-文档ID”数据集;然后依据此项的索引文档及的主键和文档ID为次键进行排序;最后将每个此项的文档ID组织成为倒排记录表,并计算此项频率或文档频率的统计量。思想11/20 图3-1 桂林电子科技大学-新闻模块目录实例3.1基于块的排序索引技术 12/20 3.1基于块的排序索引技术 图3-2 桂林电子科技大学-新闻内容文档实例13/20 3.1基于块的排序索
5、引技术 表3-1 桂林电子科技大学-新闻文档集统计数据表14/20 3.1基于块的排序索引技术基于磁盘的外部排序算法ESA(External Sorting Algorithm)核心在索引排序时,尽量减少磁盘寻道次数基础BSBI算法(Blocked Sort-based Indexing Algorithm,基于块的排序算法)15/20 3.1基于块的排序索引技术 BSBI算法步骤:1将文档集分割成多个大小相等的部分4将所有的中间文件合并成最终的索引2将每个部分的词项 ID文档 ID 对排序3将中间产生的临时排序结果存放到磁盘中16/20 3.1基于块的排序索引技术 选择合适的块算法,下图的算
6、法将每个块的倒排索引存选择合适的块算法,下图的算法将每个块的倒排索引存入文件中入文件中f f1 1f fn n,最后合并为,最后合并为f fmergedmerged。 图图3-3 3-3 基于块的排序索引算法基于块的排序索引算法17/20 3.1基于块的排序索引技术 依据图依据图3-33-3的算法将待合并的倒排记录表(两个数据块)的算法将待合并的倒排记录表(两个数据块)从磁盘读入内存,然后在内存中合并后写入磁盘(见图从磁盘读入内存,然后在内存中合并后写入磁盘(见图3-43-4)。)。 图图3-4 3-4 基于块的排序方法合并示意图基于块的排序方法合并示意图18/20 3.2基于内存单次扫描的排
7、序构建技术 基于内存单次扫描的索引算法基于内存单次扫描的索引算法SPIMI (single-pass SPIMI (single-pass in-memory indexing)in-memory indexing):n每块采用不同的词典,将每个块的词典写入磁盘,每块采用不同的词典,将每个块的词典写入磁盘,对于下一个块则重新采用新的词典。对于下一个块则重新采用新的词典。n只要硬盘空间足够大,只要硬盘空间足够大,SPIMI SPIMI 就能够索引任何大小就能够索引任何大小的文档集。的文档集。原因基于块的排序索引算法具有很好的可扩展性,但是需要一种将所有词项放到内存。对于大规模的文档集来说,该数据
8、结构会很大以致在内存中难以存放。19/20 3.2基于内存单次扫描的排序构建技术 SPIMISPIMI算法的步骤:算法的步骤:Click to add TitleClick to add TitleClick to add Title2将所有的中间文件合并成最终的索引1处理文档,直到内存不足,写入磁盘20/20 3.2基于内存单次扫描的排序构建技术 图图3-5 SPIMI3-5 SPIMI算法的块倒排索引生成算法算法的块倒排索引生成算法21/20 3.2基于内存单次扫描的排序构建技术 SPIMISPIMI算法与算法与BSBIBSBI的区别:的区别:通过判定循环动态增加排序记录表的,倒排记录表的
9、SPIMISPIMI算法算法直接在倒排记录表中增加定位符项,且开始就需要处理形成所有项的“词项文档”并进行排序BSBIBSBI算法算法22/20 3.3顺排文档索引 将文档中的每一条记录依次去匹配用户的将文档中的每一条记录依次去匹配用户的检索提问集合,文档处理完毕后,将各提问的检索提问集合,文档处理完毕后,将各提问的命中结果归并分发给有关用户。命中结果归并分发给有关用户。思想 用文档中记录一条一条去匹配提问的,是顺用文档中记录一条一条去匹配提问的,是顺序对文档记录检索的方法序对文档记录检索的方法定义 采用列表处理方法将提问逻辑式(检索式)采用列表处理方法将提问逻辑式(检索式)变换成等价的提问展
10、开式,按提问展开表的内变换成等价的提问展开式,按提问展开表的内容对顺排文档的每篇文献进行检索容对顺排文档的每篇文献进行检索关键技术表展开法、逻辑树法等表展开法、逻辑树法等常见方法23/20 3.3顺排文档索引 3.3.1 3.3.1 表展开法索引表展开法索引 1968 1968年,日本学者菊池敏典提出,又称年,日本学者菊池敏典提出,又称“菊池菊池敏典算法敏典算法”。目前主要用于面向定向服务的检索系。目前主要用于面向定向服务的检索系统,旨在将代表用户的逻辑提问式转换成检索表的统,旨在将代表用户的逻辑提问式转换成检索表的形式,该检索表规定了表内容走向和检索命中与否形式,该检索表规定了表内容走向和检
11、索命中与否的判断,检索时根据表内容走向及其他相关信息来的判断,检索时根据表内容走向及其他相关信息来判断每条记录是否检索命中。判断每条记录是否检索命中。24/20 3.3顺排文档索引 1 1、展开表的含义、展开表的含义 将经典布尔逻辑检索的逻辑提问表达式转换为逻辑将经典布尔逻辑检索的逻辑提问表达式转换为逻辑检索表,每个检索词的检索组配关系要求能够用表进行检索表,每个检索词的检索组配关系要求能够用表进行精确映射,检索的记录是够最终命中检索需求要能准确精确映射,检索的记录是够最终命中检索需求要能准确反映出来。反映出来。(A+B)(A+B)* *(C+D)(C+D)的展开表如的展开表如3-23-2所示
12、所示表表3-2 3-2 (A+BA+B)* *(C+DC+D)的展开检索基础表)的展开检索基础表l表中,“命中”表示被查比的文献满足查询要求的出口,“落选”表示反之25/203.3顺排文档索引 2 2、展开表生成、展开表生成v过程过程v检索检索词词v检索运算符检索运算符v改变运算次序的括号改变运算次序的括号供检索匹配的表格前处理26/20 3.3顺排文档索引 v前处理前处理n判断提问式中的字符,从上而下填写表格判断提问式中的字符,从上而下填写表格。对不同类型对不同类型对象的处理方式如下:对象的处理方式如下:表表3-3 3-3 对不同类型对象的处理表对不同类型对象的处理表27/20 3.3顺排文
13、档索引 v后处理后处理n后处理的主要任务就是填满整个表的空白单元,后处理的主要任务就是填满整个表的空白单元,填表的依据是表中填表的依据是表中“级位级位”栏的前后级位值,填栏的前后级位值,填表的顺序是从下向上,直至表的顶部,从而得到表的顺序是从下向上,直至表的顶部,从而得到一个完整的提问展开表。一个完整的提问展开表。28/20 3.3顺排文档索引 3 3、表展开法的检索应用描述、表展开法的检索应用描述 每读取一条记录,就生成一个检索标每读取一条记录,就生成一个检索标识表识表(可检索项可检索项),然后将,然后将该该表中的检索表中的检索项去查展开表,并对命中的做上标记项去查展开表,并对命中的做上标记
14、。查查匹配匹配 根据展开表查询情况,分析提问是否命根据展开表查询情况,分析提问是否命中中。命中者,就在相应的提问号下记下记命中者,就在相应的提问号下记下记录号及相关信息,取下条记录进行对录号及相关信息,取下条记录进行对比。比。检索项查检索项查完完 得到本次检索的最终结果得到本次检索的最终结果通过提问号通过提问号调出检索结果中各自命中结果的记录给用调出检索结果中各自命中结果的记录给用户。户。全部全部匹配匹配完完29/203.3顺排文档索引 3.3.2 3.3.2 逻辑树索引逻辑树索引v逻辑树展开法是将逻辑提问式展开成树型结构(下称主逻辑树),运算符构成树的结点,检索词被视为树叶,所有检索词也按照
15、有限自动机原理构造成字符树(即子树),主树与子树间的相关元素用指针链接。v检索采取遍历树原则,先用文档中的索引词逐字符的遍历子树,当遍历到树的一个端点(树叶),然后依照指针登记主树,并根据遍历树方式分析提问是否命中。v逻辑树展开法包括三个部分:逻辑提问式的分解、字符树的生成、检索实现。30/203.3顺排文档索引 1 1、逻辑提问式分解、逻辑提问式分解 逻辑提问式分解的分解目标为:提供可直接用于检索实现的主逻辑树表、检索词地址表以及检索词在检索式中的位置表。这些表在检索实践中分别发挥着应有的作用。(1)主逻辑树表 主逻辑树表是逻辑提问式的一种树形表达形式,它用层次型的树形结构把运算符、运算项关
16、联起来,其主要内容包括;运算种类、子项个数、父项地址以及检索处理登记栏。表表3-4 3-4 主逻辑树表结构主逻辑树表结构31/20 3.3顺排文档索引 (2)检索词地址表)检索词地址表 检索词地址表是主逻辑树表与检索词地址表是主逻辑树表与子子表的联系纽带,在表的联系纽带,在检索中,当一个检索词命中以后,通过检索中,当一个检索词命中以后,通过子子表找到其在检表找到其在检索词地址表的位置,再根据该表中记录的主表位置进行索词地址表的位置,再根据该表中记录的主表位置进行检索处理(在检索处理栏加检索处理(在检索处理栏加1等操作)。该表由两个字段等操作)。该表由两个字段组成:检索状况登录区、检索词在主表中
17、位置组成:检索状况登录区、检索词在主表中位置 。表表3-5 3-5 检索词地址表结构检索词地址表结构32/20 3.3顺排文档索引 (3)检索词位置表)检索词位置表 检索词位置表是在逻辑提问式转换成逻辑树表的过检索词位置表是在逻辑提问式转换成逻辑树表的过程中,临时生成的一个中间处理过程表,该表还将作为程中,临时生成的一个中间处理过程表,该表还将作为从逻辑提问式到词逻辑树从逻辑提问式到词逻辑树子子表的桥梁,一旦表的桥梁,一旦子子表生成完表生成完毕,该表将被清除。毕,该表将被清除。表表3-6 3-6 检索词位置表结构检索词位置表结构33/20 3.3顺排文档索引 (4)中间工作表)中间工作表 由于
18、在进行逻辑提问式到逻辑树表的转换过程中,由于在进行逻辑提问式到逻辑树表的转换过程中,涉及一些中间数据,这些数据在生成逻辑树时需多次使涉及一些中间数据,这些数据在生成逻辑树时需多次使用,因此需要建立一个中间过程工作区(中间工作表)用,因此需要建立一个中间过程工作区(中间工作表)来记录这些数据,一旦主逻辑树生成完毕,该表即可以来记录这些数据,一旦主逻辑树生成完毕,该表即可以清除。清除。 表表3-7 3-7 中间工作表结构中间工作表结构34/20 3.3顺排文档索引 (5)主逻辑树表的生成)主逻辑树表的生成 主逻辑树表的生成算法思想为:采用多次扫描的分主逻辑树表的生成算法思想为:采用多次扫描的分层分
19、解构造法。首先分解出逻辑式中最外层层分解构造法。首先分解出逻辑式中最外层“”号下的号下的子项,括号内的项暂时不分解;其次扫描已分解出的子子项,括号内的项暂时不分解;其次扫描已分解出的子项(在最外层没有项(在最外层没有“”项的情况下对整个逻辑式进行)项的情况下对整个逻辑式进行)中的中的“*”号的运算子项,若该子项为括号括起项,则仍分号的运算子项,若该子项为括号括起项,则仍分解解“”号子项;最后分解号子项;最后分解“-”号子项。号子项。35/20 3.3顺排文档索引2、逻辑树法检索应用 逻辑提问式最终转换为逻辑树的三个表:主逻辑树表、检索词地址表、检索词字符树表。这三个表构成了用户检索提问文档,整
20、个检索主要依赖这三个表。 实际检索过程为:从文档中读取一条记录,将记录中的标引项(主题词、责任者、分类号等可供检索的著录项)去匹配相关的检索词逻辑树,匹配成功者,根据检索词地址指针去判断检索词地址表对应的检索登录区,若为“1”,表明该吃已命中过,不需要在处理;若为“0”,则将该项置为“1”,同时根据本行的“主表位置”字段去修改主逻辑树表。36/20 3.3顺排文档索引 对主逻辑树表的检索处理如下:对主逻辑树表的检索处理如下:v在主逻辑树表中该词的在主逻辑树表中该词的“处理标志处理标志”栏中填上栏中填上“1”,然后根据父项地址的指针找到父项行,对然后根据父项地址的指针找到父项行,对“检索处理检索
21、处理”栏作加栏作加“1”运算,再查看运算,再查看“处理标识处理标识”栏,若为栏,若为“1”,表示该子项已做过向上遍历处理,可返回进行,表示该子项已做过向上遍历处理,可返回进行下一词的处理;若为下一词的处理;若为“0”,则根据,则根据“运算种类运算种类”做相做相应的处理。应的处理。v随着父项指针移动到顶行时,若该行的处理标志为随着父项指针移动到顶行时,若该行的处理标志为“1”,则已命中,把提问号和记录号写入命中文档。,则已命中,把提问号和记录号写入命中文档。37/20 常见方法为逆波兰展开法。3.4倒排文档索引 是一种面向单词的索引机制,相对顺排文档而言,是将顺排文档中可检索字段的作者名、关键词
22、、分类号等取出,按一定规则排序,归并相同词汇,并把在顺排文档中相关记录的记录号集合赋予其后,以保证通过某一特征词能够快速、方便地获取相关记录。思想38/20 3.4倒排文档索引 3.4.1 3.4.1 倒排文档索引的建立倒排文档索引的建立 倒排文档的组成元素如下:如下: 关键字目长记录号集合作者主题词分类号含有该关键字记录的条数所有与该关键字有关的记录号39/20 3.4倒排文档索引 1 1、倒排文档的结构、倒排文档的结构 倒排文档可视为主文档的辅助索引,它从不同的角度倒排文档可视为主文档的辅助索引,它从不同的角度提供了对主文档的快速查询,不同属性的数据结构构成不提供了对主文档的快速查询,不同
23、属性的数据结构构成不同的倒排索引文档。同的倒排索引文档。2 2、倒排文档的建立、倒排文档的建立 选择需要做索引的字段属性(如作者、关键词等),抽出其中的内容,并在其后附上记录号抽词抽词 对抽出的内容进行排序,使之便于归并相同内容排序排序 对相同内容进行归并,把合并后的内容放入倒排文档的主键字段(如标引词、作者等),统计每一数据的频次为目长,把每一内容后的记录号顺序放在记录号集合字段归并归并40/20 3.4倒排文档索引 表表3-8 3-8 文献及部分属性举例文献及部分属性举例41/20 3.4倒排文档索引 表表3-9 3-9 关键词索引关键词索引42/20 3.4倒排文档索引 表表3-10 3
24、-10 作者索引作者索引建立倒排文档的过程中需要注意:第一,倒排文档的建立应具有即时更新的功能。第二,需要建立一处文档来解决不等长问题。43/20 3.4倒排文档索引 3.4.2 3.4.2 逻辑提问式的转换逻辑提问式的转换 1929年波兰的逻辑学家卢卡西维兹提出将运算符放在运算项后面的逻辑表达式,又称“逆波兰表达式”日本的福岛首先将逆波兰表达式应用于情报检索,故又称“福岛方法”。例如:逻辑提问式 A*(B+C)+D逆波兰表达式 ABC+*D+ 思想福岛算法首先要进行提问式的转换。思想福岛算法首先要进行提问式的转换。 44/20 3.4倒排文档索引 表表3-11 3-11 运算符的优先级运算符
25、的优先级v为转换处理开辟三个存储区:为转换处理开辟三个存储区:检索词表存储区逆波兰输出区123算子栈存放转换过程中的运算存放检索词存放逻辑提问式的逆波兰表达式45/203.4倒排文档索引 从左向右逐个扫描提问逻辑是的字符,遇到不同的从左向右逐个扫描提问逻辑是的字符,遇到不同的对象做相应处理:对象做相应处理:*其中,P当前P前一:当前算符的优先级高于前一算符;为假时,包括相等。46/203.4倒排文档索引 注意两点:注意两点:1、栈的规则是、栈的规则是元素元素“先进后先进后出出”,转换结,转换结束其栈为空束其栈为空2、逆波兰输出、逆波兰输出去的算子特去的算子特征为征为1,检索,检索词特征为词特征为047/203.4倒排文档索引 v逆波兰法处理示意图逆波兰法处理示意图检索词表(A+B)*(C+EF)词表地址算子区分运算项还是运算符逆波兰输出区逻辑提问式算子栈图3-6 逆波兰转换处理示意图48/203.4倒排文档索引3.4.3 3.4.3 检索指令表的生成检索指令表的生成 逐行扫描逆波兰输出表 ,实现从逆波兰表转换
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年安全教育培训试题含答案(精练)
- 2023年教师资格之幼儿综合素质押题练习试卷B卷附答案
- 2025 安全工程师(初级)考试及答案
- 2024年女职工权益保护法律知识竞赛题库及答案
- (2025年)设备维护保养培训考试卷(含答案)
- 2025叉车司机考试试题及答案
- 【房屋构造与维护管理】形成性考核册答案(附题目)
- 2022年基金从业资格考试真题及答案
- (2025)建筑安全生产知识竞赛题库及答案
- (2026版)医院感染管理相关法律法规知识试题及答案
- 中医医院卒中中心脑出血救治流程
- 《股票价值评估用》课件
- 2027贵州航天电器秋季招聘284人考试备考题库及答案解析
- 地理信息数据分类分级工作指南试行全文
- 再生水回用处理工程设计
- 【新教材核心素养】教科版科学五年级上册3.3《用弹力驱动小车》教学课件
- 企业车间主任(班组长)岗位安全职责培训
- 氧、氮、氩气管道安装施工方案
- G3111混凝土结构加固构造图集施工技术交底与验收检查表模板
- 小学五年级英语语法讲义
- 学校实习委托书范本
评论
0/150
提交评论