【正文】 接形式互相聯(lián)系在一起，每一網(wǎng)頁對應(yīng)一個超鏈接，也稱統(tǒng)一資源定位符（URL）?！∨佬胁呗詼\析 寬度或深度優(yōu)先搜索策略搜索引擎所用的第一代網(wǎng)絡(luò)爬蟲主要是基于傳統(tǒng)的圖算法, 如寬度優(yōu)先或深度優(yōu)先算法來索引整個 Web, 一個核心的 U RL 集被用來作為一個種子集合, 這種算法遞歸的跟蹤超鏈接到其它頁面, 而通常不管頁面的內(nèi)容, 因為最終的目標(biāo)是這種跟蹤能覆蓋整個 Web. 這種策略通常用在通用搜索引擎中,因為通用搜索引擎獲得的網(wǎng)頁越多越好, 沒有特定的要求.　寬度優(yōu)先搜索算法寬度優(yōu)先搜索算法(又稱廣度優(yōu)先搜索) 是最簡便的圖的搜索算法之一 , 這一算法也是很多重要的圖的算法的原型. Dijkstra 單源最短路徑算法和 Prim 最的寬度遍歷樹的節(jié)點, 如果發(fā)現(xiàn)目標(biāo) , 則算法中止 . 該算法的設(shè)計和實現(xiàn)相對簡單, 屬于盲目搜索 . 在目前為覆蓋盡可能多的網(wǎng)頁, 一般使用寬度優(yōu)先搜索方法. 也有很多研究將寬度優(yōu)先搜索策略應(yīng)用于聚焦爬蟲中. 其基本思想是認(rèn)為與初始 U RL 在一定鏈接距離內(nèi)的網(wǎng)頁具有主題相關(guān)性的概率很大. 另外一種方法是將寬度優(yōu)先搜索與網(wǎng)頁過濾技術(shù)結(jié)合使用, 先用廣度優(yōu)先策略抓取網(wǎng)頁, 再將其中無關(guān)的網(wǎng)頁過濾掉. 這些方法的缺點在于, 隨著抓取網(wǎng)頁的增多 , 大量的無關(guān)網(wǎng)頁將被下載并過濾, 算法的效率將變低.　深度優(yōu)先搜索深度優(yōu)先搜索所遵循的搜索策略是盡可能“深”地搜索圖. 在深度優(yōu)先搜索中, 對于最新發(fā)現(xiàn)的頂點, 如果它還有以此為起點而未探測到的邊 , 就沿此邊繼續(xù)漢下去. 當(dāng)結(jié)點 v 的所有邊都己被探尋過, 搜索將回溯到發(fā)現(xiàn)結(jié)點 v 有那條邊的始結(jié)點. 這一過程一直進(jìn)行到已發(fā)現(xiàn)從源結(jié)點可達(dá)的所有結(jié)點為止. 如果還存在未被發(fā)現(xiàn)的結(jié)點, 則選擇其中一個作為源結(jié)點并重復(fù)以上過程, 整個進(jìn)程反復(fù)進(jìn)行直到所有結(jié)點都被發(fā)現(xiàn)為止. 深度優(yōu)先在很多情況下會導(dǎo)致爬蟲的陷入( trapped) 問題 , 所以它既不是完備的, 也不是最優(yōu)的. 聚焦搜索策略基于第一代網(wǎng)絡(luò)爬蟲的搜索引擎抓取的網(wǎng)頁一般少于 1 000 000 個網(wǎng)頁, 極少重新搜集網(wǎng)頁并去刷新索引. 而且其檢索速度非常慢, 一般都要等待 10 s 甚至更長的時間. 隨著網(wǎng)頁頁信息的指數(shù)級增長及動態(tài)變化, 這些通用搜索引擎的局限性越來越大, 隨著科學(xué)技術(shù)的發(fā)展, 定向抓取相關(guān)網(wǎng)頁資源的聚焦爬蟲便應(yīng), 根據(jù)“最好優(yōu)先原則”進(jìn)行訪問, 快速、有效地獲得更多的與主題相關(guān)的頁面, 主要通過內(nèi)容和Web 的鏈接結(jié)構(gòu)來指導(dǎo)進(jìn)一步的頁面抓取 [ 2 ]. 聚焦爬蟲會給它所下載下來的頁面分配一個評價分, 然后根據(jù)得分排序, 最后插入到一個隊列中. 最好的下一個搜索將通過對彈出隊列中的第一個頁面進(jìn)行分析而執(zhí)行, 這種策略保證爬蟲能優(yōu)先跟蹤那些最有可能鏈接到目標(biāo)頁面的頁面. 決定網(wǎng)絡(luò)爬蟲搜索策略的關(guān)鍵是如何評價鏈接價值, 即鏈接價值的計算方法, 不同的價值評價方法計算出的鏈接的價值不同, 表現(xiàn)出的鏈接的“重要程度”也不同, 從而決定了不同的搜索策略. 由于鏈接包含于頁面之中,而通常具有較高價值的頁面包含的鏈接也具有較高的價值, 因而對鏈接價值的評價有時也轉(zhuǎn)換為對頁面價值的評價. 這種策略通常運用在專業(yè)搜索引擎中, 因為這種搜索引擎只關(guān)心某一特定主題的頁面. 基于內(nèi)容評價的搜索策略基于內(nèi)容評價的搜索策略[ 3, 4 ] , 主要是根據(jù)主題(如關(guān)鍵詞、主題相關(guān)文檔) 與鏈接文本的相似度來評價鏈接價值的高低, 并以此決定其搜索策略: 鏈接文本是指鏈接周圍的說明文字和鏈接 U RL 上的文字信息 , 相似度的評價通常采用以下公式:sim (d i, d j ) =Σmk= 1w ik w jk(Σmk= 1w 2ik ) (Σmk= 1w 2jk )其中, di 為新文本的特征向量 , d j 為第 j 類的中心向量,m 為特征向量的維數(shù),wk 為向量的第 K Web 頁面不同于傳統(tǒng)的文本 , 它是一種半結(jié)構(gòu)化的文檔, 包含許多結(jié)構(gòu)信息 Web 頁面不是單獨存在的, 頁面中的鏈接指示了頁面之間的相互關(guān)系, 因而有些學(xué)者提出了基于鏈接結(jié)構(gòu)評價鏈接價值的方法. 基于鏈接結(jié)構(gòu)評價的搜索策略基于鏈接結(jié)構(gòu)評價的搜索策略, 是通過對 Web 頁面之間相互引用關(guān)系的分析來確定鏈接的重要性, 進(jìn)而決定鏈接訪問順序的方法. 通常認(rèn)為有較多入鏈或出鏈的頁面具有較高的價值. PageRank 和 Hits 是其中具有代表性的算法.　PageRank 算法基于鏈接評價的搜索引擎的優(yōu)秀代表是 Google ( , 它獨創(chuàng)的“鏈接評價體系”(PageRank 算法) 是基于這樣一種認(rèn)識 , 一個網(wǎng)頁的重要性取決于它被其它網(wǎng)頁鏈接的數(shù)量, 特別是一些已經(jīng)被認(rèn)定是“重要”的網(wǎng)頁的鏈接數(shù)量. PageRank 算法最初用于 Google 搜索引擎信息檢索中對查詢結(jié)果的排序過程[ 5 ] , 近年來被應(yīng)用于網(wǎng)絡(luò)爬蟲對鏈接重要性的評價, PageRank 算法中, 頁面的價值通常用頁面的 PageRank 值表示, 若設(shè)頁面 p 的 PageRank 值為PR (p ) , 則 PR (p ) 采用如下迭代公式計算:PR (p ) = C 1T+ (1 C) Σ C∈in (p )PR (p )當(dāng)成功創(chuàng)建一個 URL 對象后，我們調(diào)用 openConnection 函數(shù)建立與URL 的通信，此時，我們就獲得了一個 URLConnection 對象的引用，URLConnection 類包含了許多與網(wǎng)絡(luò)上的 URL 通信的函數(shù)。當(dāng)需要替換時，鏈表最后的位置就是最近最少被命中位置，我們只需要將新的內(nèi)容放在鏈表前面，淘汰鏈表最后的位置就實現(xiàn)了LRU 算法。不過，我沒有用過這種方式，有機(jī)會可以嘗試一下。去重，可以考慮對某個鍵，存在一個值，這個值就是那個鍵的狀態(tài)。從另一個方面來說，非常少的碰撞，對于搜索引擎的爬蟲是可以容忍的。而且，這里使用的是 URL 作為鍵，URL 字符串也占用了很大的存儲空間。試想，如果已經(jīng)下載了 100 億網(wǎng)頁，那么對應(yīng)著 100 億個鏈接，也就是這個檢查 URL是否重復(fù)的記事本文件就要存儲這 100 億 URL，況且，很多 URL 字符串的長度也不小，占用存儲空間不說，查找效率超級低下，這種方案肯定放棄。 基于磁盤的順序存儲這里，就是指把每個已經(jīng)下載過的 URL 進(jìn)行順序存儲。非常容易想到，在搜索引擎系統(tǒng)中建立一個全局的專門用來檢測，是否某一個 URL 對應(yīng)的網(wǎng)頁文件曾經(jīng)被下載過的 URL 存儲庫，這就是方案。以下在新浪新聞頁面為例，新浪一個新聞頁面大小為 50～60k，每個頁面有 90～100 個 URL，如果每秒下載 10 個頁面，就會產(chǎn)生 900～1000 次的 URL 排重操作，每次排重操作都要在幾百萬至幾千萬的 URL 庫中去查詢。這種情況非常類似于操作系統(tǒng)中虛擬儲存器管理。JAVA 使用 synchronized 關(guān)鍵字來定義程序中要求線程同步的部分。由于 JAVA 中的每個對象都是從 Object 繼承來的。 多線程同步當(dāng)同時運行的相互獨立的線程需要共享數(shù)據(jù)并且需要考慮其他線程的狀態(tài)時，就需要使用一套機(jī)制使得這些線程同步，避免在爭用資源時發(fā)生沖突，甚至發(fā)生死鎖。如果線程在運行（Running）狀態(tài)中因為 I/O 阻塞，等待鍵盤鍵入，調(diào)用了線程的 sleep 方法，調(diào)用了對象的 wait()方法等，則線程將進(jìn)入阻塞狀態(tài)，直到這些阻塞原因被解除，如：IO 完成，鍵盤輸入了數(shù)據(jù)，調(diào)用 sleep 方法后的睡眠時間到以及其他線程調(diào)用了對象的 notify 或 notifyAll 方法來喚醒這個因為等待而阻塞的線程等，線程將返回到 Runnable 狀態(tài)重新等待調(diào)度程序調(diào)度，注意，被阻塞的線程不會直接返回到 Running 狀態(tài)，而是重新回到 Runnable 狀態(tài)等待線程調(diào)度程序的調(diào)用。然后，調(diào)用線程的 start()方法，來向線程調(diào)度程序（通常是 JVM 或操作系統(tǒng)）注冊一個線程，這個時候，這個線程一切就緒，就等待 CPU 時間了。從上面兩種創(chuàng)建線程的方法可以看出，如果繼承 Thread 類，則這個類本身可以調(diào)用 start 方法，也就是說將這個繼承了 Thread 的類當(dāng)作目標(biāo)對象；而如果實現(xiàn) Runnable 接口，則這個類必須被當(dāng)作其他線程的目標(biāo)對象。使用 start()方法，線程進(jìn)入 Runnable 狀態(tài)，它將線程調(diào)度器注冊這個線程。Thread(ThreadGroup group,Runnable target)。Thread(Runnable target,String name)。Thread 有很多個構(gòu)造器來創(chuàng)建一個線程（Thread）實例：Thread()。它由 JVM 創(chuàng)建并調(diào)用 JAVA 應(yīng)用程序的 main（）方法。在 JAVA 語言中，多線程的機(jī)制是通過虛擬 CPU 來實現(xiàn)的。多線程（MultiThread）擴(kuò)展了多進(jìn)程（multiProcess）操作的概念，將任務(wù)的劃分下降到了程序級別，使得各個程序似乎可以在同一個時間內(nèi)執(zhí)行多個任務(wù)。那么，為什么我們看不出任何的中斷現(xiàn)象呢？這是因為，相對于我們的感覺，它的速度實在太快了。對于我來說，這些操作都是同步進(jìn)行的，我不需要等一首歌曲放完了再來編輯我的論文。第二章 相關(guān)技術(shù)介紹 JAVA 線程 線程概述幾乎每種操作系統(tǒng)都支持線程的概念—進(jìn)程就是在某種程度上相互隔離的，獨立運行的程序。高效，優(yōu)秀的爬蟲程序可以使人們在互聯(lián)網(wǎng)上尋找到更及時，更準(zhǔn)確的信息。爬蟲程序是一個自動獲取網(wǎng)頁的程序?，F(xiàn)在比較流行的搜索引擎，比如 google，百度，它們爬蟲程序的技術(shù)內(nèi)幕一般都不公開。搜索引擎搜集互聯(lián)網(wǎng)上數(shù)以億計的網(wǎng)頁，并為每個詞建立索引。 JAVA。ABSTRACT SPIDER is a program which can auto collect informations from inter. SPIDER can collect data for search engines, also can be a Directional information collector, collects specifically informations from some web sites, such as HR informations, house rent informations.In this paper, use JAVA implements a breadthfirst algorithm multithread SPDIER. This paper expatiates some major problems of SPIDER: why to use breadthfirst crawling strategy, and how to implement breadthfirst crawling。本文通過 JAVA 實現(xiàn)了一個基于廣度優(yōu)先算法的多線程爬蟲程序。通過網(wǎng)絡(luò)爬蟲不僅能夠為搜索引擎采集網(wǎng)絡(luò)信息，而且可以作為定向信息采集器，定向采集某些網(wǎng)站下的特定信息，如招聘信息，租房信息等。 【關(guān)鍵字】網(wǎng)絡(luò)爬蟲；JAVA；廣度優(yōu)先；多線程。 HTML code parse. etc. This SPIDER can collect URLs from one web site, and store URLs into database. 【KEY WORD】SPIDER。這使得人們在網(wǎng)上找到所需的信息越來越困難，這種情況下搜索引擎應(yīng)運而生。以何種策略偏歷互聯(lián)網(wǎng)上的網(wǎng)頁，也成了爬蟲程序主要的研究方向。 采用爬行深度、頁面導(dǎo)入鏈接量分析等方法, 限制從程序下載不相關(guān)的 Web 頁的選擇性爬行程序等等。不同的搜索引擎，會根據(jù)對搜索結(jié)果的不同需求，選擇最合適的爬行策略來搜集互聯(lián)網(wǎng)上的信息。通過實現(xiàn)此爬蟲程序可以定點搜集某一站點的 URLs，如果需要搜集其他信息，可以在解析 URLs 的同時，解析獲取相應(yīng)信息。比如，我在 Microsoft Word 編寫本論文的時候，我還打開了一個 mp3 播放器來播放音樂，偶爾的，我還會再編輯Word 的同時讓我的機(jī)器執(zhí)行一個打印任務(wù)，而且我還喜歡通過 IE 從網(wǎng)上下載一個 Flash 動畫。CPU 不斷的在這些程序之間“跳躍”執(zhí)行。因此，雖然我們看到的都是一些同步的操作，但實際上，對于計算機(jī)而言，它在某個時間點上只能執(zhí)行一個程序，除非你的計算機(jī)是多 CPU 的。 JAVA 線程模型我們知道，計算機(jī)程序得以執(zhí)行的三個要素是：CPU，程序代碼，可存取的數(shù)據(jù)。我們知道，每個 JAVA 應(yīng)用程序都至少有一個線程，這就是所謂的主線程。 創(chuàng)建線程 創(chuàng)建線程方式一在 JAVA 中創(chuàng)建線程的一種方式是通過 Thread 來實現(xiàn)的。創(chuàng)建一個線程，并指定一個目標(biāo)。創(chuàng)建一個名為 name 的線程。每個線程都是通過某個特定 Thread 對象所對應(yīng)的方法 run()來完成其操作的，方法 run()稱為線程體。在使用 Runnable 接口時，不能直接創(chuàng)建所需類的對象并運行它，而是必須從 Thread 類的一個實例內(nèi)部運行它。當(dāng)使用 new 來新建一個線程時，它處于 New 狀態(tài)，這個時候，線程并未進(jìn)行任何操作。你不能調(diào)用 restart方法來重新開始一個處于死亡狀態(tài)的線程，但是，你可以調(diào)用處于死亡狀態(tài)的線程對象的各個方法。注意，因為這個方法會引起線程的安全問題，已經(jīng)被不推薦使用了，所以，不要再程序調(diào)用這個方法。JAVA 中從 Object 對象繼承來的每個對象