杜友福，程彩凤，赵 鸣 (长江大学计算机科学学院，湖北 荆州 434023)

搜索引擎中智能代理技术及启发式搜索策略研究

杜友福，程彩凤，赵 鸣 (长江大学计算机科学学院，湖北 荆州 434023)

提出了启发式搜索应用于搜索引擎来获取特定的信息的策略。通过引入智能代理系统，自动完成搜索到的页面类型的判断，更快更准确地命中目标网页。试验结果表明，引入智能代理后的启发式搜索算法与传统的深度优先和宽度优先算法相比，获取信息的准确性更高。

搜索引擎；启发式搜索；智能代理；文本表示；估价函数

搜索引擎是以一定的策略在互联网中搜集和发现信息，并对信息进行理解、提取、组织和处理，最终为用户提供检索服务，从而达到信息导航的目的。搜索引擎中的网络蜘蛛程序是依靠一定的算法来遍历Internet中的网页，抽取相关信息，最后将其保存在数据库中。依靠网络蜘蛛，搜索引擎才能获取足够的信息供用户检索和查找。由于网络中信息分布的不确定性导致了信息收集的盲目性，从而使得使用传统的宽度和深度优先搜索算法的网络蜘蛛程序在特定信息资源获取上效率和效果都不甚理想。笔者将启发式搜索和智能代理技术引入到搜索引擎中，依靠启发信息，可以避免遍历过多的无用链接，提高网络蜘蛛类程序的效率和信息获取的准确度。

1 搜索引擎的工作原理

搜索引擎的原理[1]可以分为以下4步：

1)从互联网上抓取网页 利用能够从互联网上自动收集网页的网络蜘蛛程序，自动访问互联网，并沿着任何网页中的所有URL爬到其他网页，重复这过程，并把爬过的所有网页收集到服务器中。

2)建立索引数据库 由索引系统程序对收集回来的网页进行分析，提取相关网页信息，根据一定的相关度算法进行大量复杂计算，得到每一个网页针对页面内容中及超链中每一个关键词的相关度(或重要性)，然后用这些相关信息建立网页索引数据库。

3)在索引数据库中搜索 当用户输入关键词搜索后，分解搜索请求，由搜索系统程序从网页索引数据库中找到符合该关键词的所有相关网页。

4)对搜索结果进行处理排序 所有相关网页针对该关键词的相关信息在索引库中都有记录，只需综合相关信息和网页级别形成相关度数值，然后进行排序，相关度越高，排名越靠前。最后由页面生成系统将搜索结果的链接地址和页面内容摘要等内容组织起来返回给用户。

2 启发式搜索

2.1启发式搜索过程

启发式搜索基本过程如下[2]:

1) 给定初始状态S,产生一个状态的有限描述。

2) 使用发生函数Q(x)对S产生其后的每个后续状态。

3) 对产生的状态检查,有无目标状态G,如果有则搜索成功。

4) 如果目标状态G没有出现,就用估价函数f(x)对这些节点进行评估,选择最有希望的节点,继续使用Q(x)产生它的子节点,重复步骤3)。

5) 如果所有可能的节点都使用Q(x)拓展过,目标状态G还是没出现,则搜索失败。

以上搜索步骤可以应用于任何状态空间问题的搜索。智能启发式搜索区别于其他搜索的主要特点是估价函数f(x)的设计。

2.2估价函数的设计

估价函数的作用是估计Open表(Open表保存所有已经生成而未扩展的节点)中每个状态的估价函数值,按照值的大小重新排序。设计估计函数要考虑两方面内容，即已经付出的代价和将要付出的代价。一般把估价函数f(x)定义为初始节点经过n节点到达目标节点的最小代价路径的代价估计值。其一般形式[3]为:

f(n)=g(n)+h(n)

式中，g(n)是从初始点S到n的实际代价,而h(n)是从n到目标节点G的最佳路径的估计代价。对网站类型进行判断中，需要设计一张门户网站网址列表，所要判断的网址都要对该列表进行比对。如果属于该列表则可认为是门户网站，否则认为是一般网站。考虑Web页面中链接的特点，在估价函数中必须要对链接文本的信息和链接本身的信息作出判断。因此必须建立一个相关的知识库，在试验中以保存在文本中的关键字来表示，这些知识库为蜘蛛程序提供了对链接判断的依据。

因此，估价函数主要是对链接进行判断，当获取一个URL后，估价函数对其进行判断，如果为门户型网站则获取其站内链接，对这些链接进行判断，是否含有关键字表中所列的关键字，如果有则对该URL的估价值加20,没有则返回。如果该链接是一般的主题网站网址，则获取其外部链接，如果这些链接中含有关键字，则该链接的估价值加10。站内的链接估价值要比外部的高，因为这样可以使该站有价值的页面尽快被访问，而不需要等以后访问其他网页后重新访问，可以减少客户和服务器重新链接带来的开销。具体流程图如图1所示。

图1 估价函数对页面进行判断的流程图

3 智能代理技术的引入

把智能代理技术应用到搜索引擎中，让其自动完成文档的分类或者判断其所属类型，能够判断该页面是否属于所需要的网页。

3.1Web文本的分类判断

假设给出各关键字的词频，构成一个文本向量，用文本文件存放。对文本的分类可以按以下2种情况来判断[4]。

1)根据链接的html网页的title和meta属性 这两者往往能提供一些网页的类别信息。如果title或meta包含关键字表中的关键字，那么可以认为是所需要的网页。但是关键字出现在title属性和meta属性中所表示的网页权重不同。关键字如果出现在title中，则网页的权重就高些，这里假设其系数是3，关键字如果出现在meta中，则网页的权重系数为2。

2)根据页面内容的文本信息 采用最简单的向量分类算法。该方法的思路为：首先对较多的样本进行分析抽取一个具有代表性的向量作为中心向量，然后计算中心向量与新向量的相似度。相似度一般用两者向量的夹角表示，夹角越小，表示相似度越高。根据计算的结果，与阈值进行比较，判断是否属于需要的网页类别。

相似度sim(d1，d2)用于度量2个文档d1和d2之间的内容相关程度[5]。当文档被表示为文档空间的向量，就可以利用向量之间的距离计算公式来表示文档间的相似度。常用的向量距离度量方法有欧氏距离、内积距离和余弦距离。笔者采用的是余弦距离，其公式为：

图2 页面判断部分流程图

式中，di为新文本的特征向量；dj为中心向量；n为特征向量的维数;ωk为向量的第k维。

假定如果关键字出现在文本内容中，则其权重系数为1。中心向量为关键字的权重。结合这2种情况，分别计算各相似度，最后求其加权平均值，然后与阈值进行比较，满足要求的就是所需要的页面。

页面判断算法的流程图如图2所示。

3.2阈值的确定

在所有的数据挖掘算法中，阈值一般根据经验预设初始值。初始值的确定也很不容易，应当首先根据经验和简单的测试而定，然后不断的调整，使阈值落在一个比较合理的范围内[6]。在该试验中，最后给定阈值初始值为0.6。

4 试验结果

用启发式搜索和智能代理技术的搜索算法(简称启发式搜索算法)，在Windows环境下的试验结果与传统的深度优先和宽度优先算法相比，获取信息的准确性有很大的提高。笔者用相对回报率来评价搜索引擎中资源获取的性能。相对回报率的公式如下:

设种子网站为4个，关键字表为有关“人工智能”的内容，共有18个关键字。试验结果如表1和表2所示。

表1 启发式搜索算法试验结果表

表2 宽度优先搜索算法实验结果表

5 结 论

由上述试验可知，对于相同的关键字和种子网站，传统的搜索算法得到的相对回报率都相对较低，启发式搜索算法可以得到相对较高的回报率。这是因为启发式搜索算法依靠启发信息，对于那些无关的页面可以不去访问，从而减少了遍历的页面数。试验结果证明启发式搜索策略和智能代理技术结合能极大提高搜索的效率。

[1]徐宝文，张卫丰. 搜索引擎与信息获取技术[M].清华大学出版社，2003.

[2]蔡自兴，徐光裕.人工智能及其应用[M]. 第2版.北京:清华大学出版社，2005. 135～138.

[3]Nilson N J.Principles of Artificial Intelligence[M].Tioga Publishing Co.,2006. 258～259.

[4]Pearl J Heuristics.Intelligent Search Strategies for Computer Problem Solving[M].AddisonWesley Publishing Company, 2007. 368～339.

[5]Pearl J.Some recent results in heuristic search theory[J].IEEE Trans，2004,PAMI-6(1):1～12.

[6]王士同.多因素问题的启发式搜索算法MFRA[J].计算机学报，2006,19(2):149～152.

[编辑] 易国华

TP391

A

1673-1409(2009)02-N063-03

2009-03-26

杜友福(1961-)，男， 1982年大学毕业，教授，现主要从事人工智能技术和数据库技术方面的教学与研究工作。