计算机应用研究
APPLICATION RESERCH OF COMPUTERS
2000  Vol.17　No.1　P.12-15




WWW环境下的检索策略及分析
李瑾 王永成
摘 要 近年来，随着WWW技术的广泛应用，使得Internet飞速发展，信息量不断增加。如何在新的环境下经济省时地进行信息检索，是当前信息检索领域研究的一个热点问题。在考察WWW信息的特征和用户检索特征的基础上，讨论了WWW环境下通用的检索策略、实现方法及其分析。着重介绍了站点选择的方法和连接分析算法及其改进。
关键词 检索策略 站点选择 连接分析算法
1　引言
　　Internet是目前世界上影响最大、用户最多、信息资源最为丰富的计算机“网络的网络”。随着Internet的飞速发展，网上的信息量越来越大。虽然Internet使得我们可以得到的信息比以前任何时候都多，却并不一定意味着用户总是能得到他们想要的信息。在这样的环境下，World Wide Web上的检索服务成为网络用户最熟悉的信息检索系统之一。
　　在Internet这种信息高度分布的网络环境中，由于现实条件的限制，为所有的站点上的所有文献建立统一的索引是不现实的。为了经济省时的进行检索，方法之一就是控制查找的范围，把查找范围限制在可能包含检索相关文献的站点内，即先进行站点的选择。
　　从检索服务的用户的角度来看，有人这样描述：“最终用户希望通过最少的学习，用最轻松的方式得到检索的结果”。我们经实验发现在Web检索中用户倾向于输入较短的检索提问式(1～3 words)，而且较少使用复杂的检索表达式。Web环境中的检索还存在另外一个特征：由于各种新技术的快速发展和Web上信息量的不断增加，很多用户在Web上的检索可以称为浏览式检索(与传统的检索方式相对应)，用户构造检索表达式时，常常自己也不清楚自己所需要的文献的具体特征。因此，在Web检索的这种特定环境中，基于用户查询方面的特征，我们认为可以把与摷焖鞯闹魈鈹相关的文献作为用户检索的结果提供给用户，以满足一般性的用户要求。
　　本文就WWW环境下的检索策略方面的一些问题进行讨论。
2　站点选择
2.1　站点选择的基本方法
　　在传统的检索系统中，为了方便文献的检索，要建立文献库中的文献索引的倒排文档。类似地，在Web检索中，为了控制查找范围，将其尽可能限制在可能包含检索相关文献的站点内(即先进行站点的选择)，需要构造站点选择索引的倒排文档，站点选择索引可以看作是简单地表示对应站点内容的虚拟文献。具体地讲，这种简单的虚拟文献(站点选择索引)可以由这个站点包含的词及其频率组成。Internet上的站点数量和种类都非常多，并非所有站点上的信息都适合作为具有普遍意义的信息源。因此，我们可以只为那些具有较高参考价值的站点(例如，著名大学、国际组织和研究机构等的站点)建立站点选择索引，这样的站点是Internet上所有站点的有限子集。站点选择的结果依赖于这个站点的虚拟文献在多大程度上满足了检索提问式的要求。即：
　　一个站点的虚拟文献可以表示为：
　　VD(S)={(Wi, Fi)}
　　Wi—出现在站点S中的词
　　Fi—Wi在站点S中出现的频率
　　假设有站点S1，S2，...，Sn，对于给定的检索提问式Q，把各个虚拟文献VD(S)看作一般的文献，计算VD(S)与检索提问式的相关程度，从而得到应进一步进行查找的站点。
　　Internet上的信息是在不断变化的。一般而言，我们可以认为具有较高参考价值的站点上的信息是可以信赖且在一段时间内相对稳定的，因此，我们既有必要，也能够为站点选择索引的倒排文档进行定时更新。
2.2　存在的问题
　　这种做法虽然简单可行，但也存在明显的不足。举例说明：假设检索提问式为“the white house”，“white”和“house”两个词都是高频词，在各个站点中的分布情况很难作为正确判断一个站点与“the white house”这个检索提问式相关程度的依据。类似的情况并不少见，又如，“high blood pressure”。出现这个问题的根本原因在于，虚似文献的这种组织方式不能再现语的同现信息
2.3　解决方法
　　我们在此建议几种解决这个问题的方法。
　　第一种方法是在虚拟文献中使用词组和检索提问句。
　　虚拟文献中不仅要存储单个的词及其出现频率，还要存储摯首閿及其出现频率的信息。一般来说，这里的词组可以仅规定为名词词组。这种方法可以基本上解决词同现信息的问题，但是增加了预处理工作的复杂度。为了进一步提高检索的效率，还可以考虑将站点经常对应的检索提问句存储在虚拟文献中，如果检索提问式恰好与虚拟文献中存储的某一检索提问句相匹配，那么，该站点一定是应被选中的站点。
　　另一种方法称为检索扩充。
　　如前所述，使用高频词作为检索关键词很难为正确的选择站点提供良好的依据。因此，我们希望能够通过检索扩充为原来的检索提问式加入一些使其更具代表性的词汇，从而使得检索提问式在基本上不改变原来检索意图的情况下，更适合进行站点的选择。检索关键词所对应的主题词可能满足这一要求，因为主题词本身就很能反映一类信息的特征。而且，一个检索需求一般总能有主题词与其对应。例如，“he blood pressure”的对应主题词可能是“cholesterol”和“hypertension”，经检索扩充加入主题词后的检索提问式就能够较好地进行站点选择了，因为这种情况下主题词较好地反映了用户的需求，词同现信息就不是非常关键性的问题了。
　　这种方法需要主题词表及同义词典的支持，但并不增加预处理工作的复杂度。
　　再一种方法，可以考虑用站点信息的摘要来作为站点的虚拟文献。即，一个站点的虚拟文献可以表示为：
　　VD(Si)=Abs(Si)
　　Si—站点
　　Abs(Si)—站点Si内容的摘要
　　对于站点S1, S2, ..., Sn，及给定的检索提问式Q，把各个虚拟文献看作一般文献，计算Q与VD(Si)的相关程度，从而得到应进一步进行查找的站点。在实现过程中，虚拟文献(站点内容的摘要)并不存储摘要的本身，而是存储其索引。这种方法的效果如何，很大程度上取决于摘要的水平，而这种方法的实用程度也要依赖于摘要的自动化程度。
3　检索主题的提取
3.1　连接分析算法及其现实依据
　　在World Wide Web环境中的检索与传统的检索相比，面临很多问题。
　　1)用户倾向于使用短的检索表达式(1～3 words/query)，很难得到用户的反馈信息；用户在检索时的目的是为了了解新技术、掌握新情况，因此，用户在构造检索提问式时，并不非常清楚自己的需求。
　　2)信息源处于经常的变化之中。
　　3)文献的价值差别很大，有些文献很有参考价值，有些文献只是一些拼凑的东西，还有许多东西根本不能作为很有价值的参考信息。
　　4)Internet上的文献不像科技类或新闻类的文章那样有一定的章法可循；对文献进行深入的预处理工作是不可行的。
　　在这种情况下，想要精确地给出满足需求的文献是很困难的，而向用户提供与检索主题相关的文献则更具有一般性。
　　尽管Web上的信息检索系统面临许多不利因素，它也有着传统信息检索系统所不具备的优势，即Web上的IR系统可以充分利用Web页面的作者建立的超链接所反映的意见。可以设想，如果页面A包含有一个指向页面B的超链接，那么，页面A的作者认为页面B包含有价值的信息。如果页面A指向的有价值的页面越多，页面A的作者的观点就越有价值，而且，如果页面A有指向页面B的超链接，就意味着页面B也是有参考价值的。
　　基于以上基本思想，Kleinberg于1997年提出了超链接环境中的连接分析算法，以挖掘页面之间的链接所隐含的信息。首先作如下假设。
　　1)两个页面之间的链接表明两个页面包含相关信息。
　　2)如果页面的作者不同，且页面A包含指向页面B的指针，则A页面的作者认为B页面有参考价值。
　　这个算法的第一步是构造一个给定检索提问式的初始页面图，图的结点是页面。构造这张初始化的图可以有多种途径，我们用站点选择时得到的站点的主页为结点来构成。这样做一方面保证了初始页面集尽可能与检索提问相关；另一方面，也可以通过连接分析算法对站点选择的结果进行修正。
　　然后，以邻接关系为依据，逐步扩充初始页面图(与初始页面集有邻接关系的页面是指包含有指向初始页面集合的指针或被初始页面集合指向的页面)。实际上，一个页面结点的入度可能非常大，因此，Kleinberg建议为每一个页面最大考虑50个前趋结点。初始页面集和与其有邻接关系的页面构成了邻接页面图的结点。不具有同一URL地址的页面之间的超链接构成了图的有向边。我们认为同一URL内部的超链接出自同一作者，因此对发掘页面之间链接的隐含信息的帮助可以忽略不计。
　　有了邻接页面图，算法为每一个页面结点计算H (ub)值和A (uthority)值。A值高的页面被认为与要检索的内容相关度较高， H值高的页面被认为包含较多的指向检索相关内容的超链接。进一步讲，指向很多其它页面的页面有较高的H值，被许多页面指向的页面具有较高的A值；更进一步地讲，一个指向很多高A值的页面的页面具有更高的H值，一个被很多高H值页面指向的页面具有更高的A值。计算A值和H值的算法如下。
　　[连接分析算法]
　　(1)定义G=〈D，E〉为邻接图， D为结点的集合， E为边的集合
　　(2)对于D中的每一个结点n，定义H[n]为其H值， A[n]为其A值
　　(3)对于D中的每一个结点n，初始化H[n]和A[n]的值为1
　　(4)如果向量H和A还不收敛，做
　　(5)对于D中的每一个结点n，
　　(6)对于D中的每一个结点n，
　　(7)规一化向量H和A
　　可以证明[2]A和H最终一定能收敛，也就是说，上述计算一定能够终止。计算结束时，每个页面都有一个A值和H值。A值较高的页面与检索主题的相关度更高。
3.2　存在问题
　　我们发现上述算法存在一些不足：
　　1)不同URL地址的页面之间的相互作用关系产生的不良影响。
　　同一URL地址的一组页面可能指向另一URL地址的一个页面。这种情况会引起第一个地址上的那一组页面的H值的增加和第二个地址上的一个页面的A值增加。也存在另一种情况，第一个地址上的一个页面指向第二个地址上的多个页面，这种情况引起类似的相应问题。由于我们假设同一URL地址的页面出自同一作者，因此，在上述两种情况下，我们给一个作者的观点赋予了过多的权重。
　　2)自动生成的超链接。
　　用工具(例如，制作网页的工具，将数据库的内容转换成网页的工具等)生成的Web页经常会包含工具自动插入的超链接。在这种情况下，假设2)—认为超链接代表作者的观点，不能成立。
　　3)存在不相关的结点。
　　页面邻接图中可能存在与检索主题不相关的页面结点。如果这些结点并不孤立的话，就有可能导致检索主题偏离的现象。例如，检索提问为“car and jaguar”，则各个汽车生产厂商的主页就有可能成为A值最高的页面，而列出汽车生产厂商的页面则有可能成为H值最高的页面。
3.3　解决方法
　　要解决问题1，我们就要控制同一地址的所有页面对它们指向的另外一个页面的影响与一个页面对另一个页面的影响效果相同。为了达到这一目的，我们为下列情况下的每一条边加上权重。
　　如果从第一个地址上的页面有k条边指向第二个地址上的一个页面，我们为每条边赋权值A_W为1/k。即第一个地址上的页面指向第二个地址上的一个页面的所有边的权值A_W之和为1。

　　如果第一个地址的一个页面中有l条边指向第二个地址的一组页面，我们为这样的每一条边赋权值H_W为1/l。即第一个地址上的一个页面指向第二个地址上的页面的所有边的权值H_W之和为1。

　　这样，连接分析算法可以改为如下形式。
　　[改进的连接分析算法]
　　(1)定义G=〈D，E〉为邻接图，D为结点的集合， E为边的集合
　　(2)对于D中的每一个结点n，定义H[n]为其H值， A[n]为其A值
　　(3)对于D中的每一个结点n，初始化H[n]和A[n]的值为1
　　(4)如果向量H和A还不收敛，做
　　(5)对于D中的每一个结点n，
　　
　　(6)对于D中的每一个结点n，
　　
　　(7)规一化向量H和A
　　要解决问题3—去除无关页面结点，我们应该考虑借鉴传统信息检索中进行内容分析（即计算相关度）的方法，通过内容分析方法和改进的连接分析方法的结合，以达到删除不相关结点的目的。这种方法也起到了解决问题2的作用，因为自动插入的超链接一般都是与检索主题无关的。
　　用R(elevence)_－W(eight)来表示一个页面与检索主题的相似度。如前所述，检索主题是比检索提问本身更广的概念。因此，在计算页面与检索主题的相关度时，仅用检索提问式本身和页面进行匹配是不够的。我们要用扩充后的检索Q (例如，补充了检索关键词所对应的主题词)代替原始的检索提问式q。对于每一个页面P，计算检索主题与页面的相关度similarity(Q,Pj)：

　　wiq= freqiq *IDFi
　　wij= freqij *IDFi
　　freqiq = i 在检索Q中出现的频率
　　freqij = i 在页面Pj中出现的频率
　　IDFi= i 在World Wide Web上的倒排文档频率的估计值
　　根据实际需要，设置、调节similarity(Q,Pj)的阈值以保证满足阈值条件的页面是与检索主题密切相关的。
　　综上所述，在站点选择的基础上，综合考察改进的连接分析算法计算所得的A值和内容分析方法所得的H值，得出最后的检索结果。
　　我们的检索策略是以检索页面为目的的，站点选择方法使检索范围得到适当的控制；连接分析算法在其基础上进行，又使得站点选择的结果具有一定的容错性；而连接分析算法和内容分析算法相结合进一步保证了检索所有的内容与用户提问相关；几种方法相辅相成，相互补充。
4　结论
　　由于现在Internet网上的信息大部分都是以英文为主的，所以上述内容是以英文环境为基础讨论的。随着Internet在国内的日益发展，如何在中文环境下处理上述问题，是值得进一步研究的方向。以上讨论的问题还没有经过深入的实验，因此也缺乏相应的实验数据，这也是下一步要努力的方向。传统的检索系统经过数十年的发展，取得的成功经验值得我们在新的检索环境下学习和借鉴，使成功的经验在新的情况下得到应用和进一步发展。
本文获国家863计划863-306项目资助
李瑾（上海交通大学计算机科学与工程系 网络中心 上海 200030） 
王永成（上海交通大学计算机科学与工程系 网络中心 上海 200030）
参考文献
1，王永成等. 中文信息处理技术及其基础. 上海：上海交通大学出版社, 1991
2，Krishna Bharat, Monika R. Henzinger , Improved Algorithms for Topic Distillation in a Hyperlinked Environment, SIGIR98
3，Jinxi Xu, Jamie Callan, Effective Retrieval with Distributed Collections, SIGIR98
4，章 琳, 张保明. WWW检索工具比较研究. 情报学报, 第17卷 第4期
收稿日期：1999年6月23日
