General-Purpose Crawler Exploration (II): Applying It to Forum Crawling

通用爬虫探索（二）：落实到论坛爬取上 苏剑林 · 2017-06-06 · Machine Learning website crawler

For pages with just a single valid content region — such as a blog post or a news article — the approach described earlier is basically sufficient on its own. But for sites with a fairly pronounced hierarchical structure, such as forums, we need to go a step further. That's because, although the steps above let us extract the valid text, the result lumps all of that text together into one blob.

Depth-First Traversal

To further "chunk" the content, we also need to make use of positional information from the DOM tree. As shown in the DOM tree diagram from the previous post, we need to assign an index to every node and leaf — which means we need some way of traversing the DOM tree. Here we adopt a "depth-first" scheme.

Depth-First Search (DFS) is an algorithm for traversing or searching a tree or graph. It walks along the depth of the tree, going as deep as possible along each branch before backtracking. Once all the edges incident to node v have been explored, the search backtracks to the node from which v was originally discovered. This process continues until all nodes reachable from the source node have been discovered. If unvisited nodes still remain, one of them is chosen as a new source node and the process repeats, continuing until every node has been visited. more

Applying depth-first search to the DOM tree from the previous post, we obtain the following numbering of nodes and leaves:

Numbering of the DOM tree

Exception Tags

The purpose of numbering the nodes is to support the clustering step that follows, and naturally we want the index differences within the same cluster to be as small as possible. Among the many HTML tags, quite a few serve only to indicate emphasis, hyperlinks, and the like — for example, the strong tag for bold text, the em tag for italics, and so on. These tags only change the visual style of the content, not its hierarchical level. So when traversing such tags, we can leave the index unchanged, which keeps tags at the same logical level closer together numerically and helps ensure the clustering works well.

The list of tags we allow as exceptions is shown below:

$$ \begin{array}{c|c} \hline 标签 & 意义 \\ \hline p/br & 换行\\ \hline strong/b & 加粗 \\ \hline em & 斜体 \\ \hline font & 字体样式 \\ \hline u & 下划线 \\ \hline a & 超链接 \\ \hline img & 插入图片\\ \hline h1/h2/h3/h4/h5 & 标题标记\\ \hline \end{array}$$

For the complete list of exception tags, please refer directly to the source code.

Difference-Peak Clustering

Once the valid text has been extracted via the steps above and indexed using the depth-first scheme, we end up with a sequence describing the positions of the text. What we find is that the index difference between pieces of text within the same block tends to be small, while the index difference between different blocks tends to be large. For instance, the title, date, and body of a single post have position indices that are close together; likewise, the title, date, and body of a reply within a given floor also have position indices that are close together, and so on, as illustrated below. This suggests we can use these position indices to further cluster the valid text.

Floor segmentation on a BBS

To this end, we examine the difference sequence of the position indices, and mark the actual floor boundaries with red dashed lines, giving the plot below:

After differencing the position index sequence, with the index of the difference sequence on the x-axis and the difference values on the y-axis.

The figure above reveals a clear pattern: the boundary between floors essentially coincides with a local maximum in the difference sequence. We can therefore exploit this to perform segmentation-style clustering, cutting the text at these local peaks. This clustering approach has some nice properties:

1. It automatically determines the number of clusters — we don't need to know in advance how many floors there are;
2. It adapts naturally to special cases. For example, the second- and third-to-last floors are noticeably wider than the others because they contain nested comments (i.e., "floors within floors"), which means more content — yet even so, the same pattern still holds.

This tells us that segmenting the text and separating out the different floors according to this pattern is fairly reliable. Moreover, this clustering step can be run repeatedly to accommodate different levels of granularity. In practice, for forums, running it roughly $\sim$–2 times is enough to obtain the floor segmentation.

Content Recognition

Finally, we need to classify the content within each text block, specific to the structure of a forum. To keep the crawler simple and efficient, we use relatively straightforward recognition methods here — essentially pure rule-based classification.

Title

Recognizing the title is relatively simple, since normal page source code contains a <title> field that generally holds the complete title information. So we just need to extract the title directly using a regular expression.

Date

In Chinese-language forums, dates commonly appear in a few formats:

2017-1-9 15:42
January 9, 2017, 15:42
3 hours ago
Yesterday 20:48

The first two formats are relatively easy to recognize, while the latter two are comparatively harder. These latter two formats mainly appear on posts that were published very recently on certain forums; after a day or two, they typically revert automatically to one of the first two formats.

Here, again in the interest of simplicity and robustness, we can adopt a compromise strategy: for posts within this short recent window, we don't attempt to parse the date at all, and simply store them together without one. From the perspective of continuous monitoring, this is fine — after a day or two, the date will become recognizable anyway. This preserves the real-time nature of the monitoring while keeping the program simpler and more reliable.

Author

In practice, identifying the author (the poster) turns out to be difficult, and we haven't found an effective algorithm for building a general-purpose author-recognition model. We've also concluded that identifying the poster isn't particularly valuable, so in the end we dropped this piece of recognition work.

Body Text

Once the date has been identified, we use it to split a single text region into an upper and a lower half, and treat one of these two halves as the body content. To determine which half is the body, we compute statistics over each half — specifically, comparing which half contains a higher proportion of Chinese characters — and treat the half with the higher proportion as the body.

Of course, from a more rigorous standpoint, one could follow the academic approach from the previous post and use a language model to judge which half is closer to natural language, thereby determining which part constitutes the body. However, that approach is relatively inefficient, and since our main concern is crawling Chinese-language content, we excluded it from our experiments.