基于文本的索引构建技术.ppt
第三章,基于文本的索引构建技术,本章内容,顺序文档索引,基于内存单次扫描的索引构建技术,基于块的排序索引技术,本章小结,倒排文档索引,概要,概要,概要,概要,3.1基于块的排序索引技术,3.1.1索引文档建立必须考虑的硬件性能,3.1基于块的排序索引技术,3.1基于块的排序索引技术,内存调用：访问内存数据比访问磁盘数据快得多（5 10 9s VS 2 10 8s），尽可能地把数据放在内存中。连续存放数据块：磁盘的寻道时间平均为4ms-5ms，连续读取的数据块也应该在磁盘上连续存放。,3.1基于块的排序索引技术,利用缓冲区：操作系统往往以数据块为单位进行读写。数据块的大小通常为 8 KB、16 KB、32 KB 或 64 KB。,压缩数据：数据从磁盘传输到内存是由系统总线而不是处理器来实现的，这意味着在磁盘 I/0 时处理器仍然可以处理数据。,3.1基于块的排序索引技术,利用磁盘：系统的服务器往往有数 GB 甚至数十 GB 的内存，可以利用服务器磁盘空间大小一般比内存大小要高几个数量级：TB-PB。,3.1基于块的排序索引技术,3.1.2 基于块的排序索引方法,图3-1 桂林电子科技大学-新闻模块目录实例,3.1基于块的排序索引技术,3.1基于块的排序索引技术,图3-2 桂林电子科技大学-新闻内容文档实例,3.1基于块的排序索引技术,表3-1 桂林电子科技大学-新闻文档集统计数据表,3.1基于块的排序索引技术,3.1基于块的排序索引技术,BSBI算法步骤：,3.1基于块的排序索引技术,选择合适的块算法，下图的算法将每个块的倒排索引存入文件中f1fn，最后合并为fmerged。,图3-3 基于块的排序索引算法,3.1基于块的排序索引技术,依据图3-3的算法将待合并的倒排记录表（两个数据块）从磁盘读入内存，然后在内存中合并后写入磁盘（见图3-4）。,图3-4 基于块的排序方法合并示意图,3.2基于内存单次扫描的排序构建技术,基于内存单次扫描的索引算法SPIMI(single-pass in-memory indexing)：每块采用不同的词典，将每个块的词典写入磁盘，对于下一个块则重新采用新的词典。只要硬盘空间足够大，SPIMI 就能够索引任何大小的文档集。,3.2基于内存单次扫描的排序构建技术,SPIMI算法的步骤：,Click to add Title,Click to add Title,Click to add Title,3.2基于内存单次扫描的排序构建技术,图3-5 SPIMI算法的块倒排索引生成算法,3.2基于内存单次扫描的排序构建技术,SPIMI算法与BSBI的区别：,3.3顺排文档索引,3.3顺排文档索引,3.3.1 表展开法索引 1968年，日本学者菊池敏典提出，又称“菊池敏典算法”。目前主要用于面向定向服务的检索系统，旨在将代表用户的逻辑提问式转换成检索表的形式，该检索表规定了表内容走向和检索命中与否的判断，检索时根据表内容走向及其他相关信息来判断每条记录是否检索命中。,3.3顺排文档索引,1、展开表的含义 将经典布尔逻辑检索的逻辑提问表达式转换为逻辑检索表，每个检索词的检索组配关系要求能够用表进行精确映射，检索的记录是够最终命中检索需求要能准确反映出来。(A+B)*(C+D)的展开表如3-2所示表3-2（A+B）*（C+D）的展开检索基础表,表中，“命中”表示被查比的文献满足查询要求的出口，“落选”表示反之,3.3顺排文档索引,2、展开表生成,过程,3.3顺排文档索引,前处理判断提问式中的字符，从上而下填写表格。对不同类型对象的处理方式如下：表3-3 对不同类型对象的处理表,3.3顺排文档索引,后处理后处理的主要任务就是填满整个表的空白单元，填表的依据是表中“级位”栏的前后级位值，填表的顺序是从下向上，直至表的顶部，从而得到一个完整的提问展开表。,3.3顺排文档索引,3、表展开法的检索应用描述,3.3顺排文档索引,3.3.2 逻辑树索引,逻辑树展开法是将逻辑提问式展开成树型结构（下称主逻辑树），运算符构成树的结点，检索词被视为树叶，所有检索词也按照有限自动机原理构造成字符树（即子树），主树与子树间的相关元素用指针链接。检索采取遍历树原则，先用文档中的索引词逐字符的遍历子树，当遍历到树的一个端点（树叶），然后依照指针登记主树，并根据遍历树方式分析提问是否命中。逻辑树展开法包括三个部分：逻辑提问式的分解、字符树的生成、检索实现。,3.3顺排文档索引,1、逻辑提问式分解,逻辑提问式分解的分解目标为：提供可直接用于检索实现的主逻辑树表、检索词地址表以及检索词在检索式中的位置表。这些表在检索实践中分别发挥着应有的作用。（1）主逻辑树表 主逻辑树表是逻辑提问式的一种树形表达形式，它用层次型的树形结构把运算符、运算项关联起来，其主要内容包括；运算种类、子项个数、父项地址以及检索处理登记栏。,表3-4 主逻辑树表结构,3.3顺排文档索引,（2）检索词地址表 检索词地址表是主逻辑树表与子表的联系纽带，在检索中，当一个检索词命中以后，通过子表找到其在检索词地址表的位置，再根据该表中记录的主表位置进行检索处理（在检索处理栏加1等操作）。该表由两个字段组成：检索状况登录区、检索词在主表中位置。,表3-5 检索词地址表结构,3.3顺排文档索引,（3）检索词位置表 检索词位置表是在逻辑提问式转换成逻辑树表的过程中，临时生成的一个中间处理过程表，该表还将作为从逻辑提问式到词逻辑树子表的桥梁，一旦子表生成完毕，该表将被清除。,表3-6 检索词位置表结构,3.3顺排文档索引,（4）中间工作表 由于在进行逻辑提问式到逻辑树表的转换过程中，涉及一些中间数据，这些数据在生成逻辑树时需多次使用，因此需要建立一个中间过程工作区（中间工作表）来记录这些数据，一旦主逻辑树生成完毕，该表即可以清除。,表3-7 中间工作表结构,3.3顺排文档索引,（5）主逻辑树表的生成 主逻辑树表的生成算法思想为：采用多次扫描的分层分解构造法。首先分解出逻辑式中最外层“”号下的子项，括号内的项暂时不分解；其次扫描已分解出的子项（在最外层没有“”项的情况下对整个逻辑式进行）中的“*”号的运算子项，若该子项为括号括起项，则仍分解“”号子项；最后分解“-”号子项。,3.3顺排文档索引,2、逻辑树法检索应用,逻辑提问式最终转换为逻辑树的三个表：主逻辑树表、检索词地址表、检索词字符树表。这三个表构成了用户检索提问文档，整个检索主要依赖这三个表。实际检索过程为：从文档中读取一条记录，将记录中的标引项（主题词、责任者、分类号等可供检索的著录项）去匹配相关的检索词逻辑树，匹配成功者，根据检索词地址指针去判断检索词地址表对应的检索登录区，若为“1”，表明该吃已命中过，不需要在处理；若为“0”，则将该项置为“1”，同时根据本行的“主表位置”字段去修改主逻辑树表。,3.3顺排文档索引,对主逻辑树表的检索处理如下：在主逻辑树表中该词的“处理标志”栏中填上“1”，然后根据父项地址的指针找到父项行，对“检索处理”栏作加“1”运算，再查看“处理标识”栏，若为“1”，表示该子项已做过向上遍历处理，可返回进行下一词的处理；若为“0”，则根据“运算种类”做相应的处理。随着父项指针移动到顶行时，若该行的处理标志为“1”，则已命中，把提问号和记录号写入命中文档。,常见方法为逆波兰展开法。,3.4倒排文档索引,3.4倒排文档索引,3.4.1 倒排文档索引的建立 倒排文档的组成元素如下：,3.4倒排文档索引,1、倒排文档的结构 倒排文档可视为主文档的辅助索引，它从不同的角度提供了对主文档的快速查询，不同属性的数据结构构成不同的倒排索引文档。,2、倒排文档的建立,3.4倒排文档索引,表3-8 文献及部分属性举例,3.4倒排文档索引,表3-9 关键词索引,3.4倒排文档索引,表3-10 作者索引,建立倒排文档的过程中需要注意：第一，倒排文档的建立应具有即时更新的功能。第二，需要建立一处文档来解决不等长问题。,3.4倒排文档索引,3.4.2 逻辑提问式的转换 1929年波兰的逻辑学家卢卡西维兹提出将运算符放在运算项后面的逻辑表达式，又称“逆波兰表达式”日本的福岛首先将逆波兰表达式应用于情报检索，故又称“福岛方法”。例如：逻辑提问式 A*(B+C)+D逆波兰表达式 ABC+*D+思想福岛算法首先要进行提问式的转换。,3.4倒排文档索引,表3-11 运算符的优先级,为转换处理开辟三个存储区：,3.4倒排文档索引,从左向右逐个扫描提问逻辑是的字符，遇到不同的对象做相应处理：,*其中，P当前P前一：当前算符的优先级高于前一算符；为假时，包括相等。,3.4倒排文档索引,注意两点：,3.4倒排文档索引,逆波兰法处理示意图,检索词表,（A+B）*（C+EF）,词表地址,算子,区分运算项还是运算符,逆波兰输出区,逻辑提问式,算子栈,图3-6 逆波兰转换处理示意图,3.4倒排文档索引,3.4.3 检索指令表的生成 逐行扫描逆波兰输出表，实现从逆波兰表转换为检索指令表。操作指令表由四列元素组成：第一列为操作码，指定本行操作类型；以后三列为操作数属性，根据操作码来决定三个操作数之间的关系，具体处理过程如下：,若为检索词，操作码置1，第一操作数存放从逆波兰输出表中取出的检索同地址，第三操作数放置在放该检索词记录号集合的工作区代号。,表3-12 检索词操作指令表示,3.4倒排文档索引,若为运算符，操作码为“3”、“4”、“5”，分别代表运算符“”、“*”、“-”，第一、二操作数指定的两个工作区的记录号集合根据操作码进行相关运算，其结果送第三操作数指定的工作区。,表3-13 运算操作指令表示,若为结束行，将操作码置2，表示转储操作，把检索运算结果送第7工作区。,表3-14 结束操作指令表示,3.4倒排文档索引,若转储操作结束，将最后一行的操作码置为0，表示终止操作。,表3-15 转储操作指令表示,由于当时计算机内存的硬件特征有限，福岛方法设定工作区为7个，工作区的使用从前向后遇空闲即分配，从而保证了7个工作区能够满足检索过程的需要。,3.4倒排文档索引,3.4.4 检索实施 按照检索指令表的顺序，依赖检索词表和检索指令表，进行操作：若操作码为“1”，进行查找和输入操作。若操作码为“2”，转储操作。若操作码大于“2”，逻辑运算操作，运算结果存放到第三操作数指定的工作区中。若操作码为“0”，逻辑检索提问式检索结束，需根据第7工作区的内容（命中结果）到主文档中调出命中记录，显示或打印给用户。,3.5本章小结,信息检索技术分为两大类，即基于文本的检索技术和基于内容的检索技术 文档分为顺排文档和倒排文档基于块的排序算法基于内存但系扫描的索引算法（SPIMI）顺排文档索引：表展开法、逻辑树法倒排文档索引：逆波兰展开法,
