基于文本的索引构建技术 .ppt

3、2基于内存单次扫描的排序构建技术 SPIMI算法的步骤: Click to add Title Click to add Title Click to add Title 2 将所有的中间文件合并成最终的索引 1 处理文档，直到内存不足，写入磁盘 3、2基于内存单次扫描的排序构建技术 图3-5 SPIMI算法的块倒排索引生成算法 3、2基于内存单次扫描的排序构建技术 SPIMI算法与BSBI的区别: 　通过判定循环动态增加排序记录表的，倒排记录表的 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)的展开检索基础表 地址 检索词 条件满足指向 条件非满足指向 1 A 3 2 2 B 3 落选 3 C 命中 4 4 D 命中 落选 表中,“命中”表示被查比的文献满足查询要求的出口,“落选”表示反之 3、3顺排文档索引 2、展开表生成 过程 检索词 检索运算符 改变运算次序的括号 供检索匹配的表格 前处理 3、3顺排文档索引 前处理 判断提问式中的字符,从上而下填写表格。对不同类型对象的处理方式如下: 表3-3 对不同类型对象的处理表 类型 符号 处理方式 检索词 将其存入展开表内的检索词栏,并记下在表中的地址 运算符 + 前一词满足,指向“*”;不满足,指向后一词 * 前一词满足,指向后一词 括号 ( 在其后的检索词所在行的“级位”栏值加1 ) 在其后的检索词所在行的“级位”栏值减1 括号结束 最后一个检索词所在行的“条件满足指向”栏放入“命中”,“条件不满足”放入“落选” 3、3顺排文档索引 后处理 后处理的主要任务就是填满整个表的空白单元,填表的依据是表中“级位”栏的前后级位值,填表的顺序是从下向上,直至表的顶部,从而得到一个完整的提问展开表。 3、3顺排文档索引 3、表展开法的检索应用描述 每读取一条记录，就生成一个检索标识表（可检索项），然后将该表中的检索项去查展开表，并对命中的做上标记。 查匹配 根据展开表查询情况，分析提问是否命中。命中者，就在相应的提问号下记下记录号及相关信息，取下条记录进行对比。 检索项查完 得到本次检索的最终结果通过提问号调出检索结果中各自命中结果的记录给用户。 全部匹配完 3、3顺排文档索引 3、3、2 逻辑树索引 逻辑树展开法是将逻辑提问式展开成树型结构(下称主逻辑树),运算符构成树的结点,检索词被视为树叶,所有检索词也依照有限自动机原理构造成字符树(即子树),主树与子树间的相关元素用指针链接。 检索采取遍历树原则,先用文档中的索引词逐字符的遍历子树,当遍历到树的一个端点(树叶),然后依照指针登记主树,并依照遍历树方式分析提问是否命中。 逻辑树展开法包括三个部分:逻辑提问式的分解、字符树的生成、检索实现。 3、3顺排文档索引 1、逻辑提问式分解 逻辑提问式分解的分解目标为:提供可直截了当用于检索实现的主逻辑树表、检索词地址表以及检索词在检索式中的位置表。这些表在检索实践中分别发挥着应有的作用。 (1)主逻辑树表 主逻辑树表是逻辑提问式的一种树形表达形式,它用层次型的树形结构把