微型机情报检索系统《MCDS》中的新技术

D0I:10.13374/j.issn1001-053x.1984.04.006 北京钢领学院学报 1984年第4期 微型机情报检索系统《MCDS》中的新技术 软件工程教研室冯克清 摘 要 囿于微机系统的软、硬件配覆，尤其是外存容量过小，主机速度慢等条件，微机上的情报检索系统通常效率偏低。 本文介绍提高系统效率的一些新技术，特别是二叉分类树的严格倒排技术。并给出了实现算法。这些新技术已经 成功地用于《MCDS》之中。 一、问题的提出 微型机上的情报检索系统，其文件一般不能采取表格形式的倒排结构，也不宜采用索引 链接结构。较为适当的组织法应当是：主文件顺序组织，对各属性，则作索引树接。也就是 说，对各个属性，例如“作者姓名”，建立一个作者索引表，其中每个索引项是：作者姓 作者索引表： 始 " 张 根指针 张五 张三 1 E 张七山 下张大中 B 四中 G六 [张+e 张× 图1张姓作者的一棵索引树 66

北 京 铜 铁 学 院 学 报 年 第 期 微型机情报检索系统《 》 中的新技术 ’ 软件工 程教研室 冯 克清 摘 要 囿于徽机系统的软 、 硬件配置 ， 尤其是外存容 过小 ， 主机速度慢等条件 ， 微机上的情报检索系统通常效率偏低 。 本文介绍提高系统效率的一些新技术 ， 特别是二叉 分类树的严格倒排技术 。 并给 出了实现 算 法 。 这些新技术巳经 成功地用于 《 》 之中 。 问题的提出 微型机上 的情报检索系 统 ， 其文件一般不能采取表格形式的倒排结构 ， 也不宜采用索引 链接结构 。 较为适当的组 织法应 当是 主文件顺序组织， 对各属性 ， 则作索引树接 。 也就是 说 ， 对各个属性 ， 例如 “ 作者姓名” ， 建立一个作者索引表 ， 其中每个索引项是 作者姓 作者索引表 赵 浅 根指针 张五 张大 国国 张七 图 张姓作者的一棵索引树 DOI ：10．13374／j ．issn1001－053x．1984．04．006

名的压宿码（如取姓），以及主记录所在地址。这种索引表被作成定长的（如百家姓）， 有序的（如以姓氏笔划为序），从而适于折半查找。每个案引项中的地址，实际上是一棵 二叉分类树的树根地址。在主记录中，当然应有作者全名以及左右两个指针，以用来指示 较作者全名为“小”和“大”的作者所作文章（主记录）的物理位置。于是该系统所收集 ◆ 的文献，将按文献作者为准，全部组织在以作者索引表所指主记录为根的二叉分类树森林 之中。 这样处理索引结构的好处是明显的。例如按作者姓名作检索时，首先以姓为码，对索引 表作折半查找（速度很快），以找到树根位置，然后以作者全名为码，作二叉分类树查找 这较索引链接要快得多。 但问题是，当主文件记录越来越多时，装载主文件的软盘片也将一片片增加，而按通常 办法构造二叉分类树时，各盘片的主记录之间，在例如“作者姓名”上的联系将是杂乱无 章的。这样作的后果是：若按作者姓名查找时，将导至用户频繁地换盘（手工操作），这 对系统说来是不能忍受的。 问题之二是二叉分类树按其生成规则形成之后，一般是不平衡的，这也会严重影响系统 的效率。 二、构造严格倒排二叉分类树算法 《MCDS》采用了所谓严格倒排二叉分类树思想来解决二叉树的跨盘问题。方法的要旨 是：对一棵已知的二叉分类树，当我们要对其插入一个结点时，不是象通常的插入算法那 样插在树梢，而是将新插入结点当作树根，并将原树从根部起，逐节分解，最后重新拼接 成一棵新的二叉分类树。 这样构造二叉分类树好处有二，一是解决了跨盘问题：两片盘之间仅有一个单向联系， 二是十分符合情报检索的实际：最新侪报资料通常应当在索引树之根部。 先看一个二叉分类树倒排插之实例。图2.1是一棵已知的二叉分类树，图3是插入16以后 的新的二叉分类树。 20 20 ǖ入I6 图3 67

名的压宿码 如取姓 ， 以及 主记录所在地址 。 这种索引表被作成定长的 如百家姓 ， 有序 的 如 以姓 氏笔划为序 ， 从而适于折半查找 。 每个索引项中的地址 ， 实际上是一 棵 二叉分类树的树根地址 。 在主记录 中 ， 当然应 有作者全名以及左右两个指针 ， 以用来指示 较作者全名为 “ 小” 和 “ 大” 的作者所作文章 主记 录 的物理位置 。 于是该系统所收集 的文献 ， 将按文献作者为准 ， 全部组织在 以作者索引表所指主记 录为根的二叉分类树森林 之 中 。 这样处理索引结构的好处是 明显 的 。 例如按作者姓名作检索时 ， 首先 以姓为码 ， 对索引 表作折半查找 速度很快 ， 以找到树根位置 ，然后 以作者全名为码 ， 作二叉分类树查 找 这较索引链接要快得多 。 但间题是 ， 当主文件记录越来越多时 ， 装载主文件的软盘片也将一 片片增加 ， 而按通常 办法构造二叉分类树 时 ， 各盘片的主记录之间 ， 在例如 “ 作者姓名” 上的联系 将是杂乱无 章的 。 这 样作的后果是 若按作者姓名查找 时 ， 将导至用户频繁地换盘 手工操作 ， 这 对系统说来是不 能 忍受 的 。 问题之 二是二叉分类树按其生成规则形成之后 ， 一 般是不 平衡的 ， 这也会严重影 响系统 的效率 。 二 、 构造严格倒排二 叉分类树算法 《 》 采用 了所谓严格倒排二叉分类树思想来解决二叉树的跨盘间题 。 方法的要 旨 是 对一棵 已知 的二叉分类树 ， 当我们要对其插入一个结点时 ， 不是象通常的插入算法那 样抽在树梢 ， 而是将新插入结点 当作树根 ， 并将原树从根部起 ， 逐节分解 ， 最后重新拼接 成一棵新 的二叉分类树 。 这样构造二又分类树好处有二 ， 一 是解决了跨盘 间题 两 片盘之 间仅有一个单向联系， 二是十分符合情报检索的实际 最新情报 资料通常应 当在索引树之根部 。 先看一个二叉分类树倒排插之 实例 。 图 是一 棵 已知的二叉分类树 ， 图 是插入 以后 的新的二叉分类树 。 见。 ’ 。 矛 、 、 插 入 二 争 卜、 了 八 、 、 圈 图

二叉分类树倒插算法。 结点格式：NODE DATA LP TRP ① P=x,L=R=null,Q=根/并P,L,R,Q为指针，P指向新插入结点x,Q 指向原树之根：L,R用来记住左，右转折结点*/ ②IFQ=null THEN RETURN ③IFP<Q THEN P+RP=Q ELSE{P+LP=Q,GOTO⑤} ④L=Q, Q=Q-LP; IF Q=nu1l THEN RETURN, IF P<Q THEN GOTO④， IF R=null THEN P-LP=Q ELSE R-RP=Q L→LP=null ⑤R=Q5 Q=Q→RP, IF Q=null THEN RETURN, IF P>Q THEN GOTO⑤， IF L=null THEN P-RP=Q ELSE L-LP=Q R→RP=null GOTO④ 需要说明一点，以上算法仅适用于结点各不相同的场合。如欲使之适用于例如同一作者 写有多篇文章的情形，则可以将结点格式改成：NODE:DATA LP MP RP,其中MP用 来指明同一作者所写的另一篇文章（主记录），并且在倒插算法中也需作相应修改和扩充。 如此构成的累引树我们称之为“严格倒排三叉分类树”。一切有关的二叉（分类）树算法， 略加修改，均可适用于此种结构。三叉分类树明显地较二叉分类树效率为高，故《MCDS》 中实际使用的是三叉分类树。 三、二叉（或三叉)分类树平衡算法 不管是按通常算法还是倒插算法构成的二叉分类树一般是不平衡的，不平衡则会增加系 统开销。即使在初始建库时已设法将各二叉分类树搞成平衡，但随着系统的使用，旧文献 可能被剔除，新文献将源源加入。于是原本平衡的二叉树就不在平衡了，为此系统必须有 专门优化文件结构的功能，以便定期地将不平衡的二叉分类树改造成平衡的二叉分类树。 二叉分类树平衡算法。 它由以下两个算法构成： 1)中序走树法。一将二叉分类树变成线性有序表。 2)将线性有序表构成平衡的二叉分类树算法。中序走树算法及其特性请见有关参考资料， 68

二叉分类树例抽算法 结点格式 ① ， ， 根 ， ， ， ， 为 指针， 指向新插入 结点 ， 指 向原树之 根， ， 用来记住左 ， 右转折结点 开 ② ③ ， ， ， ⑤ ④ ， ， ， 多 ④， ， ， ， ， ⑤ ， ， ， ， ⑤， ， ， ， ， ， 丫 ④ 需要说 明一 点 ， 以上算法仅适 用 于 结点各不相 同的场合 。 如欲使 之适 用于 例如 同一作者 写 有多篇文章的情形 ， 则可 以 将结点格式改成 ， 其中 用 来指 明同一作者所 写 的另一篇文章 主 记 录 ， 并且在倒插算法 中也 需作相应 修改和扩充 。 如此 构成 的索引树我们 称之为 “ 严 格倒排三叉分类树” 。 一切有关的二叉 分类 树算法 ， 略加 修改 ，均 可适 用于此种结构 。 三 叉 分类树 明显 地较二叉 分类树效 率为 高 ， 故 《 》 中实际使用的是三 叉分类树 。 三 、 二 叉 或三 叉 分类树平衡算法 不管是按通常算法还是倒擂算法构成 的二叉分类树一般是不 平衡的 ， 不平衡则会 增加系 统 开销 。 即使 在初始建库时 已设法 将各二 叉分类 树搞成平 衡 ， 但随着系统 的使用 ， 旧文献 可能被剔除 ， 新文献将源源 加入 。 于 是原本平衡的二叉树就不 在平衡 了 ， 为此 系统必 须有 专门优化文件 结构的功能 ， 以便定期地 将不平衡的二叉 分类树改造成平 衡的二 叉分类树 。 二叉分类树平衡算法 它 由以下 两个算法构成 中序走树法 。 － 将二叉分类树变成线性有序表 。 将线性有序表构成平衡 的二又分类树算法 。 中序走树算法及其特性请见 有关参考资料

在此仅给出“线性有序表变成平衡二叉分类树算法”： 1 i=1,j=ny p=(i+j)/2,PUSH (n+1) /*n为线性有序表中元素个数，P为指针，指向i和j之中部，“/”为整除号， PUSH为进栈过程标识符*/ ②REPEAT WHILE(P≥i) j=p-1, LM=(i+j)/2,/*LM指向P之左儿子*/ IFP>LM≥i THEN P→LP=LM ELSE P-LP=null; PUSH (P), P=LM); 业 ③P=TOP,/TOP一取栈顶元素函数/ POP,,/*POP一退栈过程名/ IF P=n+1 THEN RETURN; ④i=p+l, RM=·(i+TOP-1)/2,/*RM指向P之右儿子￥/ IF P<RM<TOP THEN{P-RP=RM:P=RM ELSE{P-RP=null,P=O); G0T0② 例如，对于=12的栈性有序表，执行上述平衡构树算法后，将有如图3的平衡二叉分类 树。 49 27 13 38 65 99 19) 40 73 97 13 19 27 38 41 49 73 95 97 101 图4平衡的二叉分类树 显然，对平衡的二叉分类检索，其查找效率同高效的折半查找效率完全一致。 四、结束语 由北京钢铁学院和冶金部情报总所、部计算中心等七个单位协作研制的微型机情报检索 系统《MCDS》于84年5月通过了冶金工业部的鉴定。由于该系统在文件的组织，数据的 安排，算法的设计等方面采用了一系列先进的有创造性的技术，使系统的检索效率与lgzn 达到了和谐和一致。 本文承孙一康教授热心指点和认真审阅，在此，特表深切谢意。 69

在此仅给出 “ 线性有序表变成平衡二 叉分类树算法” ① ， ， 二 ， 关 为线性有序 表 中元素个数， 为指针 ， 指 向 和 之 中部， ’ ” 为 整 除 号， 为进栈过程标识 符 关 ② 》 一 ， ， 关 指 向 之左 儿子 关 》 ， ， ， ， ③ ， 关 － 取栈顶元素函数 关 ， ， 关 －退栈过程名 朴 ④ · 一 ， 关 指 句 之右儿子 关 ， ， ， ， ， ② 例如 ， 对于 的栈性有序表 ， 执行上述平衡构树算法后 ， 将有如图 的平衡二叉分类 树 。 图 平衡的二叉分类树 显然 ， 对平衡 的二 叉 分类检索 ， 其查 找效率同高效的折半查 找效率完全 一致 。 四 、 结束语 由北京钢铁学 院和 冶金 部情报总所 、 部计算中心 等七个单位协作研制的微型机情报检索 系统 《 》 于 年 月 通过 了冶金工业 部的鉴定 。 由于 该系统在文件的组织 ， 数 据 的 安排 ， 算法 的设 计等方 面采用 了一系 列先进 的有创造性 的技术 ， 使系统 的检索效率与 达到了和谐 和一致 。 本文 承孙一康教授热心指 点和认真审阅 ， 在此 ， 特表深 切谢意

参考文献 [1]《MCDS》使用说明书 [2]D.E克努特著，管纪文等译：“计算机程序设计技巧”第一卷 基本算法、国防 工业出版社，1680.3 [3]冯克清：“数据结构”，北京钢院内部讲义 The New Technique in the Microcomputer Information Retrieval System《MCDS》 Feng Keqing Abstract To be restricted in resource of a microcomputer system,especially in storage capacity on secondary memories and computation speed of microcomputers, system efficiency on a microcomputer information retrieval system is usually very low.In this paper Some new methods using for increasing the system efficiency has been introduced,a special one is the technique called "stric- tly inverted sorting"about binary sorting trees.These methods has been used for“MCDS”successfully。 70

参 考 文 献 【 」 《 》 使用说明书 〕 克努特著 ， 管纪文等译 “ 计算机程序设计技巧” 第一卷 工业 出版社 ， 〕 冯克清 “ 数据结构 ” 北京钢 院内部讲 义 基本算法 、 国 防 》 愁 ， ， 。 ， ‘ ” ，’ ” 。 了 护