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

李冰巖黃地龍郝園

(成都理工大學(xué)信息工程學(xué)院，四川成都610059)

1.引言

在互聯(lián)網(wǎng)發(fā)展初期，網(wǎng)站相對(duì)較少，信息查找比較容易。然而伴隨互聯(lián)網(wǎng)爆炸性的發(fā)展，普通網(wǎng)絡(luò)用戶想找到所需的資料簡(jiǎn)直如同大海撈針，這時(shí)為滿足大眾信息檢索需求的專業(yè)搜索網(wǎng)站便應(yīng)運(yùn)而生，而搜索引擎技術(shù)也隨之發(fā)展開(kāi)來(lái)。自1993第一個(gè)搜索引擎Excite誕生以來(lái)，搜索引擎不斷發(fā)展不斷完善，各種搜索技術(shù)不斷創(chuàng)新，并已形成互聯(lián)網(wǎng)的一個(gè)重要支撐業(yè)務(wù)。

搜索引擎是互聯(lián)網(wǎng)提供公共信息檢索服務(wù)的Web站點(diǎn)，它以一定的技術(shù)和策略在互聯(lián)網(wǎng)中搜索，發(fā)現(xiàn)網(wǎng)絡(luò)信息，并對(duì)網(wǎng)絡(luò)信息進(jìn)行理解，提取和處理，為網(wǎng)絡(luò)用戶提供檢索服務(wù)，是快速查找檢索信息的一種網(wǎng)絡(luò)工具。

蟻群算法是由意大利學(xué)者M(jìn).Dorigo等人在20世紀(jì)90年代初首先提出來(lái)的，它是繼模擬退火算法、遺傳算法、禁忌算法等元啟發(fā)式搜索算法以后的又一種應(yīng)用于組合優(yōu)化問(wèn)題的啟發(fā)式搜索算法。

本文基于蟻群算法的理論，結(jié)合蟻群算法的分布式特點(diǎn)，結(jié)合目前網(wǎng)絡(luò)上常用的分布式網(wǎng)絡(luò)結(jié)構(gòu)，提出了一個(gè)基于蟻群算法的搜索引擎系統(tǒng)。并通過(guò)仿真實(shí)驗(yàn)證明了這個(gè)搜索引擎算法可以提高搜索效率，具有本質(zhì)并行性，易于并行實(shí)現(xiàn)，可以較好地維護(hù)系統(tǒng)穩(wěn)定性。

2.蟻群算法

2.1 蟻群算法概念

蟻群算法是Dorigo M等人于1991年提出的。螞蟻個(gè)體之間是通過(guò)一種稱之為信息素的物質(zhì)進(jìn)行信息傳遞的。在運(yùn)動(dòng)過(guò)程中，螞蟻能夠在它所經(jīng)過(guò)的路徑上留下這種信息素，而且能夠感知信息度的濃度，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，傾向于朝著信息素濃度高的方向移動(dòng)。因此，蟻群的集體行為表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過(guò)的螞蟻越多，則后來(lái)者選擇該路徑的概率就越大，螞蟻個(gè)體之間就是通過(guò)這種信息的交流達(dá)到搜索食物的目的。

2.2 蟻群算法基本模型

定義二：信息素更新規(guī)律及公式：

其中△Tij表示邊（i，j）上的信息素濃度變化量?！鱐ijk是第k個(gè)螞蟻在時(shí)間t到t+n之間，在邊（i，j）上增加的信息素改變量。它的值由以下公式?jīng)Q定。

其中Q是一個(gè)常量，用來(lái)表示螞蟻完成一次完整的路徑搜索后，所釋放的信息素總量；Lk是第k個(gè)螞蟻的路徑總花費(fèi)，它等于第k個(gè)螞蟻經(jīng)過(guò)的各段路徑上所需的花費(fèi)Cij的總和。如果螞蟻的路徑總花費(fèi)越高，那么其在單位路徑上所釋放的信息素濃度越低。

3.用二叉樹(shù)算法存儲(chǔ)信息

網(wǎng)絡(luò)中信息是海量的，那么怎么存儲(chǔ)是個(gè)值得我們思索的問(wèn)題。以樹(shù)狀結(jié)構(gòu)組織存儲(chǔ)，有助于用戶提高查詢率，先把相同或相似內(nèi)容的資源組織起來(lái)，用戶只要查到樹(shù)根就可以用遍歷算法遍歷整個(gè)樹(shù)，進(jìn)而查詢到整個(gè)信息。這種方法在很大程度上提高了查詢效率，節(jié)省了用戶的時(shí)間，使用戶有個(gè)更好的交互體驗(yàn)。

為此我們利用二叉樹(shù)生成算法；有如下的二叉樹(shù)的存儲(chǔ)表示及一些符號(hào)定義：

利用此算法就可以生成一顆二叉樹(shù)，根節(jié)點(diǎn)可以定為包含信息量最多的節(jié)點(diǎn)，下面的內(nèi)節(jié)點(diǎn)及葉子是下級(jí)節(jié)點(diǎn)。

4.蟻群搜索引擎算法的設(shè)計(jì)

蟻群搜素引擎算法是基于蟻群算法的搜索算法。假設(shè)整個(gè)系統(tǒng)是由數(shù)目可變的多個(gè)服務(wù)器組成。這些服務(wù)器彼此相連，在網(wǎng)絡(luò)中構(gòu)成一個(gè)星型拓?fù)浣Y(jié)構(gòu)。初始狀態(tài)上，用戶從一個(gè)服務(wù)器發(fā)送搜索請(qǐng)求，暫且稱它為發(fā)送請(qǐng)求服務(wù)器。此時(shí)，該服務(wù)器會(huì)在本地服務(wù)器中進(jìn)行查找，本地搜索結(jié)束后，記錄下搜索到的信息。然后創(chuàng)建螞蟻模型，按照蟻群算法在整個(gè)網(wǎng)絡(luò)中進(jìn)行搜索。當(dāng)這些蟻群模型完成一次完整的搜索過(guò)程后，計(jì)算所花時(shí)間及搜索代價(jià)，并且更新每一條路徑上的信息素濃度。然后開(kāi)始新一輪的搜索循環(huán)。當(dāng)循環(huán)次數(shù)達(dá)到事先定義好的次數(shù)或所有的螞蟻模型都選擇了同一種路徑，整個(gè)程序結(jié)束，于是也選出了一條最優(yōu)路徑。下面是該算法的流程及部分偽代碼。

5.實(shí)驗(yàn)仿真及結(jié)果

對(duì)于這種分布式結(jié)構(gòu)的搜索服務(wù)器系統(tǒng)，如果用傳統(tǒng)的搜索方法，就要逐一去訪問(wèn)該網(wǎng)絡(luò)中的每一個(gè)服務(wù)器，這樣無(wú)疑中增加了許多不必要的搜索代價(jià)，搜索時(shí)間也進(jìn)一步增大，用戶交互性差。但是用本文所提的算法，不必像傳統(tǒng)算法那樣去訪問(wèn)每一個(gè)服務(wù)器，而是可以找到一條最優(yōu)路徑，這樣可以減少搜索代價(jià)，減少用戶等待時(shí)間。

如圖1為例來(lái)計(jì)算搜索代價(jià)：

起始點(diǎn)S為請(qǐng)求服務(wù)器，若按傳統(tǒng)搜索方法進(jìn)行搜索，由S開(kāi)始向各個(gè)節(jié)點(diǎn)發(fā)送搜索請(qǐng)求。則搜索代價(jià)為：（3+2+6+8+7）×2=52；若用蟻群搜索算法，通過(guò)計(jì)算得到搜索代價(jià)為：20×2=40?？梢钥闯鱿伻核阉魉惴ù_實(shí)減少了搜索代價(jià)，因?yàn)樗皇侨ピL問(wèn)每一個(gè)服務(wù)器，而是找到了一條最優(yōu)路徑。而且此種算法在服務(wù)器數(shù)目越多的時(shí)候越能發(fā)揮出其優(yōu)勢(shì)，它可以動(dòng)態(tài)調(diào)整服務(wù)器的數(shù)量，隨意添加或削減服務(wù)器，可見(jiàn)靈活性非常大，可以更好地保持系統(tǒng)的穩(wěn)定性。

以下通過(guò)仿真實(shí)驗(yàn)比較了在星型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下蟻群搜索算法和傳統(tǒng)算法搜索代價(jià)和響應(yīng)時(shí)間的對(duì)比。實(shí)驗(yàn)時(shí)保持其它參數(shù)的值不變。

表1為網(wǎng)絡(luò)上有10個(gè)搜索請(qǐng)求數(shù)時(shí)的蟻群搜索算法和傳統(tǒng)算法搜索代價(jià)和響應(yīng)時(shí)間的對(duì)比。如下所示：

表1 10個(gè)搜索請(qǐng)求的仿真結(jié)果

表2為網(wǎng)絡(luò)上有50個(gè)搜索請(qǐng)求數(shù)時(shí)的蟻群搜索算法和傳統(tǒng)算法搜索代價(jià)和響應(yīng)時(shí)間的對(duì)比。如下所示：

表2 50個(gè)搜索請(qǐng)求的仿真結(jié)果

從以上兩表可以看出，在網(wǎng)絡(luò)中搜索請(qǐng)求數(shù)越多的時(shí)候，蟻群搜索引擎算法更能發(fā)揮出它的優(yōu)點(diǎn)。該仿真實(shí)驗(yàn)證明了蟻群搜索引擎算法可以提高搜索效率，具有本質(zhì)并行性，易于并行實(shí)現(xiàn)，可以較好地維護(hù)系統(tǒng)穩(wěn)定性。

6.結(jié)束語(yǔ)

本文討論了一種基于分布式服務(wù)器的搜索引擎算法，此種搜索算法是基于蟻群算法的，該算法可以提高搜索效率，易于并行實(shí)現(xiàn)，并且極好地維護(hù)了系統(tǒng)的穩(wěn)定性。從理論上和仿真實(shí)驗(yàn)上說(shuō)明和驗(yàn)證了該算法的優(yōu)越性。

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

[2]姜長(zhǎng)元.蟻群算法的理論及其應(yīng)用[J].計(jì)算機(jī)時(shí)代，2004，(06)：1-3.

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

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