基于W e b的搜索引擎算法的研究

时间：2024-07-28

李冰岩黄地龙郝园

(成都理工大学信息工程学院，四川成都610059)

1.引言

在互联网发展初期，网站相对较少，信息查找比较容易。然而伴随互联网爆炸性的发展，普通网络用户想找到所需的资料简直如同大海捞针，这时为满足大众信息检索需求的专业搜索网站便应运而生，而搜索引擎技术也随之发展开来。自1993第一个搜索引擎Excite诞生以来，搜索引擎不断发展不断完善，各种搜索技术不断创新，并已形成互联网的一个重要支撑业务。

搜索引擎是互联网提供公共信息检索服务的Web站点，它以一定的技术和策略在互联网中搜索，发现网络信息，并对网络信息进行理解，提取和处理，为网络用户提供检索服务，是快速查找检索信息的一种网络工具。

蚁群算法是由意大利学者M.Dorigo等人在20世纪90年代初首先提出来的，它是继模拟退火算法、遗传算法、禁忌算法等元启发式搜索算法以后的又一种应用于组合优化问题的启发式搜索算法。

本文基于蚁群算法的理论，结合蚁群算法的分布式特点，结合目前网络上常用的分布式网络结构，提出了一个基于蚁群算法的搜索引擎系统。并通过仿真实验证明了这个搜索引擎算法可以提高搜索效率，具有本质并行性，易于并行实现，可以较好地维护系统稳定性。

2.蚁群算法

2.1 蚁群算法概念

蚁群算法是Dorigo M等人于1991年提出的。蚂蚁个体之间是通过一种称之为信息素的物质进行信息传递的。在运动过程中，蚂蚁能够在它所经过的路径上留下这种信息素，而且能够感知信息度的浓度，并以此指导自己的运动方向，倾向于朝着信息素浓度高的方向移动。因此，蚁群的集体行为表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大，蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。

2.2 蚁群算法基本模型

定义二：信息素更新规律及公式：

其中△Tij表示边（i，j）上的信息素浓度变化量。△Tijk是第k个蚂蚁在时间t到t+n之间，在边（i，j）上增加的信息素改变量。它的值由以下公式决定。

其中Q是一个常量，用来表示蚂蚁完成一次完整的路径搜索后，所释放的信息素总量；Lk是第k个蚂蚁的路径总花费，它等于第k个蚂蚁经过的各段路径上所需的花费Cij的总和。如果蚂蚁的路径总花费越高，那么其在单位路径上所释放的信息素浓度越低。

3.用二叉树算法存储信息

网络中信息是海量的，那么怎么存储是个值得我们思索的问题。以树状结构组织存储，有助于用户提高查询率，先把相同或相似内容的资源组织起来，用户只要查到树根就可以用遍历算法遍历整个树，进而查询到整个信息。这种方法在很大程度上提高了查询效率，节省了用户的时间，使用户有个更好的交互体验。

为此我们利用二叉树生成算法；有如下的二叉树的存储表示及一些符号定义：

利用此算法就可以生成一颗二叉树，根节点可以定为包含信息量最多的节点，下面的内节点及叶子是下级节点。

4.蚁群搜索引擎算法的设计

蚁群搜素引擎算法是基于蚁群算法的搜索算法。假设整个系统是由数目可变的多个服务器组成。这些服务器彼此相连，在网络中构成一个星型拓扑结构。初始状态上，用户从一个服务器发送搜索请求，暂且称它为发送请求服务器。此时，该服务器会在本地服务器中进行查找，本地搜索结束后，记录下搜索到的信息。然后创建蚂蚁模型，按照蚁群算法在整个网络中进行搜索。当这些蚁群模型完成一次完整的搜索过程后，计算所花时间及搜索代价，并且更新每一条路径上的信息素浓度。然后开始新一轮的搜索循环。当循环次数达到事先定义好的次数或所有的蚂蚁模型都选择了同一种路径，整个程序结束，于是也选出了一条最优路径。下面是该算法的流程及部分伪代码。

5.实验仿真及结果

对于这种分布式结构的搜索服务器系统，如果用传统的搜索方法，就要逐一去访问该网络中的每一个服务器，这样无疑中增加了许多不必要的搜索代价，搜索时间也进一步增大，用户交互性差。但是用本文所提的算法，不必像传统算法那样去访问每一个服务器，而是可以找到一条最优路径，这样可以减少搜索代价，减少用户等待时间。

如图1为例来计算搜索代价：

起始点S为请求服务器，若按传统搜索方法进行搜索，由S开始向各个节点发送搜索请求。则搜索代价为：（3+2+6+8+7）×2=52；若用蚁群搜索算法，通过计算得到搜索代价为：20×2=40。可以看出蚁群搜索算法确实减少了搜索代价，因为它不是去访问每一个服务器，而是找到了一条最优路径。而且此种算法在服务器数目越多的时候越能发挥出其优势，它可以动态调整服务器的数量，随意添加或削减服务器，可见灵活性非常大，可以更好地保持系统的稳定性。

以下通过仿真实验比较了在星型网络拓扑结构下蚁群搜索算法和传统算法搜索代价和响应时间的对比。实验时保持其它参数的值不变。

表1为网络上有10个搜索请求数时的蚁群搜索算法和传统算法搜索代价和响应时间的对比。如下所示：

表1 10个搜索请求的仿真结果

表2为网络上有50个搜索请求数时的蚁群搜索算法和传统算法搜索代价和响应时间的对比。如下所示：

表2 50个搜索请求的仿真结果

从以上两表可以看出，在网络中搜索请求数越多的时候，蚁群搜索引擎算法更能发挥出它的优点。该仿真实验证明了蚁群搜索引擎算法可以提高搜索效率，具有本质并行性，易于并行实现，可以较好地维护系统稳定性。