Robot算法分析

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