【導(dǎo)讀】境、工作目的等。有著巨大的應(yīng)用前景。搜索引擎作為一個(gè)輔助人們檢索信息的工具成為用戶訪問(wèn)。萬(wàn)維網(wǎng)的入口和指南。但是，這些通用性搜索引擎也存在著一定的局限性。結(jié)果包含大量用戶不關(guān)心的網(wǎng)頁(yè)。能夠?yàn)榫W(wǎng)絡(luò)爬蟲(chóng)實(shí)現(xiàn)更深入的主題相關(guān)性，提供滿足特定搜索需求的網(wǎng)絡(luò)爬蟲(chóng)。[1]Winter．中文搜索引擎技術(shù)解密：網(wǎng)絡(luò)蜘蛛[M]．北京：人民郵電出版社，[4]GaryStevens．TCP-IP協(xié)議詳解卷3：TCP事務(wù)協(xié)議，HTTP，NNTP和UNIX域協(xié)議[M]．北京：機(jī)械工業(yè)出版社，2021年1月.與技術(shù)參數(shù)，并根據(jù)課題性質(zhì)對(duì)學(xué)生提出具體要求。對(duì)url進(jìn)行分析，去重。網(wǎng)絡(luò)爬蟲(chóng)使用多線程。技術(shù)，讓爬蟲(chóng)具備更強(qiáng)大的抓取能力。對(duì)網(wǎng)絡(luò)爬蟲(chóng)的連接網(wǎng)絡(luò)設(shè)置連接及讀取時(shí)間，避免無(wú)限制的等待。研究網(wǎng)絡(luò)爬蟲(chóng)的原理并實(shí)現(xiàn)爬蟲(chóng)的相關(guān)功能。搜索，并最終得到需要的數(shù)據(jù)。件以及主要參考文獻(xiàn)等。熟，網(wǎng)絡(luò)爬蟲(chóng)是搜索引擎的重要組成部分?！到y(tǒng)設(shè)計(jì)結(jié)束并再次檢查系統(tǒng)的可靠性。學(xué)術(shù)文庫(kù)[M]．北京：科學(xué)出版社，2021年04月.

　　

【正文】 st 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. INTRODUCTION A recent Pew Foundation study [31] states that “Search engines have bee an indispensable utility for Inter users” and estimates that as of mid2021, slightly 天津大學(xué) 2021屆本科生畢業(yè)設(shè)計(jì)（論文） 28 over 50% of all Americans have used web search to find information. Hence, the technology that powers web search is of enormous practical interest. In this paper, we concentrate on one aspect of the search technology, namely the process of collecting web pages that eventually constitute the search engine corpus. Search engines collect pages in many ways, among them direct URL submission, paid inclusion, and URL extraction from nonweb sources, but the bulk of the corpus is obtained by recursively exploring the web, a process known as crawling or SPIDERing. 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) Crawling typically starts from a set of seed URLs, made up of URLs obtained by other means as described above and/or made up of URLs collected during previous crawls. Sometimes crawls are started from a single well connected page, or a directory such as , but in this case 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 天津大學(xué) 2021屆本科生畢業(yè)設(shè)計(jì)（論文） 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 天津大學(xué) 2021屆本科生畢業(yè)設(shè)計(jì)（論文） 30