基于文本的索引构建技术

第三章

基于文本的索引构建技术

本章内容顺序文档索引基于内存单次扫描的索引构建技术基于块的排序索引技术本章小结倒排文档索引概要概要

基于文本的检索技术信息检索技术基于内容的检索技术概要概要

顺排文档把记录按照一定顺序完整地组织起来如：物品数据库依据物品记录号顺序进行建立。顺排文档（SequentialFile）把顺排文档中具有检索属性的项目信息抽取出来，重新排列组织成新的数据文档如：将物品数据库中的价格数据项抽取出来，依据物品价格有高到低重新建立新的索引文档。倒排文档（InvertedFile）

3.1基于块的排序索引技术3.1.1索引文档建立必须考虑的硬件性能

3.1基于块的排序索引技术

利用缓冲区压缩数据硬件性能连续存放数据块内存调用利用磁盘

3.1基于块的排序索引技术内存调用：访问内存数据比访问磁盘数据快得多（5×10−9sVS2×10−8s），尽可能地把数据放在内存中。

连续存放数据块：磁盘的寻道时间平均为4ms-5ms，连续读取的数据块也应该在磁盘上连续存放。

3.1基于块的排序索引技术利用缓冲区：操作系统往往以数据块为单位进行读写。数据块的大小通常为8KB、16KB、32KB或64KB。

压缩数据：数据从磁盘传输到内存是由系统总线而不是处理器来实现的，这意味着在磁盘I/0时处理器仍然可以处理数据。

3.1基于块的排序索引技术

利用磁盘：系统的服务器往往有数GB甚至数十GB的内存，可以利用服务器磁盘空间大小一般比内存大小要高几个数量级：TB-PB。

3.1基于块的排序索引技术

3.1.2基于块的排序索引方法

首先扫描一篇文档集合得到所有具有检索意义的词语的“此项-文档ID”数据集；然后依据此项的索引文档及的主键和文档ID为次键进行排序；最后将每个此项的文档ID组织成为倒排记录表，并计算此项频率或文档频率的统计量。思想

图3-1桂林电子科技大学-新闻模块目录实例3.1基于块的排序索引技术

3.1基于块的排序索引技术

图3-2桂林电子科技大学-新闻内容文档实例

3.1基于块的排序索引技术

符号含义统计值N文档总量900000L每篇文档的平均词项数量160M词项目总数190000每个词项的平均字节数（包含空格与标点）4.1B每个词项的平均字节数（不包含空格与标点）3.7B每个词项的平均字节数4.6BT倒排记录总数40000000

表3-1桂林电子科技大学-新闻文档集统计数据表

3.1基于块的排序索引技术基于磁盘的外部排序算法ESA（ExternalSortingAlgorithm）核心在索引排序时，尽量减少磁盘寻道次数基础BSBI算法（BlockedSort-basedIndexingAlgorithm,基于块的排序算法）

3.1基于块的排序索引技术

BSBI算法步骤：1将文档集分割成多个大小相等的部分4将所有的中间文件合并成最终的索引2将每个部分的词项ID—文档ID对排序3将中间产生的临时排序结果存放到磁盘中

3.1基于块的排序索引技术

选择合适的块算法，下图的算法将每个块的倒排索引存入文件中f1…fn，最后合并为fmerged。

图3-3基于块的排序索引算法

3.1基于块的排序索引技术

依据图3-3的算法将待合并的倒排记录表（两个数据块）从磁盘读入内存，然后在内存中合并后写入磁盘（见图3-4）。

图3-4基于块的排序方法合并示意图

3.2基于内存单次扫描的排序构建技术

基于内存单次扫描的索引算法SPIMI(single-passin-memoryindexing)：每块采用不同的词典，将每个块的词典写入磁盘，对于下一个块则重新采用新的词典。只要硬盘空间足够大，SPIMI就能够索引任何大小的文档集。原因基于块的排序索引算法具有很好的可扩展性，但是需要一种将所有词项放到内存。对于大规模的文档集来说，该数据结构会很大以致在内存中难以存放。

3.2基于内存单次扫描的排序构建技术

SPIMI算法的步骤：ClicktoaddTitleClicktoaddTitleClicktoaddTitle2将所有的中间文件合并成最终的索引1处理文档，直到内存不足，写入磁盘

3.2基于内存单次扫描的排序构建技术

图3-5SPIMI算法的块倒排索引生成算法

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）的展开检索基础表地址检索词条件满足指向条件非满足指向1A322B3落选3C命中44D命中落选表中，“命中”表示被查比的文献满足查询要求的出口，“落选”表示反之3.3顺排文档索引

2、展开表生成过程

检索词检索运算符改变运算次序的括号供检索匹配的表格前处理

3.3顺排文档索引

前处理判断提问式中的字符，从上而下填写表格。对不同类型对象的处理方式如下：表3-3对不同类型对象的处理表类型符号处理方式检索词将其存入展开表内的检索词栏，并记下在表中的地址运算符+前一词满足，指向“*”；不满足，指向后一词*前一词满足，指向后一词括号（在其后的检索词所在行的“级位”栏值加1）在其后的检索词所在行的“级位”栏值减1括号结束最后一个检索词所在行的“条件满足指向”栏放入“命中”，“条件不满足”放入“落选”

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”，则已命中，把提问号和记录号写入命中文档。种类动作+在完成标识栏置“1”，再向父项移动*N检索处理=N子项相等，标识栏置“1”，再向父项移动不相等，就返回进行下一词的处理-顺着父项进行注销处理

常见方法为逆波兰展开法。3.4倒排文档索引

是一种面向单词的索引机制，相对顺排文档而言，是将顺排文档中可检索字段的作者名、关键词、分类号等取出，按一定规则排序，归并相同词汇，并把在顺排文档中相关记录的记录号集合赋予其后，以保证通过某一特征词能够快速、方便地获取相关记录。思想

3.4倒排文档索引

3.4.1倒排文档索引的建立

倒排文档的组成元素如下：关键字目长记录号集合作者主题词分类号含有该关键字记录的条数所有与该关键字有关的记录号

3.4倒排文档索引

1、倒排文档的结构

倒排文档可视为主文档的辅助索引，它从不同的角度提供了对主文档的快速查询，不同属性的数据结构构成不同的倒排索引文档。2、倒排文档的建立

选择需要做索引的字段属性(如作者、关键词等)，抽出其中的内容，并在其后附上记录号抽词

对抽出的内容进行排序，使之便于归并相同内容排序

对相同内容进行归并，把合并后的内容放入倒排文档的主键字段(如标引词、作者等)，统计每一数据的频次为目长，把每一内容后的记录号顺序放在记录号集合字段归并

3.4倒排文档索引

记录号篇名作者标引词1知识管理与企业管理信息系统建设A知识管理，管理信息系统，企业信息化2论知识链与知识管理B知识管理，知识链，学习型组织，知识创新3刍议知识故那里及其体系框架C知识管理，知识创新，知识共享4知识管理的知识基础A知识管理，学习型组织5论技术创新的知识空间C技术创新，知识空间，知识创新6建立企业竞争性的信息结构A企业信息化，信息结构，竞争情报7知识管理在企业竞争情报研究中的应用B知识管理，竞争情报，知识创新8管理信息系统中文化行为研究B管理信息系统，企业文化9企业竞争情报管理系统的构建研究C管理信息系统，竞争情报10企业知识管理主体研究C知识管理，企业文化，管理创新表3-8文献及部分属性举例

3.4倒排文档索引

标引词目长记录号集合管理创新110管理信息系统31；8；9技术创新15竞争情报36；7；9企业文化28；10企业信息化21；6信息结构16学习型组织22；4；知识创新42；3；5；7；知识共享13知识管理61；2；3；4；7；10知识空间15知识链12表3-9关键词索引

3.4倒排文档索引

作者目长记录号集合A31；4；6B32；7；8C43；5；9;10表3-10作者索引建立倒排文档的过程中需要注意：第一，倒排文档的建立应具有即时更新的功能。第二，需要建立一处文档来解决不等长问题。

3.4倒排文档索引

3.4.2逻辑提问式的转换

1929年波兰的逻辑学家卢卡西维兹提出将运算符放在运算项后面的逻辑表达式，又称“逆波兰表达式”

日本的福岛首先将逆波兰表达式应用于情报检索，故又称“福岛方法”。例如：逻辑提问式A*(B+C)+D

→逆波兰表达式ABC+*D+思想福岛算法首先要进行提问式的转换。

3.4倒排文档索引

运算符优先处理的级别（）1+2*3-4表3-11运算符的优先级为转换处理开辟三个存储区：检索词表存储区逆波兰输出区123算子栈存放转换过程中的运算存放检索词存放逻辑提问式的逆波兰表达式3.4倒排文档索引

从左向右逐个扫描提问逻辑是的字符，遇到不同的对象做相应处理：对象类型处理动作运算符P当前>P前一为真，将该算符送算子栈内为假，将顶部算符取出送逆波兰输出区，，当前算符再与栈内顶部算符比较，当前算符的优先级低就取出送逆波兰输出区，否则就将该算符送算子栈内左括号将左括号无条件置入算子栈内右括号栈内括号间的所有算符无条件出栈，并送逆波兰输出去，同时放弃这对括号运算项将运算检索项存入检索词表，并将其在检索词表的位置送逆波兰输出区结束号算子栈内的算子依次出栈并送入逆波兰输出区*其中，P当前>P前一：当前算符的优先级高于前一算符；为假时，包括相等。3.4倒排文档索引

注意两点：1、栈的规则是元素“先进后出”，转换结束其栈为空2、逆波兰输出去的算子特征为1，检索词特征为03.4倒排文档索引

地址检索词01A02B03C04EF……特征内容0010021+0030041+1*0*逆波兰法处理示意图（+…检索词表（A+B）*（C+EF）词表地址算子区分运算项

还是运算符逆波兰输出区逻辑提问式算子栈图3-6逆波兰转换处理示意图3.4倒排文档索引3.4.3检索指令表的生成

逐行扫描逆波兰输出表，实现从逆波兰表转换为检索指令表。操作指令表由四列元素组成：第一列为操作码，指定本行操作类型；以后三列为操作