【正文】 之間相互引用關(guān)系的分析來確定鏈接的重要性, 進(jìn)而決定鏈接訪問順序的方法. 通常認(rèn)為有較多入鏈或出鏈的頁面具有較高的價值. PageRank 和 Hits 是其中具有代表性的算法.　PageRank 算法基于鏈接評價的搜索引擎的優(yōu)秀代表是 Google ( , 它獨(dú)創(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 ) 采用如下迭代公式計(jì)算:PR (p ) = C 1T+ (1 C) Σ C∈in (p )PR (p )當(dāng)需要替換時，鏈表最后的位置就是最近最少被命中位置，我們只需要將新的內(nèi)容放在鏈表前面，淘汰鏈表最后的位置就實(shí)現(xiàn)了LRU 算法。去重，可以考慮對某個鍵，存在一個值，這個值就是那個鍵的狀態(tài)。而且，這里使用的是 URL 作為鍵，URL 字符串也占用了很大的存儲空間。 基于磁盤的順序存儲這里，就是指把每個已經(jīng)下載過的 URL 進(jìn)行順序存儲。以下在新浪新聞頁面為例，新浪一個新聞頁面大小為 50～60k，每個頁面有 90～100 個 URL，如果每秒下載 10 個頁面，就會產(chǎn)生 900～1000 次的 URL 排重操作，每次排重操作都要在幾百萬至幾千萬的 URL 庫中去查詢。JAVA 使用 synchronized 關(guān)鍵字來定義程序中要求線程同步的部分。 多線程同步當(dāng)同時運(yùn)行的相互獨(dú)立的線程需要共享數(shù)據(jù)并且需要考慮其他線程的狀態(tài)時，就需要使用一套機(jī)制使得這些線程同步，避免在爭用資源時發(fā)生沖突，甚至發(fā)生死鎖。然后，調(diào)用線程的 start()方法，來向線程調(diào)度程序（通常是 JVM 或操作系統(tǒng)）注冊一個線程，這個時候，這個線程一切就緒，就等待 CPU 時間了。使用 start()方法，線程進(jìn)入 Runnable 狀態(tài)，它將線程調(diào)度器注冊這個線程。Thread(Runnable target,String name)。它由 JVM 創(chuàng)建并調(diào)用 JAVA 應(yīng)用程序的 main（）方法。多線程（MultiThread）擴(kuò)展了多進(jìn)程（multiProcess）操作的概念，將任務(wù)的劃分下降到了程序級別，使得各個程序似乎可以在同一個時間內(nèi)執(zhí)行多個任務(wù)。對于我來說，這些操作都是同步進(jìn)行的，我不需要等一首歌曲放完了再來編輯我的論文。高效，優(yōu)秀的爬蟲程序可以使人們在互聯(lián)網(wǎng)上尋找到更及時，更準(zhǔn)確的信息?，F(xiàn)在比較流行的搜索引擎，比如 google，百度，它們爬蟲程序的技術(shù)內(nèi)幕一般都不公開。 JAVA。本文通過 JAVA 實(shí)現(xiàn)了一個基于廣度優(yōu)先算法的多線程爬蟲程序。 【關(guān)鍵字】網(wǎng)絡(luò)爬蟲；JAVA；廣度優(yōu)先；多線程。這使得人們在網(wǎng)上找到所需的信息越來越困難，這種情況下搜索引擎應(yīng)運(yùn)而生。 采用爬行深度、頁面導(dǎo)入鏈接量分析等方法, 限制從程序下載不相關(guān)的 Web 頁的選擇性爬行程序等等。通過實(shí)現(xiàn)此爬蟲程序可以定點(diǎn)搜集某一站點(diǎn)的 URLs，如果需要搜集其他信息，可以在解析 URLs 的同時，解析獲取相應(yīng)信息。CPU 不斷的在這些程序之間“跳躍”執(zhí)行。 JAVA 線程模型我們知道，計(jì)算機(jī)程序得以執(zhí)行的三個要素是：CPU，程序代碼，可存取的數(shù)據(jù)。 創(chuàng)建線程 創(chuàng)建線程方式一在 JAVA 中創(chuàng)建線程的一種方式是通過 Thread 來實(shí)現(xiàn)的。創(chuàng)建一個名為 name 的線程。在使用 Runnable 接口時，不能直接創(chuàng)建所需類的對象并運(yùn)行它，而是必須從 Thread 類的一個實(shí)例內(nèi)部運(yùn)行它。你不能調(diào)用 restart方法來重新開始一個處于死亡狀態(tài)的線程，但是，你可以調(diào)用處于死亡狀態(tài)的線程對象的各個方法。JAVA 中從 Object 對象繼承來的每個對象都有一個單獨(dú)的鎖。在持續(xù)下載的過程中，新的 URL非常少，還是以新浪網(wǎng)舉例，1 天 24 小時中總共出現(xiàn)的新 URL 也就是 10000左右。而想要控制這種重復(fù)性下載問題，就要考慮下載所依據(jù)的超鏈接，只要能夠控制待下載的 URL 不重復(fù)，基本可以解決同一個網(wǎng)頁重復(fù)下載的問題。這種方式幾乎沒有人考慮使用了，但是這種檢查的思想是非常直觀的。另外，MD5 算法能夠?qū)⑷魏巫址畨嚎s為 128 位整數(shù)，并映射為物理地址，而且 MD5 進(jìn)行 Hash 映射碰撞的幾率非常小，這點(diǎn)非常好。 基于布隆過濾器（Bloom Filter）的存儲使用布隆過濾器，設(shè)計(jì)多個 Hash 函數(shù)，也就是對每個字符串進(jìn)行映射是經(jīng)過多個 Hash 函數(shù)進(jìn)行映射，映射到一個二進(jìn)制向量上，這種方式充分利用了比特位。如：URL url=new URL（ ）；如果傳遞無效的 URL 給 URL 對象，該對象會拋出 MalformedURLException異常。 Hub 表示一個 Web 頁面指向其它頁面的數(shù)量, 即該頁面的出度值. 網(wǎng)頁的出度值越大 , 其 Hub 值越高. 由于 Hub 值高的頁面通常都提供了指向權(quán)威頁面的鏈接, 因而起到了隱含說明某主題頁面權(quán)威性的作用.HITS (Hyperlink Induced Top ic Search) 算法是利用 Hub246。 SPIDER 體系結(jié)構(gòu)此爬蟲程序主要分為三個部分：任務(wù)執(zhí)行端，任務(wù)調(diào)度端，數(shù)據(jù)服務(wù)端。DateBaseConnect 類：用于提供數(shù)據(jù)庫連接。考慮使用哪一種方式的前提是，構(gòu)造的 SPIDER 程序必須能夠訪問非常大的 Web 站點(diǎn)。然后線程 1 會再從 URL 隊(duì)列中獲取新的 URL，下載 HTML 代碼，并解析出 URLs，再加入到 URL 隊(duì)列中去。如圖 ，假如 a 代表初始 URL，bcd 為以 a 獲取的 3 個 URLs，efg 為以b 獲取的 URLs，以此類推。第三個方框?yàn)?，解?b 對應(yīng) HTML 獲取URLs：efg ，同時刪除 URL：b。比如 href=”url”這樣情況，我們就可以通過截取雙引號之間的內(nèi)容來獲取 URL；如果是 href=’url’這種情況，我們就需要截取單引號之間的內(nèi)容來獲取 URL；或者有些是 href=url，我們需要以等號為開始標(biāo)記，而這種情況通常結(jié)尾是空格或者符號。這些格式的 URL 是無法獲取 HTML 代碼的，也就不可能進(jìn)行 URL 解析。圖 第五章 系統(tǒng)實(shí)現(xiàn) 實(shí)現(xiàn)工具操作系統(tǒng)是 winXP。while (s == null) {s = ()。connection = (HttpURLConnection) ()。這個方法是通過調(diào)用 JAVA 里面的 URL 這個類，可以用給定的 URL 構(gòu)造這個類的一個實(shí)例，然后通過 openStream()這個方法得到 HTML 代碼的數(shù)據(jù)流，然后再一行一行地把數(shù)據(jù)流轉(zhuǎn)換成 String 字符串，再用 StringBuffer 將這些字符串拼接成一個完整的 HTML 代碼。之間的這段字符串即為 URL。String url = 。if (isSiteInsideUrl(url, urlQueueManager)) {if (!(url)) {(url)。當(dāng)?shù)玫竭@些完整的 URL 地址以后，我們需要對其進(jìn)行過濾。所以我們可以通過判斷 URLs 中是否包含站點(diǎn) host 就可以了。 URL 隊(duì)列管理 URL 消重處理URL 消重處理，我是用 LRU 算法加上 MD5 壓縮算法來實(shí)現(xiàn)的。它的具體構(gòu)造如下：public class LRULinkedHashMapK, V extends LinkedHashMapK, V {private static final long serialVersionUID = 1L。return (key)。這樣當(dāng)進(jìn)行 URL 去重處理時，會認(rèn)為它們不是一個 URL。但是因?yàn)?URL 等待隊(duì)列會非常巨大，所以我將 URL 等待隊(duì)列設(shè)計(jì)成 3 段式。下面是具體實(shí)現(xiàn)的 JAVA 代碼。)。對于 MYSQL 數(shù)據(jù)庫，可以使用 LIMIT 這個關(guān)鍵字。while (()) {((url))。下面是 JAVA 程序連接MYSQL 數(shù)據(jù)庫的代碼。5 分鐘內(nèi)總共爬行出了 2201 個 URL。所以這種 URL 因該過濾掉。我在 SpiderWorker 的 run 方法寫入這樣一段代碼：(線程 + biaoji+運(yùn)行 )。但是在功能細(xì)節(jié)上還有很多不足，比如系統(tǒng)不夠優(yōu)化，功能不夠強(qiáng)大，沒有解析網(wǎng)頁信息。外文資料原文Efficient URL Caching for World Wide Web CrawlingAndrei Z. BroderIBM TJ Watson Research Center19 Skyline DrHawthorne, NY 10532Marc NajorkMicrosoft Research1065 La AvenidaMountain View, CA 94043Ja L. WienerHewlett Packard Labs1501 Page Mill RoadPalo Alto, CA 94304ABSTRACTCrawling the web is deceptively simple: the basic algorithm is (a)Fetch a page (b) Parse it to extract all linked URLs (c) For all the URLs not seen before, repeat (a)–(c). However, the size of the web (estimated at over 4 billion pages) and its rate of change (estimated at 7% per week) move this plan from a trivial programming exercise to a serious algorithmic and system design challenge. Indeed, these two factors alone imply that for a reasonably fresh and plete crawl of the web, step (a) must be executed about a thousand times per second, and thus the membership test (c) must be done well over ten thousand times per second against a set too large to store in main memory. This requires a distributed architecture, which further plicates the membership test.A crucial way to speed up the test is to cache, that is, to store in main memory a (dynamic) subset of the “seen” URLs. The main goal of this paper is to carefully investigate several URL caching techniques for web crawling. We consider both practical algorithms: random replacement, static cache, LRU, and CLOCK, and theoretical limits: clairvoyant caching and infinite cache. We performed about 1,800 simulations using these algorithms with various cache sizes, using actual log data extracted from a massive 33 day web crawl that issued over one billion HTTP requests. Our main conclusion is that caching is very effective – in our setup, a cache of roughly 50,000 entries can achieve a hit rate of almost 80%. Interestingly, this cache size falls at a critical point: a substantially smaller cache is much less effective while a substantially larger cache brings little additional benefit. We conjecture that such critical points are inherent to our problem and venture an explanation for this phenomenon.1. INTROD