倒排文档检索中逆声波转换的实现

倒排文档检索中逆声波转换的实现

随着信息技术的不断发展和信息安全技术的不断创新和完善，。其中布尔逻辑检索技术最为突出,它可以根据不同的信息检索服务采用不同的实现方法,目前采用最多的是适用于倒排文档全文检索的逆波兰检索技术。所谓倒排文档全文检索,就是建立由检索词和与其对应的源文献编号所组成的倒排索引文档,根据检索算式,将所求文献编号集合进行逻辑运算(包括或、与、非等),最后根据所得文献编号结果集合从主文档中读出命中文献的全文信息。在倒排文档全文检索中常采用“逆波兰”检索算法(福岛算法)。该算法分为两步:①将检索算式转化为“逆波兰式”。“逆波兰式”是将一般的逻辑提问式处理为除去括号并严格地按“由左向右”运算地后缀表达式;②检索指令表的生成。上述检索算法的关键在于“逆波兰式”的生成。本文重点讨论逆波兰转换“堆栈”算法及“二叉树”算法分析及程序设计,比较两者不同点,使读者对逆波兰转换的实现有一个清晰的认识。鉴于Foxpro数据库管理系统具有很强的数据管理功能和语法简洁的程序设计能力,数据独立性好,现已广泛地应用于图书情报领域,是信息检索系统的主要开发工具之一。本文讨论的逆波兰转换“堆栈”算法与“二叉树”算法的程序设计均在Foxpro平台下实现。1存储数据存取堆栈是一种重要的线型数据结构,它提供一组线型的数据存储空间,并规定所有数据的存取只能在栈顶进行,遵循“先进后出”的存取原则。在逆波兰转换“堆栈”算法中,我们使用堆栈作为该算法的核心数据结构,最基本的运算均围绕堆栈进行。1.1数据结构转换要实现该算法,首先要设计该算法所使用的数据结构,也就是“逆波兰”转换工作区与存储区。在算法中,所采用的数据结构均为线型结构(包括堆栈),使用三个存储区。(1)建立一维两组该存储区用于存储检索表达式,可以根据检索算式的长度建立一维数组,也可以使用Foxpro中的字符串变量(char)。进行转换时,扫描一维数组或逐个截取字符串变量中的字符。(2)逆波兰转换算子栈该算子栈用于暂时存储检索算式中的运算符,即将检索算式中的运算符压入算子栈顶,当满足一定条件后,再将运算符从算子栈顶逐个弹出。该算子栈是逆波兰转换的核心数据结构,可以使用1维数组来构造,以数组已经存储数据的最大下标表示栈顶,实现运算符的堆栈操作。算子栈是整个算法中真正的工作区,在该堆栈中进行数据的存储与读取,以实现逆波兰转换。(3)下标标记运算符该输出区用于存储检索算式转化的最终结果“逆波兰式”。可以使用二维数组来组织该输出区:1维下标标记运算符与检索词总数;2维下标定义为常数2。其中第1单元存储区别标志:1、2、3、4、5分别表示检索词、“·”“+”“*”“-”运算符,便于计算机对“逆波兰式”扫描生成检索指令表;第2单元存储提问检索词或运算符。这里仅讨论逆波兰转换问题,因此可以省略第1单元。1.2逆波兰转换规则的程序设计假定在检索算式中仅存在“-”(本文中作为双目运算符,“不包含”而不是“非”。例:A-B指的是A中不包含B,这样将所有运算都转换为双目运算,便于程序设计),“+”(或),“*”(且),“(”,“)”以及“·”(结束)等运算符,则逆波兰转换堆栈算法的基本思想如下所示。(1)首先设定运算符的运算优先级别。在这里,设定“*”,“+”,“-”,“(”,“)”以及“·”的优先级从高到低,取值分别是3、2、2、1,1和0。(2)扫描检索算式,得到检索词,则在“逆波兰式”输出区中无条件输出。(3)扫描检索算式,得到“-”,“+”,“*”等运算符,则在算子栈顶比较运算符。若当前得到运算符的优先级高于算子栈顶运算符,则将当前运算符送入算子栈(入栈)中作为栈顶运算符;若优先级不高于(包括等于)栈顶运算符的优先级,则将栈顶运算符从栈顶取出送往“逆波兰式”输出区,当前运算符再与栈顶运算符比较,重复前面过程。(4)扫描检索算式,得到开括号“(”,表示其后存在复合检索项,将此开括号无条件置入算子栈顶;若得到的是闭括号“)”,则表示复合检索项结束,与其相对应(算子栈中离栈顶最近)“(”之间所有运算符都可以组成运算,将这些运算符依次出栈,送入“逆波兰式”输出区,并舍弃“(”和“)”。(5)若遇到检索算式结束号“·”,则将算子栈内所有运算符依次送入“逆波兰式”输出区。上面论述的是“堆栈”算法中逆波兰转换规则。根据这些规则,即可以进行程序设计。需要注意的是:本文中规定若算子栈中为空,当前运算符无条件进入算子栈,作为栈底元素。1.3ss的标记转换根据前面所介绍的数据结构设计以及“堆栈”算法规则分析,可以使用Foxpro语言来完成程序设计。程序设计流程如下所示。(1)分配存储空间,设定工作区,定义所需的变量并初始化。按照前面的数据结构设计,共定义一个存储空间:stringSS,字符串变量,作为检索算式存储区;R(N,1),一维数组,作为“逆波兰式”输出区(这里仅输出字符,不考虑字符类型)。一个工作区:S(A,2),二维数组,作为算子栈,其中增加的第2单元用于存储相应运算符的运算优先级。此外,除A、N等数组维数变量,还定义了L、i、ss,yxj、flag等变量,其中,L为stringSS长度,i为计数变量初值为1,ss为stringSS中截取的每一个字符变量,yxj表示运算符的运算优先级,flag用作标记符,标记前一个字符是否是运算符。(2)使用Foxpro中的For循环,对stringSS字符串进行逐个字符扫描,对截取的每一个字符SS进行条件分支判断(DOCASE语句,下面(3)～(10)为分支);循环结束(i>L),执行(11)。(3)若ss为“(”(casess=”(”),设置yxj=1,A=A+1,将字符和优先级存入S数组中,并使flag=0,表示当前字符属于运算符。(4)若ss为“*”(CaseSS=“*”,设置yxj=3,执行(7)。(5)若ss为“-”(casess=“-”),设置yxj=2,执行(7)。(6)若ss为“+”(casess=“+”),设置yxj=2,执行(7)。(7)循环比较yxj与算子栈(S数组)中已有元素的优先级(S(A,2)),即当A>=1andyxj<=S(A,2)时,令N=N+1,R(N)=S(A,1),A=A-1。循环结束后,A=A+1,将ss和yxj存入S数组中,并使flag=0。(8)若ss为“)”(casess=“)”,设置yxj=1,循环比较yxj与算子栈(S数组)中已有元素的优先级(S(A,2)),当A>=1andyxj<S(A,2)时(即还没有在算子栈中遇到”(”运算符),N增1,将S(A,1)赋值给R(N),并使A减1。循环结束后,A=A-1(退栈),并使flag=0。(9)若ss为“·”(casess=“·”),设置yxj=0,使用计数变量递减的For循环将S数组中的元素依次赋值给R数组,N依次递增。最后将结束符“·”也赋值给R(N),令flag=0。(10)若ss不是运算符(OTHERWISE),即ss为检索词字符,此时又分为两种情况,可以使用IF……ELSE…ENDIF分支语句。若flag=0(即前一字符为运算符),在R(N)数组中,用新元素存储该字符,即令N=N+1,R(N)=ss;若flag=1(即前一字符为检索词),在R(N)数组中,下标N不移动(不变),表示用原元素存储该字符,即令R(N)=R(N)+ss。最后令flag=1。(11)将R数组中所有字符元素依次输出,即可以显示原检索算式相应的“逆波兰式”;至此,逆波兰转换结束。上述整个程序流程如下图1所示。2“逆波兰”的形式逆波兰转换可以使用堆栈数组实现外,还可以使用二叉树的数据结构来完成。以二叉树的叶结点表示检索词,而中间结点和根结点表示运算符,则普通检索算式可以由某二叉树的中序遍历结果来表示,该二叉树的后序遍历结果即为该检索算式的“逆波兰”形式。根据这一思想,可以先将检索算式转化为某二叉树结构,即指定检索算式中运算符的左右子结点,再后续遍历该二叉树,即可得到相应检索算式的逆波兰形式。2.1数据结构的设计在“二叉树”算法中,也需要三个转换工作区与存储区。(1)创建具有落实内部点的二叉树创建二叉树可以使用两种方法:指针结构和数组结构。Foxpro语言不支持指针,因此在Foxpro程序设计中只能采用数组结构来创建二叉树。设计一个二维数组表,记录表示结点,每一记录可以包括六个单元,分别表示结点编号、结点类型(用1表示运算符结点(根结点和中间结点),0表示检索词结点(叶结点))、左子结点编号、右子结点编号、结点内容、运算符根优先级。不难得到,该二维数组表中“左右子结点编号”单元内容的设定过程即为二叉树的创建过程。(2)在搜索状态下，存储区域与“反向波兰公式”输出区之间这两个存储区作为逆波兰转换的数据输入与输出区,其结构同“堆栈”算法。2.2“二叉树”算法分析正如前面所说,该算法分两步进行,具体如下所示。(1)创建用于二叉树根控制的点火在该算法中,二叉树的生成是其中最重要也是最复杂的部分,逆波兰表达式能否顺利生成,这是关键的核心模块。具体过程如下:①规定在检索算式中仅存在“+”,“-”,“*”,“(”,“)”等运算符,根据表达式运算优先级,先做“(”、“)”运算,后“*”运算,最后“+”、“-”按顺序运算。再结合二叉树结点中序(根)遍历结果即为检索算式这一特点,得知在二叉树中优先级高的运算符应该在优先级低的运算符左下方。因此二叉树根结点首先应该是检索算式中最后出现的“+”或者“-”运算符,如果不存在“+”或“-”运算符,则是最后出现的“*”运算符,而“(”、“)”运算符不出现在逆波兰表达式中,虽然存储在结点存储区中,并不作为二叉树结点,因此上述运算符的根优先级可以分别设为是3,3,2,1,-1,检索词的根优先级则设为0。②扫描检索算式,初步创建结点存储区数组,填入结点编号、类型、内容以及根优先级等单元的值。③扫描结点存储区,根据根优先级顺序,先寻找括号外最后出现的“+”或“-”作为二叉树的根结点;如果没有,则寻找括号外最后出现的“*”作为二叉树的根结点;如果也没有,则寻找“(”,将“(”与其相应的“)”之间的结点集合作为新的结点存储区,重复③的过程;如果连开括号“(”都找不到,则只剩下检索词,此时,返回该检索词所在结点的结点编号。④找到作为二叉树根结点的运算符后,将比根结点编号小的结点集合作为该根结点的左子树,而比根结点编号大的结点集合作为该根结点的右子树,将左右子树分别作为新的结点存储区重复③的过程,将返回的左右子树根结点编号,填入原根结点记录相应位置。根据上面的算法过程,最终可以生成二叉树,以结点存储区数组形式存在。上面的算法采用了递归方法,即不断调用本身,直到满足某一条件为止。由于二叉树的概念是通过递归定义的,因此有关二叉树数据结构的问题可以通过递归方法方便予以解决。(2)叉树的根控制检索算式的二叉树生成之后,只需后序(根)遍历该二叉树,所得到的算式即为原检索算式的逆波兰形式。在这里可以使用两种算法:①常规循环方法。即先找到二叉树中最左下角叶结点(结点存储区中第一个检索词)作为二叉树后序(根)遍历的起始点,再寻找该结点的父结点(左子结点编号为该结点的结点),这样就可以找到起始结点的兄弟结点(右子结点编号),将此三个结点按左右中(父)顺序存储到“逆波兰式”输出区中即可。然后以父结点作为起始结点重复上述过程,直到起始结点为整个二叉树的根结点(在创建二叉树时应该有所记录)为止。②递归方法。从二叉树的根结点出发,先遍历该根结点的左子树(编号比根结点小的结点存储区),再遍历该根结点的右子树(编号比根结点大的结点存储区),最后遍历该根结点(输出到“逆波兰式”输出区);而在遍历左右子树(子树根结点在根结点记录中得到)时又采用上面的三步曲:左右中(根),直到结点没有子树(叶结点)为止,输出该叶结点到“逆波兰式”输出区。比较上述两种后序遍历方法,常规循环方法思路清晰,理解方便,但算法繁乱,程序设计困难:相反递归方法自我调用,层层递进,不易理解,但迎合二叉树的结构特点,程序设计上简单。2.3“二叉树”算法的编程方法有上面数据结构设计和算法分析作为基础,就可以进行程序设计了。该程序分为四个部分。(1)生成控制函数主程序显示二叉树算法程序的总体结构:①为结点存储区W(J,6)、“逆波兰式”输出区R(N,1)(R与N均定义为全局变量)、检索算式存储区stringSS以及所需要的变量(J,M,L,flag,i,N等)分配空间并赋初值。②扫描stringSS,为W(J,1)、W(J,2)、W(J,5)以及W(J,6)的内容赋值,M为结点存储区记录个数。③二叉树根结点变量G=二叉树创建函数(1,M)。④后序遍历二叉树函数(G)。(2)ss的结构生成该模块可以放在主程序中,也可以另外定义函数,再由主程序调用,具体过程如下所示:①使用For循环对截取检索算式中的每一个字符ss进行判断(SUBSTR函数)。②根据ss的不同值,进入分支结构(DOCASE)。对于运算符,J=J+1,W(J,1)=J,W(J,2)=1,W(J,5)=ss,Flag=0,再根据不同的运算符决定优先级W(J,6)的值;对于检索词,则需要判断Flag的值是否为1,是则W(J,5)=W(J,5)+ss,不是则上J+1,W(J,1)=J,W(J,2)=0,W(J,5)=ss,W(J,6)=0,不管Flag的值是否为1,均设置Flag=1。③对于所有ss均执行②操作,直至计数变量i>检索算式的长度L。最后令M=J。(3)判断是否为真、有条件结果检查方式bintree(a,b)为二叉树创建函数,其中a,b分别为结点存储区上下限参数。根据前面的算法分析,具体的函数程序如下:①定义函数局部变量yxj,i,G,cz(标志括号层数);比较a与b的大小,如果a不小于b,则结点存储区中只有一个结点,返问该结点的编号a或b(a不可能人工b,除非检索算式不正确),执行⑩;否则,令yxj=W(a,6),i=a,G=a(条件初始化),执行②。②比较i与下界b的大小,如果i大于b,执行①;否则执行③。③判断W(i,6)是否等于1,是(遇到开括号)则令cz=1,执行④;否则执行⑥。④执行无限循环Dowhile.t,每次循环令i=i+i,如果此时W(i,6)=1orW(i,6)=-1为真,则令cz=cz+W(i,6);紧接着判断此时cz=0是否成立,如果成立(遇到相应的闭括号),执行⑤;否则执行④。⑤当判断i>=bandyxj=1为真时(整个检索算式是由括号括起来的复合式),令a=a+1,b=b+1(除去首尾括号),yxj=W(a,6),i=a,G=a(条件初始化);不管判断是否为真,都执行exit命令,强制退出无限循环,执行⑥。⑥当yxj<=W(i,6)成立时,令yxj=W(i,6),G=i;不论比较是否成立,均令i=i+1,执行②。⑦令W(G,3)=bintree(a,G-1),递归调用,参数为a与G-1,执行⑧。⑧令W(G,4)=bintree(G+1,b),递归调用,参数为G+1与b,执行⑨。⑨返回上下限分别为a,b的结点存储区(二叉树工作区)根结点G,执行⑩。⑩程序结束。上述过程可以用图2表示。(4)根控制结论在这里,使用递归方法代替循环方法,具体函数程序流程如下。①定义函数局部变量Le,Ri(左右子树根结点变量);判断当前二叉树根结点G是非运算符结点(二叉树叶结点),即W(G,2)=0,则将该结点送入“逆波兰式”输出区,即令N=N+1,R(N)=W(G,5),执行⑥;否则执行②。②取出根结点G的左右子结点(左右子树的根结点)编号,即W(G,3)与W(G,4)的值,令Le=W(G,3),Ri=W(G,4),执行③。③递归调用backlook(Le),以左子结点编号作为左子树的根结点参数。执行④。④递归调用backlook(Ri),以右子结点编号作为右子树的根结点参数。执行⑤。⑤将根结点G送入“逆波兰式”输出区,令N=N+1,R(N)=W(G,5),执行⑥。⑥程序结束。3对两种算法的对比通过对检索算式A+B*(C-D*EF)逆波兰转换过程的描述,使读者对上述两种算法有更加清晰的理解。图3通过图示的方法描述整个检索算式逆波