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

李冰巖黃地龍郝園

(成都理工大學信息工程學院，四川成都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個搜索請求的仿真結果

從以上兩表可以看出，在網絡中搜索請求數越多的時候，蟻群搜索引擎算法更能發揮出它的優點。該仿真實驗證明了蟻群搜索引擎算法可以提高搜索效率，具有本質并行性，易于并行實現，可以較好地維護系統穩定性。

6.結束語

本文討論了一種基于分布式服務器的搜索引擎算法，此種搜索算法是基于蟻群算法的，該算法可以提高搜索效率，易于并行實現，并且極好地維護了系統的穩定性。從理論上和仿真實驗上說明和驗證了該算法的優越性。

[1]靳凱文，李春葆，秦前清.基于蟻群算法的最短路徑搜索方法研究[J].公路交通科技，2006，(03)：127-129.

[2]姜長元.蟻群算法的理論及其應用[J].計算機時代，2004，(06)：1-3.

[3]程陳，齊開樂，陳劍波，姚紹文.基于Web2.0的綜合搜索引擎[J].計算機應用與軟件2010，(01)：180-183.

[4]Dorigo M，Strtzle T.Ant Colony Optimization[M].USA：Massachusetts Institute of Technology，2004.