總第168期艦船電子工程Vol, 28 No 62008年第6期Ship Electronic EngineeringRobot算法分析江禪志王才元(海軍潛艇學(xué)院青島266071)摘要介紹 Robot搜索算法與啟發(fā)式搜索箅法分析 Robot廣度優(yōu)先策略深度優(yōu)先策略以及廣度、深度結(jié)合策略探索 Robot優(yōu)化策略關(guān)鍵詞Robo搜索算法; Robot優(yōu)化策略中圖分類號(hào)TP01.6Analysis on the robot ArithmeticJiang Chanzhi Wang CaiyuanNavy Submarine Academy, Qingdao 266071)Abstract This paper introduces search arithmetic and heuristic search arithmetic, and analyzes robot extent precedencetrategies, robot deepness precedence strategies and the combination of this two strategies, and makes a research in Robot opti-Key words Robot approach, Robot seeking strategiesClass Number TP301.6Extract the hyperlinks from d;引言Let U the set of URLs cited in these hyperlinks在搜索引擎中,信息采集 Robot的效率會(huì)直for each URL u in U接影響搜索引擎的更新周期和數(shù)據(jù)的及時(shí)性,Robot的實(shí)現(xiàn)決定搜索引擎的性能。在搜索網(wǎng)頁時(shí),由于各個(gè)網(wǎng)站的相應(yīng)時(shí)間不同,存在 Robot的最佳搜索線路問題。Enqueue操作是往隊(duì)列中F添加一個(gè)新的2 Robot搜索算法URL, Dequeue操作給隊(duì)首的URL作為一個(gè)訪問標(biāo)2.1 Robot搜索算法的基本描述記( removed),相當(dāng)于把隊(duì)首的URL彈出隊(duì)列,當(dāng)所有的URL都被訪問之后,則判斷條件EmpyLet be a list of initial URLs(F)為真。在實(shí)際搜索過程中,由于網(wǎng)絡(luò)帶寬的Let F be a queue;限制和另一端的HTTP服務(wù)器的反應(yīng)延時(shí)原因,第For each URL i in I9行的Cet操作耗時(shí)最長(zhǎng)。Enqueue(i, F);在 Robot的深度及廣度優(yōu)先策略中, Robot收集Web頁面至本地?cái)?shù)據(jù)庫中對(duì)網(wǎng)頁的重要性并沒While Empty(F)Dequeue(F)有考慮,于是就出現(xiàn)了啟發(fā)式網(wǎng)頁搜索算法,以期d+-Get(u);//request document d pointed by u使得中國(guó)煤化工高2.2CNMHG·收稿日期:2007年7月18日,修回日期:2007年8月30日作者簡(jiǎn)介:江禪志,男,高級(jí)工程師,研究方向:作戰(zhàn)模擬2008年第6期艦船電子工程啟發(fā)式算法基本描述:址且已經(jīng)被搜索過,則對(duì)其引用計(jì)數(shù)值加1,形成下Uset←網(wǎng)站首頁的URL次搜索時(shí)的待搜索抵制的優(yōu)先權(quán)加權(quán)值,如果未While Uset I null被搜索過,則將該地址加入到地址列表中3.2深度優(yōu)先策略select the highest ranked URL from Uset into URL. Next它是從起始結(jié)點(diǎn)出發(fā),一直搜索到那些不含任if Value( URL. Next)=high threshold then3.3廣度-深度結(jié)合策略save web. page as a target web page:Robot沿著網(wǎng)絡(luò)上的超鏈接搜索,當(dāng)它到達(dá)Else個(gè)新的網(wǎng)站,能對(duì)引用該網(wǎng)站的超鏈接進(jìn)行統(tǒng)計(jì),add all hyperlinks into Uset并對(duì)該網(wǎng)站進(jìn)行檢索,且將檢索結(jié)果呈現(xiàn)給用戶End if接著為所獲得的URIs運(yùn)行搜索引擎程序,重復(fù)以End while上的步驟。其中,Ⅴaue()為評(píng)價(jià)函數(shù),用來評(píng)價(jià)一個(gè)網(wǎng)頁·廣度優(yōu)先策略:能找到兩個(gè)Web文檔之間或網(wǎng)頁中的一個(gè)超鏈接。對(duì)網(wǎng)頁的評(píng)價(jià)就是對(duì)網(wǎng)的最短路徑,不會(huì)出現(xiàn)陷進(jìn)wwW深層文檔中而頁中關(guān)鍵詞相應(yīng)的權(quán)值進(jìn)行累積;對(duì)于超鏈接的評(píng)回不到出發(fā)點(diǎn)的情況。但是對(duì)于深層Wb文檔的價(jià)是對(duì)該鏈接的地址信息、 Anchor提示文本信息搜索花費(fèi)的時(shí)間較長(zhǎng)。以及所在段落的正文進(jìn)行類似計(jì)算。low. threshold深度優(yōu)先策略:能遍歷一個(gè)Web站點(diǎn)或嵌和high. threshold為給定的常量,權(quán)值低于bow.套很深的文檔集合。但是如果由于Web結(jié)構(gòu)很threshold的URL被認(rèn)為是無用URL,終止搜索;權(quán)深,會(huì)造成搜索回不到起點(diǎn)的情況值高于 high threshold的網(wǎng)頁被認(rèn)為是目標(biāo)網(wǎng)頁·廣度-深度結(jié)合策略:當(dāng)搜索引擎搜索過啟發(fā)式搜索算法采用一個(gè)集合Uset來儲(chǔ)存下個(gè)Wb站點(diǎn)或文檔時(shí)要作上標(biāo)記,避免搜索引擎步可以訪問網(wǎng)頁的URLs(Ue初始狀態(tài)只包含對(duì)同一Web站點(diǎn)或文檔重復(fù)搜索,在搜索引擎的個(gè)指向網(wǎng)站首頁的URL),通過評(píng)價(jià)函數(shù)對(duì)Uset服務(wù)器上返回一個(gè)值代表該Wb站點(diǎn)或文檔已經(jīng)中的每一個(gè)網(wǎng)頁進(jìn)行評(píng)價(jià),選取最佳URL對(duì)網(wǎng)頁被訪問過,得到的是能夠及時(shí)更新的檢索結(jié)果,具進(jìn)行評(píng)價(jià)如果高于某個(gè)給定的閾值,則認(rèn)為得到有很高的查全率。但是當(dāng)同一時(shí)間用戶過多時(shí),服個(gè)目標(biāo)網(wǎng)頁;否則將網(wǎng)頁上所有的超鏈接加入到務(wù)器負(fù)擔(dān)過重可能會(huì)造成信息阻塞Uset集合中,如此反復(fù)直至Uset為空。啟發(fā)式搜索算法大大縮短了 Robot信息采集時(shí)間4 Robot優(yōu)化策略3 Robot的遍歷策略分析4.1避免重復(fù)搜集分布式 Robot系統(tǒng),注意避免兩個(gè) Robot對(duì)同Robot的遍歷策略是指當(dāng) Robot搜索到一個(gè)文個(gè)文檔搜索兩次,可以定義兩個(gè)表,“未訪問表檔之后,下一步應(yīng)轉(zhuǎn)到哪個(gè)文檔的策略問題。由于存儲(chǔ)準(zhǔn)備取入待訪問隊(duì)列的URL,“已訪問表”中Robot檢索的 Internet文檔數(shù)量巨大, Robot遍歷策存儲(chǔ)已經(jīng)請(qǐng)求過網(wǎng)頁的URL,合理解決多個(gè) Robot略非常重要。 Robot的遍歷策略有廣度優(yōu)先策略,并發(fā)訪問隊(duì)列F的問題,使隊(duì)列維護(hù)操作的時(shí)耗深度優(yōu)先策略以及廣度、深度兩者的結(jié)合。小于Get操作的時(shí)耗。3.I廣度優(yōu)先策略域名與IP的對(duì)應(yīng)關(guān)系存在四種關(guān)系:一對(duì)一度優(yōu)先策略中把一個(gè)Web頁面中所有超鏈接對(duì)多、多對(duì)一、多對(duì)多,后三種情況有可能造成重搜索完,再繼續(xù)下一層的搜索,直到搜索到最底層復(fù)搜集。找出指向同一物理位置URL的多個(gè)域名具體方法:從URL列表中取得第一個(gè)URL對(duì)和P中國(guó)煤億亍名和然后相應(yīng)的Web文檔進(jìn)行預(yù)處理,并在該文檔中找到指把這鏈接出的最開向其他Web文檔的超鏈接。 Robot將找到的超鏈接始的CNMHG結(jié)果一樣,應(yīng)該與 robot中的屏蔽地址列表中的URLs作比較:不是歸為一組。以后搜集的時(shí)候可以只選擇其中的搜索范圍內(nèi)的地址則丟棄,如果是搜索范圍內(nèi)的地(下轉(zhuǎn)第209頁)2008年第6期艦船電子工程采樣系統(tǒng)都有個(gè)延遲,延遲最小就是保證延遲定性,具有很強(qiáng)的使用價(jià)值時(shí)間在一個(gè)開關(guān)周期內(nèi)。如圖5由于定時(shí)器中斷和AD采樣中斷服務(wù)處理程序的指令數(shù)固定,因而每周期內(nèi)AD采樣的位置相對(duì)于開關(guān)周期的開始時(shí)間是固定的。選擇合適的AD采樣濾波參數(shù),更[1] Brown Marty. Practical Switching Power Supply Design有利于跟蹤電感的平均電流。AD中斷間隔開關(guān)(2]張占松蔡宜三開關(guān)電源的原理與設(shè)計(jì)M]北京:周期的開始時(shí)間很短,可以保證數(shù)字控制器有足夠子工業(yè)出版社,1998的時(shí)間執(zhí)行完。[3]邢巖蔡宣三.開關(guān)型電壓調(diào)節(jié)系統(tǒng)數(shù)字仿真的一種新6結(jié)語算法[J].通信學(xué)報(bào),1988,19(3)[4]李學(xué)海.PC單片機(jī)實(shí)用教程[M].北京:北京航空航本文敘述了DSC控制高壓電源的方法,對(duì)全天大學(xué)出版社,2002橋移相PWM變換器和高壓變壓器進(jìn)行了設(shè)計(jì)。[5]劉和平鄭群英.dPC通用數(shù)字信號(hào)控制器原理與應(yīng)并在實(shí)際應(yīng)用中證明了此高壓電源的可靠性和穩(wěn)用2007(上接第161頁)該服務(wù)器時(shí),首先瀏覽這個(gè)文件。根據(jù)指定URL個(gè)進(jìn)行搜集,選擇的時(shí)候應(yīng)該優(yōu)先選擇有域名的,獲取文檔:從服務(wù)器端得到對(duì)應(yīng)的文檔。有的網(wǎng)站對(duì)于直接用P訪問是被禁止的4.4對(duì)已經(jīng)獲取的URL充分處理4.2首先搜集重要的文檔Robot在運(yùn)行過程中,為了提高 Robot與URL體現(xiàn)網(wǎng)頁重要度的特征有:1)網(wǎng)頁的入度大,集合的交互效率,我們必須對(duì)龐大URL列表進(jìn)行表明被引用的次數(shù)多;2)某網(wǎng)頁的父網(wǎng)頁入度大;充分處理。URL實(shí)施模塊包括:管理拒絕 Robot訪3)網(wǎng)頁的鏡像度高;4)網(wǎng)頁的目錄深度小,易于用問的URL,通過 Robot.txt文件說明哪些鏈接不可戶瀏覽到。訪問及拒絕哪些Robo訪問等;獲取新的URL并準(zhǔn)由于搜索引擎開始工作時(shí),前三項(xiàng)特征無法確備添加列表中,從已經(jīng)獲取的文檔中分析出新的定,只有最后一項(xiàng)不需要知道網(wǎng)頁內(nèi)容可確定某個(gè)URL;添加URL之前的加工處理:URL的存儲(chǔ)可以URL是否重要的標(biāo)準(zhǔn),由于URL長(zhǎng)度都小于256在存儲(chǔ)占用空間以及訪問速度兩個(gè)方面進(jìn)行優(yōu)化。個(gè)字符,這使得URL目錄深度易判別,所以最后一首先把已獲取的URL按字典順序排列,只存儲(chǔ)項(xiàng)是最值得考慮的指導(dǎo)因素。URL的增加部分,可以減少70%的存儲(chǔ)量。利用4.3加快 Robot訪問速度Hash的方法存儲(chǔ)URL,可以加速URL的訪問。另形成不同更新時(shí)間間隔的URL列表。不同的外。分配URL給不同的 Robot:把從源URL集合中URL一般都具有不同的更新時(shí)間間隔,在 Robot訪讀取的URL根據(jù)既定規(guī)則分配給不同的 Robot。問過程中,逐漸把URL根據(jù)其更新時(shí)間間隔歸并到不同的URL列表中, Robot則依據(jù)時(shí)間間隔訪參考文獻(xiàn)問,提高 Robot的搜索效率把地域相近的URL分配給同一個(gè) Robot采集,使每一個(gè) Robot所需訪向[1]李曉明,宏飛,王繼民信息檢索[M].北京:科學(xué)出的Web服務(wù)器的距離較近;開發(fā)多種類型的Ro[2]蘇新寧信息檢索理論與技術(shù)[M]北京科學(xué)技術(shù)文獻(xiàn)bot。包括:定題采集型、定點(diǎn)報(bào)道型和熱點(diǎn)追蹤出版社,2004型不同語種的 Robot,根據(jù)時(shí)差對(duì)Rbot分組等。[3]孫建軍,成穎信息檢索技術(shù)[M]北京:科學(xué)出版社,與服務(wù)器方協(xié)作。開發(fā)生存于某些站點(diǎn)服務(wù)器的 Robot,在服務(wù)器端跟蹤服務(wù)器上文檔的修改、[4]宋聚平搜索引擎中 ROBOT搜索算法的優(yōu)化[J情報(bào)刪除、增加等情況,根據(jù)不同情況向搜索引擎服務(wù)器主動(dòng)發(fā)送信息?；蛘咴诜?wù)器上生成一個(gè)關(guān)于[5】王YH中國(guó)煤化工僉索關(guān)鍵技術(shù)分析CNMHG服務(wù)器上文檔變更情況的特殊文件,當(dāng) Robot訪問