Exploration of General Crawlers (I): Crawlers for General Websites · English (unofficial) translations of posts at kexue.fm

This is a simplified version of the paper I submitted for this year’s Teddy Cup, Problem C. Although it only received a consolation prize, I personally feel that some of the ideas presented here have reference value for web crawling work. Therefore, I am sharing it for everyone’s reference.

Introduction

A crawler can be divided into two steps: 1. Downloading the webpage; 2. Extracting the required information from the webpage. Both steps present corresponding technical difficulties. For the first step, the difficulty lies in how to deal with the anti-crawling measures of major websites, such as IP blocking or CAPTCHAs if the access frequency is too high. This needs to be designed according to the different anti-crawling measures of different websites; theoretically, a universal solution does not exist. For the second step, the traditional approach is to design corresponding regular expressions. As website designs become increasingly diverse, writing regular expressions becomes correspondingly difficult.

Obviously, it is quite difficult to obtain a universal crawling solution using traditional regular expressions. However, if we step out of the limitations of regular expression thinking and look at the website from a global perspective, combining it with DOM tree parsing, we can obtain a fairly universal solution. Therefore, the main content of this article revolves around the second step of crawling. The work in this article is carried out in two parts: First, an information extraction scheme suitable for general websites is proposed; then, this scheme is refined and applied to information extraction from forums.

Process

It sounds sophisticated, but in fact, the idea can be summarized in one sentence, which is "subtraction": Webpage Content - Webpage Template = Effective Webpage Content. How is the webpage template obtained? It is the intersection of all webpages from the same website!

The specific process is roughly as follows:

Download the pages of the website to be crawled and parse them into DOM trees;

Compare the DOM trees of several pages to obtain the basic template of the website;

Traverse the DOM tree in a "depth-first" manner, numbering every node and leaf of the tree;

Compare the DOM tree of each page with the standard template; the differing parts are the effective text;

Further filter through some manual rules;

Using the node and leaf numbers as values, cluster and block the effective text.

Analysis

The following is a brief explanation of the above process.

Normal webpage source code is a mixture of HTML tags and effective text, and different websites have different templates, which brings difficulties to universal crawling. However, within different pages of the same website, there is uniformity between pages. In common terms: For the same website, different pages look similar; the only difference is the main content of the page.

Therefore, for a universal crawler, our design idea is: use different pages of the same website to construct a standard template for that website, and compare any page of the same website with the standard template. The differences are the effective text we need to extract. In this process, we use the DOM tree to perform syntactic parsing of the webpage source code.

HTML Code

A normal and relatively standard HTML page source code looks something like this:

<html>
    <head>
        <meta charset="UTF-8">
        <title>This is the Website Title</title>
    </head>
    <body>
        <div id="post_1">
            <h2>This is Article Title 1</h2>
            <a href="http://xxx.com"><img src="https://xxx.com/test.img"></a>
        </div>
        <div id="post_2">
            <h2>This is Article Title 2</h2>
            <a href="http://xxx.com"><img src="https://xxx.com/test.img"></a>
        </div>
        <div id="post_3">
            <h2>This is Article Title 3</h2>
            <a href="http://xxx.com"><img src="https://xxx.com/test.img"></a>
        </div>
    </body>
</html>

DOM Tree

We can parse the source code of an HTML page into a tree structure called a DOM tree, which stands for Document Object Model. It is a document object model that uses an object representation to represent the corresponding document structure and its content. The HTML page shown earlier can be represented as the following DOM tree structure:

In other words, a webpage is actually layers of nested HTML tags. Each tag is a node or leaf in the tree, and the text content of the webpage is within these tags. One benefit of parsing into a DOM tree is that we can ignore the interference of specific styles, for example:

<div id="content" class="content">
    <h2 id="title_1" class="title_1">The weather is nice today</h2>
    <h2 id="title_2" class="title_2">General Crawler Scheme</h2>
</div>

Here, div and h2 are fixed tags, but to assign different styles to different titles, different id and class are set for each <h2> tag. id and class can be set freely (or automatically generated according to some pattern), which creates difficulties for universal crawling. However, if parsed into a DOM tree, these specific markers will be automatically ignored, and only the universal div and h2 markers will be retained.

Another benefit of parsing into a DOM tree is that it can describe the hierarchical structure of the webpage, allowing us to traverse an HTML page in an orderly manner and divide the crawled content through the division of different page levels.

Standard Template

For the same website, we first download several pages and parse them into DOM trees. Then, we represent each node or leaf in the form of "tag path + tag text". For the HTML page shown earlier, its website title can be represented as "html_head_title_This is the Website Title", and its article title can be represented as "html_body_div_h2_This is Article Title 1". Note that not every tag has text content; for example, the <img> tag generally has no text. Here we only consider tags with text.

At this point, each webpage is represented as a set of tags. We can define the standard template of the website as: S = \bigcap_{h\in H} h where H is the set of all webpages of the website. That is to say, the standard template is the intersection of all webpages. At this point, extracting the effective text of the webpage is very simple: \text{effective} = h \setminus S In other words, the effective text of page h is the set difference between set h and set S.

Through this scheme, we can automatically build a standard template for any specified website, thereby extracting the effective text of the page. This process is established based on the assumption that "identical content between webpages is meaningless, while different content is what is worth crawling." In this way, regardless of the website’s hierarchical structure or whether there are embedded advertisements, we can effectively filter out ineffective text. Thus, we have obtained a universal crawling scheme.

Stream Generation

Although we define the standard template as the intersection of all pages, we do not need to crawl all pages before obtaining the standard template. At the beginning, we can use only two pages, take their intersection as the standard template, and then update the standard template every time a new page is crawled, making the standard template more and more accurate. This stream-style scheme meets the requirements of a production environment.

Rule Filtering

On some websites, different pages embed different codes. Therefore, after crawling with the previous scheme, these codes will also be saved, reducing the precision of the effective text. Thus, some filtering rules are needed to filter them out.

Engineering Rules

From a production perspective, one is usually willing to sacrifice some precision for higher speed. Therefore, obviously, the easiest method to implement for engineering is to count the ratio of Chinese to English characters in each segment of effective text obtained previously, and then based on the assumption that "webpage content is basically Chinese," we can safely remove parts with a low proportion of Chinese.

Of course, this will also remove information such as dates and usernames. Therefore, we must first identify dates and usernames to prevent accidental deletion. For dates, the formats are relatively fixed, such as "2017-04-15", "April 15, 2017", etc., and are usually accompanied by words like "Release Time" or "Published on", so they are relatively easy to identify. For usernames, they are usually a combination of Chinese, English, numbers, and underscores, and spaces are not allowed, while code happens to contain many spaces. Therefore, based on this filtering, usernames can be identified in advance.

So, the general rules are:

Text with date formats needs to be retained;

Text composed purely of a combination of Chinese, English, numbers, and underscores needs to be retained;

In the remaining parts, those where the proportion of Chinese is greater than a certain threshold need to be retained;

The rest of the content is filtered out directly.

Academic Solution

Engineering rules are simple and efficient but only suitable for specific situations. For example, the above rules are suitable for crawling general Chinese websites, but if it is an English website, these rules are not suitable.

In general, this is actually a question of judging whether a piece of text is natural language. We can use language models. A language model models the probability of a sentence. A sentence consists of n words w_1, w_2, \dots, w_n. We consider the probability: P(w_1, w_2, \dots, w_n) According to the formulas of probability theory, we get: P(w_1, w_2, \dots, w_n) = P(w_1)P(w_2|w_1)P(w_3|w_1, w_2) \dots P(w_n|w_1, w_2, \dots, w_{n-1}) The right side of the above equation is generally difficult to estimate accurately. For this reason, we make a truncation: the probability of the next word only depends on the probability of the previous word. In this way, we get: \label{eq:score} P(w_1, w_2, \dots, w_n) = P(w_1)P(w_2|w_1)P(w_3|w_2) \dots P(w_n|w_{n-1}) In this way, we only need to count the probability of each word P(w_i) and the co-occurrence probability of adjacent words P(w_{i-1}, w_i) to calculate the transition probability: P(w_i|w_{i-1}) = \frac{P(w_{i-1}, w_i)}{P(w_{i-1})}

With the transition probabilities, we can use Equation [eq:score] to score each piece of text and then set a threshold. Only if it is greater than this threshold do we conclude it is natural language and thus retain it. This scheme is applicable to all languages (only requiring the language model of the corresponding language) and is a theoretically more elegant model.

Please include the original address when reposting: https://kexue.fm/archives/4413

For more detailed reposting matters, please refer to: "Scientific Space FAQ"