第6章 计算机信息检索概述

第6章

计算机信息检索概述信息组织与检索——目录6.1计算机信息检索的含义和特点6.1.1

含义6.1.2

发展简史6.1.3

分类6.1.4

特点目录6.2

计算机信息检索的数学模型6.2.1

布尔检索模型6.2.2

向量空间模型6.2.3

概率检索模型参见《计算机情报检索》P36－41目录6.3计算机信息检索的策略6.3.1

检索策略的含义与作用6.3.2

检索表达式6.3.3

检索表达式的构造步骤6.3.4

检索策略的反馈与调节目录6.4信息检索技术6.4.1

文档检索技术6.4.2

全文检索技术

6.4.1.1

书目数据库的结构：记录与字段、逻辑记录与物理记录、各种文档

6.4.1.2

顺序文档的检索技术

6.4.1.3倒排文档的检索技术6.4.3

基于内容的多媒体检索技术：图像、视频、音频含义：人们根据特定的信息需求，按照一定的方法，利用计算机从相关的信息检索系统中识别并获取所需的信息的过程。本质——信息用户的提问标识与信息集合数据库特征标识匹配的过程。参见图6－1。6.1.1计算机信息检索的含义6.1.2计算机信息检索发展简史120世纪50年代开始的脱机批处理检索。定题检索和回溯检索。220世纪60年代至80年代的联机检索阶段。320世纪80年代以来的光盘检索。20世纪80年代后期开始的网络检索。原有的联机检索系统的网络化；搜索引擎。46.1.3计算机信息检索的分类1.根据所检索数据库的形式分：书目检索、数据检索、事实检索和全文检索。2.根据计算机检索服务形式分：SDI、回溯检索和日常检索3.根据检索方式分：脱机检索、联机检索、光盘检索（又分为单机光盘检索和光盘网络检索两种）和网络检索6.1.4计算机信息检索的特点1.检索范围大2.速度快3.功能强大、组配灵活4.途径多5.数据更新及时，时效性强6.检索结果输出形式多样6.2计算机信息检索的数学模型信息检索的数学模型：就是运用数学的语言和工具，对信息检索系统中的信息及其处理过程加以翻译和抽象，表述为某种数学公式，再经过演绎、推断、解释和实际检验，反过来指导信息检索实践。检索系统的形式化描述：S＝（D，T，Q，f）其中，D＝（D1，D2，D3，……Dn），为某系统中经过标引的文献集合，T＝（T1，T2，T3，……Tm），Q＝（Q1，Q2，Q3，……Ql），T和Q分别表示所有可能存在的标引词集合和提问集合，f为匹配函数。6.2.1布尔检索模型采用布尔代数的方法，用布尔表达式表示用户提问，通过对文献标识与提问式的逻辑比较来检索文献。在传统的布尔模型中，每一文献用一组标引词表示。例如，对于某一特定文献i，可表示为：Di＝（T1，T2，T3……Tm）每个提问则表示为标引词的布尔组配。例如某个特定的提问Qj，表示为Qj＝（T1ANDT2）OR（T3

AND（NOTT4））6.2.1布尔检索模型局限：布尔检索式的非友善性，即构造一个好的检索式是不容易的易造成零输出或输出过量无差别的组配元，不能区分各组配元的重要程度匹配标准存在某些不合理的地方检索结果不能按照任何用户定义的重要性排序输出。6.2.2向量空间模型向量空间模型（Vector

SpaceModel）中，检索系统中的每一篇文献和每个提问均用等长的向量表示：Di＝（T1，T2，T3……Tm）Tj

＝（T1，T2，T3……Tm），Di为文献集合中的第i篇文献；Qj为提问集合中的第j个提问；Tk表示文献向量或提问向量中的第k个分量，即文献表示或提问式中所含的第k个标引词或检索词。传统的向量空间模型将Tk取值为0或1，现在大多在[0，1]区间取值。6.2.2向量空间模型可以构成一个向量空间，把信息检索中文献与提问的匹配处理过程转化为向量空间中文献向量与提问向量的相似度问题。某一文献与某一提问的相关程度通过计算该向量对之间的相似度来测定。最简单的计算相似度的方法是用点积函数，它把文献向量与提问向量的相似度定义为：S（Di，Qj）＝∑Tik×TjkK＝1m6.2.2向量空间模型最常用的计算相似度的方法是用余弦函数，它把文献向量与提问向量的相似度定义为：√

∑

（Tik）2×∑

（Tjk）2S（Di，Qj）＝K＝1m∑Tik×TjkK＝1mK＝1m6.2.2向量空间模型向量空间模型的局限：①相似度计算的工作量巨大；②文献向量中各分量的值(标引词权值)较难确定；③对标引词两两正交的假设也太僵硬。文献中的标引词实际上并不是相互独立的，它们之间存在一定的语义联系。为此，有人又致力于研究基于词相依性的向量模型。6.2.3概率检索模型概率检索模型（ProbabilisticModel）基于概率排序原理，即文献应该根据它们与提问的相关概率来排序输出。基本思想：给定文献与给定提问之间存在不确定性，即给定文献与给定提问之间存在某种相关概率。所以利用概率论的原理，通过赋予标引词某种概率值来表示这些词在相关文献集合或无关文献集合中的出现的概率，然后计算某一给定文献与某给定提问相关的概率，最后系统据此作出检索决策。它的提问式不是直接由用户编定的，是由系统通过某种归纳式学习过程(相关反馈)来构造一个决策函数去表示用户提问。6.2.3概率检索模型由M·E·Maron和J·L·Kuhns最早提出了概率标引理论。该模型将将标引作业描述为：给定某一特定文献d，对某个标引词来说，标引员的任务是作出这样的预测：如果某一类型用户B判定d为相关且在他的提问中只用一个检索词，则他可能选用该词的概率有多大。

——也就是说，标引员要估计的是：对使用该标引词检索文献的给定用户类型来说，某一给定文献的相关概率或权值。标引词加权和利用这种权值来计算文献的“相关值”(满足给定提问的概率)的方法就是概率标引理论的基础。概率检索模型1：6.2.3概率检索模型概率检索模型1：首先定义一组事件Di：获得的第i篇文献并发现它是相关的。Ij：要求获得以第j个词为标引词的某一主题领域的文献。A：来自信息资源集合的信息。然后，利用Bayes逆概公式,对文献的相关概率加以定义。6.2.3概率检索模型概率检索模型1：公式左端表示当某用户要求获得有关Ij的信息时，文献Di满足其需要的概率；右端的P(A，Di)是文献Di的一个先验概率，通过信息资源管理机构的统计数据获得；P(A，Di，Ij)表示当某用户需要获得Di所含的信息时，他用Ij做检索词的概率，而对于给定的提问Ij来说，P(A，Jj)是一个常数。6.2.3概率检索模型基本思想：标引阶段不对标引词进行加权，而是在检索阶段才导入概率检索机制。检索作业重复若干次，每重复一次，用户就对检出文献进行相关性判断。然后利用这种反馈信息，根据每个词在相关文献集合和无关文献集合的分布情况来计算它们的相关概率。用下式计算标引词的权值：p和p’是该模型的参数，分别表示某词在相关文献集合或无关文献集合中出现的概率。某一文献的权值(决定它在排序输出中的位置）则是它所含的标引权值之和。概率检索模型2：词相关权值＝logp/（1－p）p’/（1－p’）6.2.3概率检索模型基本思想：同时做两种预测，标引员选词标引时要预测文献对具有不同特性的用户的相关概率；用户选词检索时也要预测某词对具有不同特性的文献的相关概率。可用下图来表示模型3。概率检索模型3：Model3Model1Model2标引员用户信息集合信息需求信息特征提问特征预测6.2.3概率检索模型概率检索模型的一般表述形式：给定提问Q，则文献D的相关概率为P(rel︱D)。根据Bayes定理，可用下式求其值：P(rel)和P(nrel)分别代表某一给定文献相关或不相关的先验概率；

P(D︱rel)和P(D︱nrel)则代表文献D属于相关文献集合或无关文献集合的概率。P(rel︱D)＝P(D︱rel)×P(rel)

P(D︱rel)×P(rel)＋P(D︱nrel)×P(nrel)6.2.3概率检索模型概率检索模型的主要优点是：①它注意到检索决策是容易出错的，故采用了一种理论上更为严密的方式来进行决策。②它容易与加权方法结合起来，为人们提供了一种理论基础③它不涉及布尔算符的使用，回避了构造布尔提问式的困难④文献可按用户的期望值来排序输出⑤吸收了相关反馈原理，可开发出理论上更为坚实的方法。6.2.3概率检索模型概念检索模型的主要缺陷：①布尔关系消失了(至少在早期的模型中是如此)，AANDB和AORB被视为等同。②增加了存贮和计算资源的开销。③参数估计难度大。为此，人们提出了各种参数估计技术，如最大阀值估计法，相关反馈原理，最大熵原理等。6.3.1检索策略的含义与作用检索策略的基本知识：通常应是在分析检索课题内容实质（即明确检索目标和信息需求）的基础上进行的，选择检索系统，确定检索词及其相互关系、拟定检索表达式等的信息检索方案。是为实现检索目标而制定的计划或方案，是对整个检索过程的科学规划。可分为手工检索策略和计算机检索策略。明确用户的信息需求，是制定检索策略的基础和依据。6.3.2检索表达式是检索策略的逻辑表达式和具体体现，是指信息检索中用来表达用户检索提问的逻辑表达式；由检索词和各种布尔逻辑算符、位置算符以及系统规定的其他组配连接符号组成。是计算机可以识别和执行的命令形式。6.3.2检索表达式6.3.2.1逻辑表达式基于布尔检索模型。布尔逻辑算符：常见的有逻辑与（AND或*）、逻辑或（OR或＋）、逻辑非（NOT或-）。逻辑表达式：也叫布尔逻辑表达式，利用布尔代数中的逻辑运算符来描述检索词间的关系，把检索词连接起来，为检索式搭起框架，指定检索词出现或不出现的条件。6.3.2检索表达式6.3.2.1逻辑表达式构造容易，便于理解可以表达和用户思维习惯相一致的查询要求，与计算机逻辑运算功能一致，表达意义比较明显直观不能实现检索结果的相关性排序不能反映表达式中检索词的重要性如果用户的检索课题中涉及的检索词较多，可能写出一个相当复杂的表达式。6.3.2检索表达式6.3.2.2加权表达式加权检索：是指在检索提问中，根据每个检索词在检索要求中的重要程度，分别给予一定的数值加以区别，即赋权，这个数值就是权值，然后对含有这些检索词的信息进行加权计算，其和在规定的阀值以上的，即确定为命中信息。例如：中国（5）高等教育（5）发展趋势（5）阀值W＝156.3.2检索表达式6.3.2.3检索表达式中的位置算符位置算符：表示所连接的各个检索词间位置关系的符号，它的作用是对复合检索词进行加工修饰，限制词与词间的位置关系，弥补布尔逻辑算符只是定性规定检索词的范围，提高查准率。不同的检索系统中采用的位置算符通常有差异。常见的有（W），（nW），（N），（nN），（S），（F），（C），（L）等。6.3.2检索表达式6.3.2.4检索表达式中的截词符截词符：对单元检索词进行加工修饰，解决检索词的单、复数问题，词干相同而词尾不同以及英美词汇拼写差异问题等。常用的有“*”，“?”，“$”。截词按截断的词量分为有限截断和无限阶段。按截断形式分有左截断（后方一致）、中截断（任意一致）和右截断（前方一致）。有限截断是检索词串与被检索词实现只能在指定位置可以不一致的匹配。常用“？”表示。无限截断是检索词串与被检索词实现部分一致的匹配，常用“*”表示。6.3.2检索表达式6.3.2.4检索表达式中的限制符限制符：限制检索词或表达式在数据库记录中出现的字段位置。数据库中可供检索的检索字段有题名（TI），文摘（AB），主题词（DE）和标识词（ID），主题词（SU），作者（AU），语种（LA），出版年代（PY）、刊物名称（JN），文献类型（DT）等。限制符在不同的数据库中有不同的表达形式和使用规则。6.3.3检索策略的构造步骤1.分析信息需求2.选择检索系统3.选择检索途径和方法，确定检索词，构造检索表达式4.处理检索结果5.获取原始信息6.3.3检索策略的构造步骤6.3.3.1分析信息需求，明确检索要求信息需求的类型：新、全、准。所需要的信息类型：数据、事实还是文献。所需要信息的目的：科学研究、生产、生活等所需要信息的格式：数字的、印刷的…………6.3.3检索策略的构造步骤6.3.3.2选择检索系统6.3.3.3选择检索途径和方法，确定检索词，构造检索表达式6.3.3.4处理检索结果6.3.3.5获取原始资料例如：构造有关“造纸废水的处理技术”的检索表达式。抽取检索词：造纸：papermaking，paperpulp；废水：wastewater；处理：treat，treatment。构造检索表达式：（paperwmakingORpaperwpulp)ANDwastewaterAND(treatORtreatment)6.3.4检索策略的反馈与调节6.3.4.1影响查全率和查准率的主要因素主题的分析检索词检索词间的逻辑关系6.3.4检索策略的反馈与调节6.3.4.2提高查全率和查准率的方法1.

提高查全率的方法降低检索词的专指度；可从词表中选上位概念或检出信息中的相关词补充到检索式中进行族性检索，可采用分类号检索或采用一组近义词或同义词或相关词OR连接在检索式中进行截词检索，可采用后截断、前截断、前后截断等截词方法增加和调整检索途径调节检索式的网络度，如删去某个不重要的概念面取消某些限制过严的检索条件，如年代、语种、文献类型等6.3.4检索策略的反馈与调节6.3.4.2提高查全率和查准率的方法2.

提高查准率的方法提高检索词的专指度，增加或换用下位词和专指性较强用AND连接一些进一步限定主题概念的相关检索项，增加相互制约利用NOT限制与信息提问不相关信息的输出，减少检索噪音利用限制符，限制检索词出现的可检字段，用位置符控制检索词的词间顺序和位置进行加权检索，从定量角度加以控制对检索结果的外部特征进行限制，加强针对性进行二次检索，或对检索结果进行后处理，如聚类、挖掘等。信息检索步骤的流程图：明确用户需求，分析主题选择信息检索工具或数据库确定检索词构造检索表达式提交检索表达式显示与优化检索结果获取原始信息满意修改表达式不满意修改检索词重新选择工具再次确定用户需求6.4信息检索技术6.4.1书目数据库的检索技术6.4.1.1书目数据库的结构

书目数据库主要来源于期刊论文、会议论文、研究报告等一次文献，结构简单、数据量大，连续性积累性强。主要用途是联机检索服务。主要有文摘索引DB和图书馆书目DB是以文档的形式组织起来的，文档的基本组成单位是记录。6.4.1.1书目数据库的结构

记录(record)是作为一个单位来处理的有关数据的集合，是对某一实体的属性进行描述的结果。在书目数据库中，被描述的实体是某一特定的文献，实体的属性就是该文献的持征。

字段（field）是记录的下级数据单位，用来描述实体的某一属性。在书目数据库的记录中，字段的划分与文献著录事项的划分相一致，一个字段与一个著录项目相对应。每个字段的具体内容称为字段值（fieldvalue)或属性值（attributevalue）。1.记录与字段6.4.1.1书目数据库的结构逻辑记录：由应用程序员根据需要，把某些逻辑上相关联的数据组织在一起的数据集合称为逻辑记录，简称记录。物理记录：是指硬件设备上的一个基本存贮单位，亦称为“块”。随着设备的不同，物理记录有不同的固定类型和长度。一个物理记录可含有一个或多个逻辑记录，而一个逻辑记录也可能存放在一个或几个物理记录中。物理记录是内外存之间进行数据交换的基本数据单位。2.逻辑记录与物理记录6.4.1.1书目数据库的结构（sequentialfile）全部记录按顺序存放，记录的物理位置通常由记录的键值决定，记录之间的逻辑顺序与物理顺序一致。又称为链式文档或线性文档。这种存贮方式决定了对记录的存取只能顺序进行。它使记录之间紧密排列在一起。文档的修改和删除操作简单，但插入操作麻烦，存取时间与数据的物理位置有关。3.文档——（1）顺序文档6.4.1.1书目数据库的结构是相对顺序文档的另一种存贮方式。文档中的记录按随机方式存放在支持直接存取的磁盘、磁鼓或内存中。在记录的关键码与存放该记录的地址之间建立某种关系，根据这种关系来确定该记录在文档中的位置以及对文档进行存取的方式。它的待点是：对记录可以随机存取，不考虑记录在文档中的排列次序。3.文档——（2）随机文档6.4.1.1书目数据库的结构3.文档——（3）主文档masterfile：每条记录以线性形式存放，都包含了对应信息的所有字段，检索时，只能按其物理顺序读取这些记录及其中的字段。外购、合建或自建数据库经过格式转换（转换成标准格式或本联机系统内部格式）构成检索系统的主文档。主文档的记录为可变长记录，一般采用紧密无间隙地组织和组块方式存贮，并建立相应的主文档索引（masterfileindex，简写MX），即主文档的索引文档，指明每条记录在磁盘中的存贮起始位置。MX中的数据结构为：存取号地址指针6.4.1.1书目数据库的结构（invertedfile，IF）就是把记录中一切可检字段或属性值等抽出，按某种顺序重新加以组织后所得到的一种文档。既可以按不同类型的宇段组成不同的倒排档(如著者倒排档、主题词倒排档等)，也可以把所有不同的字段组成一个混合倒排档。MF和IF主要区别是：MF以文档的完整记录为处理和检索单元，IF则以文献的属性（即记录中的可检字段）为处理和检索单元。IF是从MF中派生出来的一种文档。3.文档——（4）倒排文档例子：现有一个文献集合001专家系统在信息检索中的应用（标引词：专家系统；智能检索系统）……002一种新的倒排档溢出处理算法（标引词：倒排档；溢出处理）……003信息检索专家系统的特点与发展（标引词：专家系统；智能检索系统）……004提问式中的位置算符（标引词：提问逻辑式；位置算符）……005提问式准波兰变换算法的研究（标引词：提问逻辑式；准波兰变换）……006智能检索系统的设计与开发（标引词：智能检索系统）……用“＃”作为记录分隔符，上面6个信息的主文档如下：

001专家系统在信息检索中的应用＃002一种新的倒排档溢出处理算法＃003信息检索专家系统的特点与发展＃004提问式中的位置算符＃005提问式准波兰变换算法的研究＃006智能检索系统的设计与开发对应的主题倒排文档如下：倒排档002提问逻辑式004，005位置算符004溢出处理002智能检索系统001，003，006专家系统001，003准波兰变换0056.4.1.1书目数据库的结构由于主文档中每条记录含可检字段很多，建成的倒排文档很大，且其中每个检索键（Key）所带的记录号个数不等，所以可建立一种随机文档，采用定长的记录格式，但这样做又浪费了空间。折中的做法是将倒排文档中的检索键和记录号分开处理。用一个文档单独存贮各种检索键，称为“词典”文档（IX），按随机方式存贮。其数据结构如下：Keynp3.文档——（5）“词典”文档p为地址指针，指向相应的倒排文档记录的相对地址。记录号字段代号句编号词编号记录个数Keynp另为词典文档建一顺序文档存贮与检索键对应的记录号集合，仍称为倒排文档（IF），它的数据结构为：Key为检索键的值，如“著者名、主题词、分类号等”。n为出现的频率，即有关的记录个数。KEY13p1KEY22p2KEY3n3p3………………KEYmnmpm字典文档（IX）词典文档的倒排文档（IF）……检索系统中各文档之间的关系检索词IX检索词在IF中的地址指针IF命中信息在主文档中的地址MF命中信息MX记录号词表文档相关词以“智能检索系统”为例：第一步：先利用词典文档获取指针：智能检索系统3011111第二步：利用指针从词典文档的倒排文档中获取记录号：记录号字段代码………………………………001003006……第三步：利用记录号访问主文档的索引文档即MX，获取各记录号对应的物理地址；001物理地址n003物理地址m……………………006地址p第四步：利用记录号对应的物理地址从主文档中获取完整记录。6.4.1.2顺序文档的检索技术最早由日本人菊池敏典提出，将文档中的每一条记录依次匹配用户的检索提问集合，处理完后，将各提问的命中结果归并分发给用户。即用文档中记录一条一条去匹配提问。主要方法有：1.表展开法表展开法的关键技术是采用列表处理方法将提问逻辑式(检索式)变换成等价的提问展开表，按提问展开表的内容对顺排文档的每篇文献进行检索。2.树展开法6.4.1.2顺序文档的检索技术提问式Q＝（（A＋B＋C）*D＋E）*F的展开表地址条件满足指向条件不满足指向级位检索词代号检索条件所属字段检索词14221略A24323略B34515略C46517略D56不命中09略E6命中不命中011略F6.4.1.2顺序文档的检索技术检索提问式（A＋B）*（C＋D）＋E*F树展开法顺序文档的检索技术——表展开法（1）提问的编辑(表展开法)例如要检索计算机信息检索方面1985—1990年间出版的文献资料，该课题的检索词表及提问逻辑式的形式可如下：检索词代号所属字段截断说明比较条件检索词165011情报265011计算机365011检索42603319855260341990顺序文档的检索技术——表展开法（1）提问的编辑(表展开法)“所属字段”栏用来说明检索词属于哪个字段，“截断说明”栏可用代码表示检索词截断的类型，如：1一不截断(完全一致)；2—后截断(前方—致)；3——前后截断(中间一致)；4——前裁断(后方一致)“比较条件”栏也可用代码表示：1——相等；2一不相等；3——大于；4——小于有了检索词表以后，就可以根据各检索词之间应有的逻辑组配关系，用检索词代号构成一个提问式。本例的提问逻辑式如下：Q＝1*2*3*4*5顺序文档的检索技术——表展开法（2）提问展开表的定义表展开法是将每个提问逻辑式列成提问展开表。一个提问式转换成一张表，有N个提问式就可做成N个提问展开表。所谓展开表，就是由检索词及其代号、条件满足指向、条件不满足指向、级位等栏构成的一张表。一个检索词对应表中的一行。提问表最多允许20行。顺序文档的检索技术——表展开法（2）提问展开表的定义地址条件满足指向条件不满足指向级位检索词代号检索条件权值检索词提问展开表的结构顺序文档的检索技术——表展开法（2）提问展开表的定义地址——按自然数顺序编排，用以表示检索词地址；条件满足指向——指当文献记录的标引词与提问式的检索词一致时，下一个应比较的检索词的地址；条件不满足指向——指当文献记录的标引词与提问式的检索词不一致时，下一个应比较的检索词的地址；级位——当前检索词在提问式中的层次级别；检索词代号——检索词在提问式中的编号；检索条件——有截断说明、比较条件等；权值——进行加权检索时，指定的检索词的权值；检索词——提问逻辑式中的提问项目。顺序文档的检索技术——表展开法（3）提问展开表的形成以Q＝（（1＋3＋5）*7＋9）*11为例子，1、3、5、7、9、11分别代表检索词A、B、C、D、E和F。假设提问式已形成检索词表。顺序文档的检索技术——表展开法（3）提问展开表的形成逐个扫描逻辑式的字符，将提问式的字符一一依次取出，再进行如下判断：若是数字(即检索词代号)，则将对应的检索词的有关内容由检索词表移入展开表内。若是“+”号，把提问式中下一检索词的地址(即表中下一行的地址)置入该“+”号左边检索词所在行的“条件不满足指向”栏；若是“*”号，把提问式中下一检索词的地址(即表中下一行的地址)置入该“*”号左边检索词所在行的“条件满足指向”栏。第一个检索词的级位的初值为零，以后每一个检索词的初始级位由上一个检索词复制得到，然后再根据条件加减。若检索式的第一个符号是左括号，则将第一个检索词做加级运算。顺序文档的检索技术——表展开法（3）提问展开表的形成若是“(”，则将其前一检索词所在行的级位值加1，放入其后的检索词所在行的“级位”拦，同时有多层左括号时，级位值连续加1多次。若是“)”，则将紧前一个检索词所在行的级位值减1，同时有多层右括号时，级位值连续减1多次。若是“.”句号，位提问式结束标志，则在前一检索词（即式中最后一个检索词）所在行的“条件满足指向”栏放入“命中”，“条件不满足指向”栏放入“不命中”。顺序文档的检索技术——表展开法（3）提问展开表的形成地址条件满足指向条件不满足指向级位检索条件所属字段检索词1略略A2略略B3略略C4略略D5略略E6略略F2210023456命中不命中Q＝（（A＋B＋C）*D＋E）*F1顺序文档的检索技术——表展开法（4）提问展开表的后处理通过比较展开表中“级位”栏内各行级位值的大小，从最后一个检索词开始反填表的第2、3栏：若K1行的级位值大于K2行（上一行为K1，下一行为K2）：若K1行的“条件不满足指向”栏（简称第3栏）空着，则表示K1*K2，应把K2行第3栏内容复制到K1行第3栏；若K1行“条件满足指向”栏（简称第2栏）空着，则表示K1＋K2，把K2的行的第2栏内容复制到K1行的第2栏；顺序文档的检索技术——表展开法（4）提问展开表的后处理若K1行的级位值等于K2行若K1行的第3栏空着，则表示K1*K2，应把K2行第3栏内容复制到K1行第3栏；若K1行第2栏空着，则表示K1、K2之间是＋运算，唯有遇到右括号或结束符时候才能得知满足后的处理。所以应当把K1检索词后的第一个右括号或者结束符前的检索词所在行的满足栏内容复制到K1的满足栏。顺序文档的检索技术——表展开法（4）提问展开表的后处理若K1行的级位值小于K2行，则表示K1之后是左括号，应将该左括号至其对应右括号后出现的第一个“＋”或结束号之间的内容作为一个复合检索项。若K1行第3栏空着，则把K1行下面第一个与其级位相等行或第一个小于K1行级位值的行的第3栏内容复制到K1行第3栏中。若K1行第2栏空着，则把K1紧后一个复合检索项中最后一个检索词所在行的第2栏内容复制到K1行第2栏中。顺序文档的检索技术——表展开法（4）提问展开表的后处理地址条件满足指向条件不满足指向级位检索条件所属字段检索词122略略A232略略B341略略C451略略D560略略E6命中不命中0略略F不命中①6②5③4④4⑤顺序文档的检索技术——表展开法（4）提问展开表的后处理最终结果得到的展开表如下：地址条件满足指向条件不满足指向级位检索词代号检索条件所属字段检索词14221略A24323略B34515略C46517略D56不命中09略E6命中不命中011略F顺序文档的检索技术——表展开法（5）表展开法对逻辑“非”的处理具有逻辑“非”的提问式展开表的生成，主要依据下述三条原则：①逻辑“非”先按逻辑“与”展开得到展开表；②当“非”项为单项时，该项的“条件满足指向”与“条件不满足指向”两栏内容互换；③当“非”项为多项式时，各项的“条件满足指向”与“条件不满足指向”两栏中关于“命中”和“不命中”的内容作反项转换。顺序文档的检索技术——表展开法（5）表展开法对逻辑“非”的处理例子：求A－（B－C＋D）的展开表。第一步：先求A*（B*C＋D）的展开表，如下。地址条件满足指向条件不满足指向级位检索词12不命中0A2341B3命中41C4命中不命中0D顺序文档的检索技术——表展开法（5）表展开法对逻辑“非”的处理例子：求A－（B－C＋D）的展开表。第二步：C项的“条件满足指向”与“条件不满足指向”两栏内容互换。地址条件满足指向条件不满足指向级位检索词12不命中0A2341B34命中1C4命中不命中0D顺序文档的检索技术——表展开法（5）表展开法对逻辑“非”的处理例子：求A－（B－C＋D）的展开表。第三步：B、C和D的“条件满足指向”与“条件不满足指向”两栏中关于“命中”和“不命中”的内容作反项转换。得到最终结果如下：地址条件满足指向条件不满足指向级位检索词12不命中0A2341B34不命中1C4不命中命中0D顺序文档的检索技术——表展开法（6）课堂练习求A*(B+C)+(D*(E+F*G))的展开表。地址条件满足指向条件不满足指向级位检索词1240A2命中31B3命中40C45不命中1D5命中62E67不命中2F7命中不命中0G顺序文档的检索技术——表展开法（7）表展开法的优点①.凡是可不查阅的文献属性(即字段)一定不查。即对具体的提问，只在检索词本身所在的属性范围(如关键词、标题、著者、年代等)内查找；②.凡是可不再查阅的检索词一定不再查。即在“条件满足指向’栏中一旦遇到“命中”，或“条件不满足指向”栏中遇到“不命中”，可立即停止关于下面检索词的查阅，而不一定要求把提问式所有检索词都一一查阅。顺序文档的检索技术——表展开法（8）表展开法的缺点①.表展开算法的效率在某种程度上依赖于原提问逻辑式的书写。例如：原提问式为A*B，假如A是高频词(即很多文献都含有A)B是低频词(即很少数文献含有B)，则提问式A*B的展开表不如提问式B*A的展开表检索效率高。因为由B*A得到的展开表，将首先在文献中查找检索词B，在大多数文献不满足B的前提下，可省去查找匹配检索词A的过程。②.在实际的定题批式检索中，很多提问中往往含有许多相同的检索词。由于每个提问都要与主文档进行匹配处理，因此一批提问中这些相同的检索词，和同一篇文献要重复匹配处理多次。6.4.1.3倒排文档的检索技术1.福岛方法（逆波兰变换法）最初由日本人福岛提出，故又称为福岛方法。这种方法的处理要点是：先将提问逻辑式转换成逆波兰表示形式，然后将逆波兰表示形式翻译成一组检索指令。在书写算术表达式时，将运算符放在运算项的后面，如(A＋B)*C表达式为AB+C*，人们称这种表示法为后缀表示法或逆波兰表示法。运算时，只需从左向右扫描表达式，遇到运算项时，就把它保存起来，遇到运算符时，就取出其前面紧接的两个运算项进行运算处理，并把结果当作一个新的运算项保存起来，再继续向右检查表达式的其它符号，直至结束。一般表示法（中缀法）正波兰（前缀）表示法逆波兰（后缀）表示法A＋B*C＋A*BCABC*＋(A+B)*(C+D)*+AB+CDAB+CD+*A/(B*C)+D*(E-A)*C+/A*BC**D-EACABC*/DEF-*C*+三种表示方法的比较检索表达式的逆波兰变换处理：首先需要在计算机内存中设置以下三个工作区域：逆波兰输出区、算符栈、检索词表。其中逆波兰输出区存放经过变换后的提问式算法栈是一个先进后出的表，是形成逆波兰变换处理的临时堆栈，主要借助它来重新排列运算符，以便调整、确定表达式中各种运算的先后顺序检索词表则是提问式中的检索词表，这样，在逆波兰输出区可以使用检索词表中的地址编号来代替运算项的检索词算符优先级）1＋2×3－4（5/1（入栈/栈内）逆波兰变换处理中算符的优先级别表检索表达式的逆波兰变换处理：从左往右扫描提问式的字符。如果是检索词，则将其置入检索词表中，并将相应的词表地址送入逆波兰输出区中如果是运算符＋、×，－，则将它与算子栈栈顶的那个算符按优先级进行比较，若比栈顶算符优先级高，则把它压入栈内，若相等或者低于栈顶算符的优先级，则取出栈顶算符，转送入逆波兰输出区，然后再与新的栈顶算符进行优先级比较，以此类推。如果是右括号，则表示该右括号与之匹配的左括号之间的所有运算都要执行。这时应该从算子栈按先进后出的次序将这对括号内的算符都依次取出，移入到逆波兰输出区。如果是结束标记，则将留在算子栈内的算符按后进先出的次序全部移入到逆波兰输出区。6.4.1.3倒排文档的检索技术2.准波兰变换法是对逆波兰进行改进，得到一个检索时只需要内存工作区个数最少的后缀表达式变换方法。基本原理：根据表达式二叉树的定义，任何一个算术表达式都可以用一棵二叉树来表示，其中，表达式的运算项为二叉树的叶子节点，运算符为二叉树的根或子树的根结点。准波兰的处理过程：创建检索表达式的二叉树表示；比较二叉树中每一层上的左右子树是否对称，如果不，把大的一枝保留或调整到左边，小枝保留或调整到右边，直到全部结点的左右子树都这样处理完后续遍历该二叉树，结点的输出序列即为该表达式的准波兰式3.析取范式变换法基本原理：通过改进提问式的书写来改善内存工作区的使用状况，其理论依据是“任一布尔逻辑检索式都可以化为与之等价的析取（或合取）范式”。所谓析取范式，它满足三个条件：式中只允许出现三种基本布尔