【導讀】件以及主要參考文獻等。有著巨大的應用前景。搜索引擎作為一個輔助人們檢索信息的工具成為用戶訪問。萬維網(wǎng)的入口和指南。但是，這些通用性搜索引擎也存在著一定的局限性。結(jié)果包含大量用戶不關(guān)心的網(wǎng)頁。熟，網(wǎng)絡爬蟲是搜索引擎的重要組成部分。網(wǎng)絡上比較著名的開源爬蟲包括。網(wǎng)絡爬蟲最重要的是網(wǎng)頁搜索策略（廣度優(yōu)先和最。單的可在后臺自動運行的爬蟲程序。本課題研究的內(nèi)容是如何使網(wǎng)絡爬蟲靈活高效。網(wǎng)絡爬蟲應用寬度搜索技術(shù)。對url進行分析，去重。網(wǎng)絡爬蟲使用多線程。技術(shù)，讓爬蟲具備更強大的抓取能力。網(wǎng)絡爬蟲還要完成信息提取任務，對于抓。對網(wǎng)絡爬蟲的連接網(wǎng)絡設置連接及讀取時。間，避免無限制的等待。研究網(wǎng)絡爬蟲的原理并實現(xiàn)爬蟲的相關(guān)功能?！到y(tǒng)設計結(jié)束并再次檢查系統(tǒng)的可靠性。所以本課題的可行性較高。HTTP，NNTP和UNIX域協(xié)議[M]．北京：機械工業(yè)出版社，2021年1月.為了適應不同需求，使網(wǎng)絡爬蟲可以根據(jù)預先設定的主

　　

【正文】 a relatively large portion of the web (estimated at over 20%) is never reached. See [9] for a discussion of the graph structure of the web that leads to this phenomenon. If we view web pages as nodes in a graph, and hyperlinks as directed edges among these nodes, then crawling bees a process known in mathematical circles as graph traversal. Various strategies for graph traversal differ in their choice of which node among the nodes not yet explored to explore next. Two standard strategies for graph traversal are Depth First Search (DFS) and Breadth First Search (BFS) – they are easy to implement and taught in many introductory algorithms classes. (See for instance [34]). However, crawling the web is not a trivial programming exercise but a serious algorithmic and system design challenge because of the following two factors. 1. The web is very large. Currently, Google [20] claims to have indexed over 3 billion pages. Various studies [3, 27, 28] have indicated that, historically, the web has doubled every 912 months. 2. Web pages are changing rapidly. If “change” means “any change”, then about 29 40% of all web pages change weekly [12]. Even if we consider only pages that change by a third or more, about 7% of all web pages change weekly [17]. These two factors imply that to obtain a reasonably fresh and 679 plete snapshot of the web, a search engine must crawl at least 100 million pages per day. Therefore, step (a) must be executed about 1,000 times per second, and the membership test in step (c) must be done well over ten thousand times per second, against a set of URLs that is too large to store in main memory. In addition, crawlers typically use a distributed architecture to crawl more pages in parallel, which further plicates the membership test: it is possible that the membership question can only be answered by a peer node, not locally. A crucial way to speed up the membership test is to cache a (dynamic) subset of the “seen” URLs in main memory. The main goal of this paper is to investigate in depth several URL caching techniques for web crawling. We examined four practical techniques: random replacement, static cache, LRU, and CLOCK, and pared them against two theoretical limits: clairvoyant caching and infinite cache when run against a trace of a web crawl that issued over one billion HTTP requests. We found that simple caching techniques are extremely effective even at relatively small cache sizes such as 50,000 entries and show how these caches can be implemented very efficiently. The paper is anized as follows: Section 2 discusses the various crawling solutions proposed in the literature and how caching fits in their model. Section 3 presents an introduction to caching techniques and describes several theoretical and practical algorithms for caching. We implemented these algorithms under the experimental setup described in Section 4. The results of our simulations are depicted and discussed in Section 5, and our remendations for practical algorithms and data structures for URL caching are presented in Section 6. Section 7 contains our conclusions and directions for further research. 2. CRAWLING Web crawlers are almost as old as the web itself, and numerous crawling systems have been described in the literature. In this section, we present a brief survey of these 30 crawlers (in historical order) and then discuss why most of these crawlers could benefit from URL caching. The crawler used by the Inter Archive [10] employs multiple crawling processes, each of which performs an exhaustive crawl of 64 hosts at a time. The crawling processes save nonlocal URLs to disk。 at the end of a crawl, a batch job adds these URLs to the perhost seed sets of the next crawl. The original Google crawler, described in [7], implements the different crawler ponents as different processes. A single URL server process maintains the set of URLs to download。 crawling processes fetch pages。 indexing processes extract words and links。 and URL resolver processes convert relative into absolute URLs, which are then fed to the URL Server. The various processes municate via the file system. For the experiments described in this paper, we used the Mercator web crawler [22, 29]. Mercator uses a set of independent, municating web crawler processes. Each crawler process is responsible for a subset of all web servers。 the assignment of URLs to crawler processes is based on a hash of the URL’s host ponent. A crawler that discovers an URL for which it is not responsible sends this URL via TCP to the crawler that is responsible for it, batching URLs together to minimize TCP overhead. We describe Mercator in more detail in Section 4. Cho and GarciaMolina’s crawler [13] is similar to Mercator. The system is posed of multiple independent, municating web crawler processes (called “Cprocs”). Cho and GarciaMolina consider different schemes for partitioning the URL space, including URLbased (assigning an URL to a Cproc based on a hash of the entire URL), sitebased (assigning an URL to a Cproc based on a hash of the URL’s host part), and hierarchical (assigning an URL to a Cproc based on some property of the URL, such as its toplevel domain). The WebFountain crawler [16] is also posed of a set of independent, municating crawling processes (the “ants”). An ant that discovers an URL for which it is not responsible, sends this URL to a dedicated process (the “controller”), which forwards the URL to the appropriate ant. UbiCrawler (formerly known as Trovatore) [4, 5] is again posed of multiple 31 independent, municating web crawler processes. It also employs a controller process which oversees the crawling processes, detects process failures, and initiates failover to other