Shulou(Shulou.com)06/03 Report--

Traversal strategy is the core problem of the crawler. In the crawler system, the URL queue to be fetched is a very important part. The order in which the URL in the URL queue to be crawled is also a very important question, because it involves the method of determining the order of the URL by crawling that page first and then which page to crawl. There are mainly the following crawler strategies:

First, depth-first traversal strategy:

Depth-first traversal test means that the web crawler will start from the start page, follow one link at a time, process the link on this line, and then go to the next start page to continue tracking the link. Let's take the following figure as an example:

The traversal path is: A-F-G E-H-I B C D

However, when we are doing crawlers, the depth-first strategy may not be applicable to all situations. If depth-first strategy strays into infinite branches (infinite depth), it is impossible to find the target node.

Second, breadth-first traversal strategy:

The breadth-first strategy is to search according to the level of the tree, and if the search is not completed at this level, it will not go to the next level of search. That is, one level of search is completed first, and then the next level is carried out, which is also called hierarchical processing. Let's also take the above figure as an example:

The traversal path is: the first layer traversal: A-B-C-D-E-F, the second layer traversal: Gmurh, and the third layer traversal: I.

However, the breadth-first traversal strategy is a blind search, it does not consider the possible location of the results, will thoroughly search the whole picture, so it is less efficient, but if you want to cover as many pages as possible, breadth-first search method is a better choice.

Third, part of the strategy of PageRank:

The idea of PageRank algorithm: for the downloaded web pages, together with the URL of the URL queue to be crawled, a collection of web pages is formed, and the PageRank value of each page is calculated (PageRank algorithm reference: PageRank algorithm-from principle to implementation). After calculation, the URL in the queue is arranged according to the value of the page level, and the URL pages are crawled sequentially.

If you crawl a new web page each time, the calculated PageRank value is obviously too inefficient. The compromise is to save enough web pages to calculate once.

The following figure is a schematic diagram of the strategy at the web page level:

Set every 3 web pages downloaded to calculate the new PageRank. At this time, 3 web pages have been downloaded to the local area. These three web pages contain links to {4je 5je 6}, that is, the URL queue to be crawled. How to determine the download order?

The six web pages are formed into a new set, and the value of the PageRank calculated for this set is calculated. In this way, the corresponding page level value is obtained, and the download order is assumed to be 5pc4, 6, sorted from big to small. When 55 pages are downloaded, the link is extracted and pointed to page 8. At this time, 8 is given a temporary PageRank value. If this value is greater than the PageRank of 4 and 6, then download page 8 first. Such a continuous cycle, that is, the formation of an incomplete web page-level strategy calculation ideas.

Fourth, OPIC strategy (online page importance calculation):

Basic idea: before the start of the algorithm, give all pages the same initial cash (cash). After downloading a page P, apportion P's cash to all the links analyzed from P, and empty P's cash. All pages in the URL queue to be crawled are sorted by the amount of cash.

The difference between PageRank and PageRank is that each time of PageRank needs iterative calculation, while OPIC strategy does not need iterative process, so the calculation speed is much faster than that of PageRank, so it is suitable for real-time computing.

Fifth, the strategy of giving priority to major stations:

Strategic thinking: take the website as a unit to select the importance of web pages. For the pages to be crawled in the URL queue, according to the website they belong to, if which website has the most pages waiting to be downloaded, then give priority to downloading these links, and its essential idea tends to give priority to downloading large websites. Because large websites tend to contain more pages. In view of the fact that large websites are often the content of famous enterprises, and their web pages are generally of high quality, this idea is simple, but it has a certain basis. The experimental results show that the effect of this algorithm is also slightly prior to the width-first traversal strategy.

Peanut agent dynamic exchange IP software can achieve a national city IP automatic switching, tens of millions of dynamic IP pool, support filtering, support for computer and mobile phone multi-terminal use, tens of thousands of random dial lines, 24-hour uninterrupted supply of dynamic IP.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.