背景
继上次使用Jsoup简易爬取POJ题面之后，我所在的校创小组最近又有了新任务，就是要标注算法题所涉及的知识点。人工标注肯定不现实，所以想到了模拟百度搜索并从CSDN博客上爬取相应的题目解析，和预先定义好的知识点集合进行匹配，统计匹配成功次数，按匹配次数从大到小排序，从而实现习题知识点的初步标注。下面以标注HDU OJ的题目知识点为例：
定义知识点集合
在开始爬取之前，我们要预先定义用于匹配爬取结果的知识点集合。事实证明知识点集合的粒度和广度对标注结果影响很大，所以如何定义一个合适的知识点集合还需要再三斟酌。这里我只是大致罗列了一些算法知识点，保存在项目resource目录的algorithm.txt中：
模拟
贪心
枚举
递归
构造
递推
后缀数组
树状数组
差分约束
dp
BFS
DFS
迭代加深搜索
记忆化搜索
分治
排序
动态规划
最短路
拓扑排序
最小生成树
网络流
二分
二分图
数论
组合数学
计算几何
博弈
线段树
字典树
并查集
KMP
AC自动机
凸包
三分
GCD
扩展欧几里得
尺取法
RMQ
IDA*
背包
莫队算法
Polya
定义知识点分类实体类
/**
* 分类实体类
*/
public class Category {
private int index;
private int occurCount;
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public int getOccurCount() {
return occurCount;
}
public void setOccurCount(int occurCount) {
this.occurCount = occurCount;
}
@Override
public String toString() {
return "Category{" +
"name=" + Main.getCandidate().get(index) +
", occurCount=" + occurCount +
'}';
}
}
引入Jsoup依赖
由于构建的是Maven项目，可以直接在pom.xml文件里引入Jsoup的相关依赖：
<dependency>
<groupId>org.jsoup</groupId>
<artifactId>jsoup</artifactId>
<version>1.11.2</version>
</dependency>
定义爬虫工具类
下面是整个项目的核心，用于模拟百度搜索和爬取所需信息。
import org.jsoup.Jsoup;
import org.jsoup.nodes.Document;
import org.jsoup.nodes.Element;
import org.jsoup.select.Elements;
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
/**
* 爬虫工具类
*/
import org.jsoup.Jsoup;
import org.jsoup.nodes.Document;
import org.jsoup.nodes.Element;
import org.jsoup.select.Elements;
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
/**
* 爬虫工具类
*/
public class CrawlUtils {
public static void crawl(int begin,int end) throws IOException {
//用百度搜索关键词HDU+题号+CSDN博客
for (int pid = begin; pid <= end; pid++) {
Document doc = Jsoup.connect("https://www.baidu.com/s?ie=utf-8&wd=HDU"
+ pid + "CSDN博客").get();
Elements elements = doc.select("h3.t");
//处理公共资源，加锁
synchronized(CrawlUtils.class){
List<String> arrayList = Main.getCandidate();
Category[] c = Main.getCategories();
for (int i = 0;i < c.length;i++) {
c[i] = new Category();
c[i].setIndex(i);
c[i].setOccurCount(0);
}
System.out.println("HDU" + pid + "分析结果：");
//选取百度的前5个链接，分别解析
for (int k = 0;k < 5;k++) {
//如果题号不匹配，直接跳过该链接
if(!elements.get(k).text().contains(String.valueOf(pid)))
continue;
String link = elements.get(k).selectFirst("a").attr("href");
//对于每个链接页面，爬取article标签中的文本
String text = Jsoup.connect(link).timeout(30000).get().select("article").text();
//将文本和预先定义的算法集合进行匹配，统计不同算法出现次数
for (int i = 0;i < arrayList.size();i++) {
int start = 0;
while(start < text.length() && text.indexOf(arrayList.get(i),start) != -1){
c[i].setOccurCount(c[i].getOccurCount() + 1);
start = text.indexOf(arrayList.get(i),start) + 1;
}
}
}
//按照出现次数从高到低排序
Arrays.sort(c, new Comparator<Category>() {
public int compare(Category o1, Category o2) {
return o2.getOccurCount() - o1.getOccurCount();
}
});
//输出出现次数大于1的算法标签
int tot = 0;
for(int i = 0;i < 50;i++){
if(c[i].getOccurCount() > 0){
System.out.println(c[i]);
tot++;
}
}
if(tot == 0){
System.out.println("未匹配到算法分类");
}
System.out.println();
}
}
}
}
为提高爬取效率，我们采用了多线程爬虫，即用多个线程同时爬取不同题目范围的URL信息。特别要注意的是，在本例中多个爬虫线程共用一个控制台，即控制台属于公共资源。在处理公共资源时（输出爬取结果），需要加锁，否则多个线程的爬取结果将交替输出。但不可以对整个crawl方法加锁，这样锁的粒度太大，多线程爬虫的效率没有得到发挥，即同一时刻只允许有一个线程爬取数据，其他线程都被同步阻塞，这显然是不符合预想的。
定义爬虫线程类
import java.io.IOException;
/**
* 爬虫线程
*/
public class CrawlerThread implements Runnable{
private int start;
private int end;
public CrawlerThread(int start, int end) {
this.start = start;
this.end = end;
}
public void run() {
try {
CrawlUtils.crawl(start,end);
} catch (IOException e) {
e.printStackTrace();
}
}
}
编写主方法开始爬取
为了提高效率，开了8个线程爬取。
import java.io.*;
import java.util.*;
public class Main {
private static List<String> candidate = new ArrayList<String>(); //存放候选的算法分类
private static Category[] categories = new Category[50];//保存不同分类，包括名称和出现次数
static { //导入候选的算法分类
InputStream is = null;
try {
is = new FileInputStream("./resource/algorithm.txt");
} catch (FileNotFoundException e) {
e.printStackTrace();
}
BufferedReader br = null;
try {
br = new BufferedReader(new InputStreamReader(is,"GBK"));
String line;
while ((line = br.readLine()) != null) {
candidate.add(line);
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
br.close();
is.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
public static void main(String[] args) throws IOException {
//开8个线程爬取
Thread th[] = new Thread[8];
for(int i = 0;i < 8;i++){
th[i] = new Thread(new CrawlerThread((i + 2) * 500,(i + 2) * 500 + 500));
th[i].start();
}
}
public static List<String> getCandidate() {
return candidate;
}
public static void setCandidate(List<String> candidate) {
Main.candidate = candidate;
}
public static Category[] getCategories() {
return categories;
}
public static void setCategories(Category[] categories) {
Main.categories = categories;
}
}
爬取结果
爬取结果
网友评论