背景
繼上次使用Jsoup簡(jiǎn)易爬取POJ題面之后界轩，我所在的校創(chuàng)小組最近又有了新任務(wù)，就是要標(biāo)注算法題所涉及的知識(shí)點(diǎn)衔瓮。人工標(biāo)注肯定不現(xiàn)實(shí)浊猾，所以想到了模擬百度搜索并從CSDN博客上爬取相應(yīng)的題目解析，和預(yù)先定義好的知識(shí)點(diǎn)集合進(jìn)行匹配报辱，統(tǒng)計(jì)匹配成功次數(shù)与殃，按匹配次數(shù)從大到小排序，從而實(shí)現(xiàn)習(xí)題知識(shí)點(diǎn)的初步標(biāo)注碍现。下面以標(biāo)注HDU OJ的題目知識(shí)點(diǎn)為例：
定義知識(shí)點(diǎn)集合
在開始爬取之前幅疼，我們要預(yù)先定義用于匹配爬取結(jié)果的知識(shí)點(diǎn)集合。事實(shí)證明知識(shí)點(diǎn)集合的粒度和廣度對(duì)標(biāo)注結(jié)果影響很大昼接，所以如何定義一個(gè)合適的知識(shí)點(diǎn)集合還需要再三斟酌爽篷。這里我只是大致羅列了一些算法知識(shí)點(diǎn)，保存在項(xiàng)目resource目錄的algorithm.txt中：
模擬
貪心
枚舉
遞歸
構(gòu)造
遞推
后綴數(shù)組
樹狀數(shù)組
差分約束
dp
BFS
DFS
迭代加深搜索
記憶化搜索
分治
排序
動(dòng)態(tài)規(guī)劃
最短路
拓?fù)渑判?最小生成樹
網(wǎng)絡(luò)流
二分
二分圖
數(shù)論
組合數(shù)學(xué)
計(jì)算幾何
博弈
線段樹
字典樹
并查集
KMP
AC自動(dòng)機(jī)
凸包
三分
GCD
擴(kuò)展歐幾里得
尺取法
RMQ
IDA*
背包
莫隊(duì)算法
Polya
定義知識(shí)點(diǎn)分類實(shí)體類
/**
* 分類實(shí)體類
*/
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依賴
由于構(gòu)建的是Maven項(xiàng)目慢睡，可以直接在pom.xml文件里引入Jsoup的相關(guān)依賴：
<dependency>
<groupId>org.jsoup</groupId>
<artifactId>jsoup</artifactId>
<version>1.11.2</version>
</dependency>
定義爬蟲工具類
下面是整個(gè)項(xiàng)目的核心逐工，用于模擬百度搜索和爬取所需信息。
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 {
//用百度搜索關(guān)鍵詞HDU+題號(hào)+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 + "分析結(jié)果：");
//選取百度的前5個(gè)鏈接泪喊，分別解析
for (int k = 0;k < 5;k++) {
//如果題號(hào)不匹配，直接跳過該鏈接
if(!elements.get(k).text().contains(String.valueOf(pid)))
continue;
String link = elements.get(k).selectFirst("a").attr("href");
//對(duì)于每個(gè)鏈接頁面髓涯，爬取article標(biāo)簽中的文本
String text = Jsoup.connect(link).timeout(30000).get().select("article").text();
//將文本和預(yù)先定義的算法集合進(jìn)行匹配袒啼，統(tǒng)計(jì)不同算法出現(xiàn)次數(shù)
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;
}
}
}
//按照出現(xiàn)次數(shù)從高到低排序
Arrays.sort(c, new Comparator<Category>() {
public int compare(Category o1, Category o2) {
return o2.getOccurCount() - o1.getOccurCount();
}
});
//輸出出現(xiàn)次數(shù)大于1的算法標(biāo)簽
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();
}
}
}
}
為提高爬取效率，我們采用了多線程爬蟲，即用多個(gè)線程同時(shí)爬取不同題目范圍的URL信息蚓再。特別要注意的是滑肉，在本例中多個(gè)爬蟲線程共用一個(gè)控制臺(tái)，即控制臺(tái)屬于公共資源摘仅。在處理公共資源時(shí)（輸出爬取結(jié)果）靶庙，需要加鎖，否則多個(gè)線程的爬取結(jié)果將交替輸出娃属。但不可以對(duì)整個(gè)crawl方法加鎖六荒，這樣鎖的粒度太大，多線程爬蟲的效率沒有得到發(fā)揮矾端，即同一時(shí)刻只允許有一個(gè)線程爬取數(shù)據(jù)恬吕，其他線程都被同步阻塞，這顯然是不符合預(yù)想的须床。
定義爬蟲線程類
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個(gè)線程爬取渐裂。
import java.io.*;
import java.util.*;
public class Main {
private static List<String> candidate = new ArrayList<String>(); //存放候選的算法分類
private static Category[] categories = new Category[50];//保存不同分類豺旬，包括名稱和出現(xiàn)次數(shù)
static { //導(dǎo)入候選的算法分類
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個(gè)線程爬取
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;
}
}
爬取結(jié)果
爬取結(jié)果
