程式扎記: [ Java Crawler ] 寬度優先爬蟲和帶偏好的爬蟲

標籤

2011年10月11日 星期二

[ Java Crawler ] 寬度優先爬蟲和帶偏好的爬蟲


參考至 自己動手寫網路爬蟲 ISBN:9866143309
前言 :
在開始這個主題前, 可能你必須具備了解 HttpHttp Status code 與 一些簡單的 Algorithm 如 Tree 的 廣度優先 Visited. 幸運的是這些並不會太難, 且網路有相當多資源在解釋或說明它們. 這裡我們要介紹的是 Crawler 俗稱爬蟲, 而爬蟲的用途則是檢查網際網路並將相關的網頁抓取過來.

網際網路可以看成一個超級大的圖型結構, 而每個頁面可以看成是一個"節點". 頁面的連結則可以看成圖的 "有向邊". 因此能透過圖的檢查方式對這個網際網路這個超級大的 "圖" 進行存取. 而圖的檢查通常可以分為 寬度優先檢查 與 深度優先檢查 兩種方式. 但是深度優先檢查可能會在深度檢查時進入了"無止盡"的黑洞而不可自拔, 因此大多數爬蟲都不採用這種方式. 另一方面在爬取時, 有時候也不能完全按照寬度優先檢查方式, 而是給待檢查的網頁賦予一定的優先順序, 根據這個優先順序進行檢查, 這種方式稱為帶偏好的檢查.

圖的寬度優先檢查 :
在開始介紹爬蟲前先來了解一下寬度優先的檢查過程. 圖的寬度優先檢查 (BFS) 演算法是一個分層搜尋的過程, 和樹的層序檢查演算法相同. 首先在圖中選取一個節點作為起始節點, 然後按照階層檢查方式一層層的進行存取. 事實上寬度優先使用 佇列資料結構 來完成所以一層層的存取, 實際演算法如下所列 :
(1) 頂點 V 入佇列
(2) 當佇列非空時繼續往下執行, 否則退出並完成演算法.
(3) 出佇列, 並存取該節點 V 後標示該節點已被存取.
(4) 尋找頂點 V 的相鄰頂點, 如果該頂點 col 未被存與過則將該頂點進佇列.
(5) 前往步驟 (2)

沒圖沒真相, 下面我們以圖示方式介紹寬度優先檢查過程 :


在上圖的檢查過程中, 出佇列的節點順序即是圖的寬度優先檢查存取順序. 由上可以知道存取順序為 :
A -> B -> C -> D -> E -> F -> H -> G -> I

接著我們會著重講解如何對網際網路進行寬度優先檢查.

寬度優先檢查網際網路 :
實際上的爬蟲種子連結就像寬度優先檢查的節點, 可以有多個而如何定義一個連結的子檢點? 每個連結對應一個 HTML 頁面或是其他檔案 (如 word, pdf, jpg 等), 在這些檔案中, 只有 HTML 頁面中有相應的 "子節點", 這些子節點就是頁面上對應的超連結. 整個寬度優先爬蟲過程就是從一系列的種子節點開始, 接著把網頁的 "子節點" (也就是超連結) 分析出來並放入佇列依次進行抓取. 被處理過的連結需放入一張表 (通常稱為 Visited 表) 中. 每次新處理一個連結前都須檢視這個連結是否已經存在於 Visited 表中, 如果存在代表已經處理過並跳過, 否則進行下一步處理. 過程如下 :


如上圖所示, 初始的 URL 位址是爬蟲系統中提供的種子 URL (一般是系統設定檔中給定). 當解析這些種子 URL 網頁時, 上面的連結會產生新的 URL 並進行下面步驟 :
(1) 把解析出來的連結與 Visited 表中的連結進行比較, 若 Visited 表中不存在此連結表示未被處理過.
(2) 如果未被處理過則放進 TODO 表中.
(3) 處理完畢後, 再次從 TODO 表中取得下一條連結並放入 Visited 中.
(4) 針對處理連結網頁繼續上述過程直到 TODO 表為空.

之所以採用寬度優先為爬蟲處理網頁的策略, 主要原因有三點 :
重要的網頁往往離種子比較近.
* www 的實際深度最多能達到 17 層, 但到達某個網頁總存在一條很短路徑, 而寬度優先檢查會以最快速度到達這個網頁.
寬度優先有利於多爬蟲的合作抓取, 多爬蟲合作通常先抓站內連結, 抓取封閉性強.

底下我們會來看看實作的部分.

Java 寬度優先爬蟲範例 :
這裡使用 Java 實現一個簡單的爬蟲, 其中用到 HttpClient 和 HttpParser 兩個開放原代碼工具包. 有關這兩個開源包的使用說明, 請參考對應官網上的教學. 下面為程式的執行流程 :


首先需要有一個 "URL 佇列", 這裡使用 LinkedList 來實現這個佇列 :
- Queue.java :
  1. package john.crawler;  
  2.   
  3. import java.util.LinkedList;  
  4.   
  5. /** 
  6. * 數據結構隊列 
  7. */  
  8. public class Queue {  
  9.   
  10.     private LinkedList queue=new LinkedList();  
  11.       
  12.     public void enQueue(T t)  
  13.     {  
  14.         queue.addLast(t);  
  15.     }  
  16.       
  17.     public T deQueue()  
  18.     {  
  19.         return queue.removeFirst();  
  20.     }  
  21.       
  22.     public boolean isQueueEmpty()  
  23.     {  
  24.         return queue.isEmpty();  
  25.     }  
  26.       
  27.     public boolean contians(T t)  
  28.     {  
  29.         return queue.contains(t);  
  30.     }  
  31.       
  32.     public boolean empty()  
  33.     {  
  34.         return queue.isEmpty();  
  35.     }  
  36.       
  37.     public void clear(){queue.clear();}  
  38. }  

除了 URL 佇列外, 在爬蟲過程中還需要一個資料結構來記錄已經存取過的 URL. 每當要存取一個 URL 時候, 首先要確保該 URL 未存取過(如果存取過則忽略該筆 URL). 而這個資料結構要有兩個特點 :
* 結構中儲存的 URL 不能重複
* 能夠快速地尋找(因為 URL 數目可能非常多!)

針對以上特點, 這裡使用 HashSet 作為儲存已存取過URL 的資料結構 :
- LinkDB.java :
  1. package john.crawler;  
  2.   
  3. import java.util.HashSet;  
  4. import java.util.Set;  
  5.   
  6. /** 
  7. * 用來保存已經訪問過Url 和待訪問的Url 的類 
  8. */  
  9. public class LinkDB {  
  10.     // 已訪問的url 集合  
  11.     private static Set visitedUrl = new HashSet();  
  12.     // 待訪問的url 集合  
  13.     private static Queue unVisitedUrl = new Queue();  
  14.   
  15.     public static void reset()  
  16.     {  
  17.         visitedUrl.clear();  
  18.         unVisitedUrl.clear();  
  19.     }  
  20.       
  21.     public static Queue getUnVisitedUrl() {  
  22.         return unVisitedUrl;  
  23.     }  
  24.   
  25.     public static void addVisitedUrl(String url) {  
  26.         visitedUrl.add(url);  
  27.     }  
  28.   
  29.     public static void removeVisitedUrl(String url) {  
  30.         visitedUrl.remove(url);  
  31.     }  
  32.   
  33.     public static String unVisitedUrlDeQueue() {  
  34.         return unVisitedUrl.deQueue();  
  35.     }  
  36.   
  37.     // 保證每個url 只被訪問一次  
  38.     public static void addUnvisitedUrl(String url) {  
  39.         if (url != null && !url.trim().equals("") && !visitedUrl.contains(url)  
  40.                 && !unVisitedUrl.contians(url))  
  41.             unVisitedUrl.enQueue(url);  
  42.     }  
  43.   
  44.     public static int getVisitedUrlNum() {  
  45.         return visitedUrl.size();  
  46.     }  
  47.   
  48.     public static boolean unVisitedUrlsEmpty() {  
  49.         return unVisitedUrl.empty();  
  50.     }  
  51. }  

下面程式碼用途為下載某 URL 對應到的網路資源. 它考慮到請求逾時以及避掉儲存網頁遇到不合法檔案字元的問題 :
- FileDownLoader.java :
  1. package john.crawler;  
  2.   
  3. import java.io.DataOutputStream;  
  4. import java.io.File;  
  5. import java.io.FileOutputStream;  
  6. import java.io.IOException;  
  7. import java.io.InputStream;  
  8.   
  9. import org.apache.commons.httpclient.DefaultHttpMethodRetryHandler;  
  10. import org.apache.commons.httpclient.HttpClient;  
  11. import org.apache.commons.httpclient.HttpException;  
  12. import org.apache.commons.httpclient.HttpStatus;  
  13. import org.apache.commons.httpclient.methods.GetMethod;  
  14. import org.apache.commons.httpclient.params.HttpMethodParams;  
  15.   
  16. public class FileDownLoader {  
  17.     private String  charset="";  
  18.     private long    fileSize=-1;  
  19.     /** 
  20.      * 根據url 和網頁類型生成需要保存的網頁的文件名 去除掉url 中非文件名字符 
  21.      */  
  22.     public String getFileNameByUrl(String url, String contentType) {  
  23.         url = url.substring(7);// remove http://  
  24.         if (contentType.indexOf("html") != -1)// text/html  
  25.         {  
  26.             url = url.replaceAll("[\\?/:*|<>\"]""_") + ".html";  
  27.             return url;  
  28.         }   
  29.         else// 如application/pdf  
  30.         {  
  31.             //System.out.println("\t[FileDownLoader] ContentType="+contentType+"("+contentType.substring(contentType.lastIndexOf("/") + 1)+")");  
  32.             return url.replaceAll("[\\?/:*|<>\"]""_") + "."  
  33.                     + contentType.substring(contentType.lastIndexOf("/") + 1);  
  34.         }  
  35.     }  
  36.   
  37.     /** 
  38.      * 保存網頁字節數組到本地文件 filePath 為要保存的文件的相對地址 
  39.      */  
  40.     private void saveToLocal(byte[] data, String filePath) {  
  41.         try {  
  42.             DataOutputStream out = new DataOutputStream(new FileOutputStream(  
  43.                     new File(filePath)));  
  44.             for (int i = 0; i < data.length; i++)  
  45.                 out.write(data[i]);  
  46.             out.flush();  
  47.             out.close();  
  48.         } catch (IOException e) {  
  49.             e.printStackTrace();  
  50.         }  
  51.     }  
  52.       
  53.     private long saveToLocal(InputStream is, String filePath)  
  54.     {  
  55.         try{  
  56.             DataOutputStream out = new DataOutputStream(new FileOutputStream(new File(filePath)));  
  57.             long dbytes = 0;  
  58.             byte b[] = new byte[1024];  
  59.             int r;  
  60.             while((r=is.read(b))>0)  
  61.             {  
  62.                 for(int i=0; i
  63.                 dbytes+=r;  
  64.             }  
  65.             out.flush();  
  66.             out.close();  
  67.             is.close();  
  68.             return dbytes;  
  69.         }  
  70.         catch(IOException e)  
  71.         {  
  72.             e.printStackTrace();  
  73.         }  
  74.         return -1;  
  75.     }  
  76.   
  77.       
  78.     public void getCharset(String cntType)  
  79.     {  
  80.         if(cntType!=null && !cntType.isEmpty())  
  81.         {  
  82.             String[] params = cntType.split(";");  
  83.             for(String param:params)  
  84.             {  
  85.                 param = param.trim();  
  86.                 if(param.startsWith("charset="))  
  87.                 {  
  88.                     charset=param.substring(8, param.length());  
  89.                 }  
  90.             }  
  91.         }  
  92.     }  
  93.       
  94.     /* 下載url 指向的網頁 */  
  95.     public String downloadFile(String url) {  
  96.         if(url==null || url.isEmpty())  
  97.         {  
  98.             System.out.println("\t[FileDownLoader] Illegal URL='"+url+"'...");  
  99.         }  
  100.         charset="";  
  101.         fileSize = -1;  
  102.         String filePath = null;  
  103.         /* 1.生成HttpClinet 對象並設置參數 */  
  104.         HttpClient httpClient = new HttpClient();  
  105.         // 設置Http 連接超時5s  
  106.         httpClient.getHttpConnectionManager().getParams()  
  107.                 .setConnectionTimeout(5000);  
  108.   
  109.         /* 2.生成GetMethod 對象並設置參數 */  
  110.         GetMethod getMethod = new GetMethod(url);  
  111.         // 設置get 請求超時5s  
  112.         getMethod.getParams().setParameter(HttpMethodParams.SO_TIMEOUT, 5000);  
  113.         // 設置請求重試處理  
  114.         getMethod.getParams().setParameter(HttpMethodParams.RETRY_HANDLER,  
  115.                 new DefaultHttpMethodRetryHandler());  
  116.   
  117.         /* 3.執行HTTP GET 請求 */  
  118.         try {  
  119.             int statusCode = httpClient.executeMethod(getMethod);  
  120.             // 判斷訪問的狀態碼  
  121.             if (statusCode != HttpStatus.SC_OK) {  
  122.                 System.err.println("Method failed: "  
  123.                         + getMethod.getStatusLine());  
  124.                 filePath = null;  
  125.             }  
  126.   
  127.             /* 4.處理HTTP 響應內容 */  
  128.             String cntType = getMethod.getResponseHeader("Content-Type").getValue();  
  129.             // byte[] responseBody = getMethod.getResponseBody();// 讀取為字節數組  
  130.             // 根據網頁url 生成保存時的文件名  
  131.             filePath = "temp/"  
  132.                     + getFileNameByUrl(url, cntType);  
  133.             getCharset(cntType);  
  134.             fileSize = saveToLocal(getMethod.getResponseBodyAsStream(), filePath);  
  135.         } catch (HttpException e) {  
  136.             // 發生致命的異常,可能是協議不對或者返回的內容有問題  
  137.             System.out.println("Please check your provided http address!");  
  138.             e.printStackTrace();  
  139.         } catch (IOException e) {  
  140.             // 發生網絡異常  
  141.             e.printStackTrace();  
  142.         } finally {  
  143.             // 釋放連接  
  144.             getMethod.releaseConnection();  
  145.         }  
  146.         return filePath;  
  147.     }  
  148.       
  149.     public long getFileSize() {  
  150.         return fileSize;  
  151.     }  
  152.   
  153.     public String getFileSizeInStr()  
  154.     {  
  155.         if(fileSize<0)  
  156.             return "0 bytes";  
  157.         else if(fileSize<1000)  
  158.             return fileSize+" bytes";  
  159.         else   
  160.         {  
  161.             long kb = fileSize/1000;  
  162.             return kb+"k bytes or "+fileSize+" bytes";  
  163.         }  
  164.     }  
  165.       
  166.     public String getCharset() {  
  167.         return charset;  
  168.     }  
  169.   
  170.     // 測試的main 方法  
  171.     public static void main(String[] args) {  
  172.         FileDownLoader downLoader = new FileDownLoader();  
  173.         downLoader.downloadFile("http://www.twt.edu.cn");  
  174.     }  
  175. }  

接下來我們還需要從以下載的網頁分析其中的連結, 這個工作可以透過 Html Parser 來做到. 透過底下類別的方法 extracLinks 便可以將某個頁面上的所有連結回傳 :
- HtmlParserTool.java :
  1. package john.crawler;  
  2.   
  3. import java.util.HashSet;  
  4. import java.util.Set;  
  5.   
  6. import org.htmlparser.Node;  
  7. import org.htmlparser.NodeFilter;  
  8. import org.htmlparser.Parser;  
  9. import org.htmlparser.filters.NodeClassFilter;  
  10. import org.htmlparser.filters.OrFilter;  
  11. import org.htmlparser.tags.LinkTag;  
  12. import org.htmlparser.tags.ImageTag;  
  13. import org.htmlparser.util.NodeList;  
  14. import org.htmlparser.util.ParserException;  
  15.   
  16. public class HtmlParserTool {  
  17.     public static Set extracLinks(String host, String url, LinkFilter filter)  
  18.     {  
  19.         return extracLinksWithEncoding(host , url, null, filter);  
  20.     }  
  21.     // 獲取一個網站上的鏈接,filter 用來過濾鏈接  
  22.     public static Set extracLinksWithEncoding(String host, String url, String encoding, LinkFilter filter) {  
  23.   
  24.         Set links = new HashSet();  
  25.         try {  
  26.             Parser parser = new Parser(url);  
  27.             if(encoding==null||encoding.isEmpty()) parser.setEncoding("gb2312");  
  28.             else parser.setEncoding(encoding);  
  29.             // 過濾標籤的filter,用來提取frame 標籤裡的src 屬性所表示的鏈接  
  30.             NodeFilter frameFilter = new NodeFilter() {  
  31.                 @Override  
  32.                 public boolean accept(Node node) {  
  33.                     if (node.getText().startsWith("frame src="))  
  34.                         return true;  
  35.                     return false;  
  36.                 }  
  37.             };  
  38.             // OrFilter 來設置過濾 標籤,和 標籤  
  39.             OrFilter linkFilter = new OrFilter(new NodeClassFilter(LinkTag.class), frameFilter);  
  40.             OrFilter linkImgFilter = new OrFilter(new NodeClassFilter(ImageTag.class), linkFilter);  
  41.             // 得到所有經過過濾的標籤  
  42.             NodeList list = parser.extractAllNodesThatMatch(linkImgFilter);  
  43.             for (int i = 0; i < list.size(); i++) {  
  44.                 Node tag = list.elementAt(i);  
  45.                 if (tag instanceof LinkTag)// 標籤  
  46.                 {  
  47.                     LinkTag link = (LinkTag) tag;  
  48.                     String linkUrl = link.getLink();// url  
  49.                     if (filter==null || filter.accept(linkUrl))   
  50.                         if(linkUrl.startsWith("/")) links.add(host+linkUrl);  
  51.                         else links.add(linkUrl);  
  52.                 }   
  53.                 else if(tag instanceof ImageTag)// 標籤  
  54.                 {  
  55.                     ImageTag imgTag = (ImageTag) tag;  
  56.                     String imgSrc = imgTag.getImageURL();  
  57.                     if(filter==null || filter.accept(imgSrc))   
  58.                         if(imgSrc.startsWith("/")) links.add(host+imgSrc);  
  59.                         else links.add(imgSrc);  
  60.                 }  
  61.                 else  
  62.                 {  
  63.                     // 提取frame 裡src 屬性的鏈接如  
  64.                     String frame = tag.getText();  
  65.                     System.out.println("\t[HtmlParserTool] Parsing frame="+frame+"...");  
  66.                     int start = frame.indexOf("src=");  
  67.                     frame = frame.substring(start);  
  68.                     int end = frame.indexOf(" ");  
  69.                     if (end == -1)  
  70.                         end = frame.indexOf(">");  
  71.                     String frameUrl = frame.substring(5, end - 1);  
  72.                     if (filter==null || filter.accept(frameUrl))  
  73.                         links.add(frameUrl);  
  74.                 }  
  75.             }  
  76.         } catch (ParserException e) {  
  77.             e.printStackTrace();  
  78.         }  
  79.         return links;  
  80.     }  
  81. }  

最後來看看該爬蟲的主程式 : 
- Crawler.java : 
  1. package john.crawler;  
  2.   
  3. import java.util.Observable;  
  4. import java.util.Set;  
  5. import java.util.regex.Matcher;  
  6. import java.util.regex.Pattern;  
  7.   
  8. public class Crawler extends Observable{  
  9.     private boolean isRecursive = false;    /*決定是否 recursive 的從下載網頁取出連結入佇列*/  
  10.     private boolean isHostonly = false;     /*是否只取該 URL 相同 Host 下的資源*/  
  11.     //private String acceptHost = "";  
  12.     private Pattern ptn = Pattern.compile("(http://[a-zA-Z0-9.]+)/.*");  
  13.   
  14.     public Crawler(boolean isR, boolean isH) {isRecursive = isR; isHostonly=isH;}  
  15.     public Crawler() {}  
  16.   
  17.     //public Crawler(String ahost) {  
  18.     //  this.acceptHost = ahost;  
  19.     //}  
  20.   
  21.     protected void printf(String fmt, Object...args)  
  22.     {  
  23.         String log = String.format(fmt, args);  
  24.         System.out.print(log);  
  25.         setChanged();  
  26.         notifyObservers(log);  
  27.     }  
  28.       
  29.     /* 使用種子url 初始化URL 隊列 */  
  30.     private void initCrawlerWithSeeds(String[] seeds) {  
  31.         LinkDB.reset();  
  32.         for (int i = 0; i < seeds.length; i++)  
  33.             LinkDB.addUnvisitedUrl(seeds[i]);  
  34.     }  
  35.   
  36.     protected String getHost(String url)  
  37.     {  
  38.         Matcher mhr = ptn.matcher(url);  
  39.         if(mhr.find()) return mhr.group(1);  
  40.         else return null;  
  41.     }  
  42.       
  43.     public long crawling(String url)  
  44.     {  
  45.         return crawling(new String[]{url});  
  46.     }  
  47.       
  48.     /* 爬取方法 */  
  49.     public long crawling(String[] seeds) {  
  50.         long totalSize = 0;  
  51.         // 初始化URL 隊列  
  52.         initCrawlerWithSeeds(seeds);  
  53.         // 循環條件:待抓取的鏈接不空且抓取的網頁不多於1000  
  54.         while (!LinkDB.unVisitedUrlsEmpty() && LinkDB.getVisitedUrlNum() <= 100) {  
  55.             // 隊頭URL 出對  
  56.             String visitUrl = LinkDB.unVisitedUrlDeQueue();  
  57.             if(visitUrl.endsWith(".gif") ||  
  58.                visitUrl.endsWith(".jpg") ||  
  59.                visitUrl == null)  
  60.                         continue;  
  61.               
  62.             FileDownLoader downLoader = new FileDownLoader();  
  63.             // 下載網頁  
  64.             printf("\t[Crawler] Download page=%s...",visitUrl);  
  65.             downLoader.downloadFile(visitUrl);  
  66.             totalSize+=downLoader.getFileSize();  
  67.             printf("Done! (Charset=%s, Size=%s)\n",downLoader.getCharset(),downLoader.getFileSizeInStr());  
  68.             // 該url 放入到已訪問的URL 中  
  69.             LinkDB.addVisitedUrl(visitUrl);  
  70.               
  71.             // 提取出下載網頁中的URL  
  72.             if(isRecursive)  
  73.             {  
  74.                 LinkFilter filter = null;  
  75.                 final String host = getHost(visitUrl);  
  76.                 if(isHostonly)  
  77.                 {  
  78.                       
  79.                     filter = new LinkFilter() {  
  80.                         // 提取以http://www.twt.edu.cn開頭的鏈接  
  81.                         public boolean accept(String url) {  
  82.                             //System.out.println("\t[LinkFilter] check "+url+" with "+host);  
  83.                             if (url.startsWith(host)) return true;  
  84.                             else if(url.startsWith("/")) return true;  
  85.                             else  
  86.                             {  
  87.                                 //printf("\t[Crawler] Bypass '%s'...\n", url);  
  88.                                 return false;  
  89.                             }  
  90.                         }  
  91.                     };  
  92.                 }  
  93.                               
  94.                 if(host!=null)  
  95.                 {  
  96.                     Set links = HtmlParserTool.extracLinksWithEncoding(host, visitUrl, downLoader.getCharset(), filter);  
  97.                     // 新的未訪問的URL 入隊  
  98.                     for (String link : links) {  
  99.                         //printf("\t[Crawler] Extrack link=%s...\n",link);  
  100.                         LinkDB.addUnvisitedUrl(link);  
  101.                     }  
  102.                 }  
  103.                 else  
  104.                 {  
  105.                     printf("\t[Crawler] Unknow Host for URL=%s...\n",visitUrl);  
  106.                 }  
  107.             }  
  108.         }  
  109.         return totalSize;  
  110.     }  
  111.   
  112.     public boolean isRecursive() {  
  113.         return isRecursive;  
  114.     }  
  115.   
  116.     public void setRecursive(boolean isRecursive) {  
  117.         this.isRecursive = isRecursive;  
  118.     }  
  119.   
  120.     public boolean isHostonly() {  
  121.         return isHostonly;  
  122.     }  
  123.   
  124.     public void setHostonly(boolean isHostonly) {  
  125.         this.isHostonly = isHostonly;  
  126.     }  
  127.   
  128.     // main 方法入口  
  129.     public static void main(String[] args) {  
  130.         Crawler crawler = new Crawler();  
  131.         crawler.crawling(new String[] { "http://localhost/jforum/posts/list/1422.page" });  
  132.     }  
  133. }  

上面主程式使用了一個 LinkFilter 介面並且實現為一個內部類別. 這個介面的目的是為了過濾分析出來的 URL, 它使得程式分析出來的 URL 只會與原先 URL 同一個 Host.

帶偏好的爬蟲 :
有時候在 URL 佇列中選擇要抓取的 URL 時不一定要按照佇列 "先進先出" 的方式進行出佇列的選擇, 而是把"重要"的 URL 先從佇列中 "挑" 出來進行處理. 這種策略稱為 "頁面選擇" (Page selection), 這可以使有限的資源用來照顧重要性高的網頁. 那麼哪些是重要性高的頁面呢?

判斷頁面的重要性因素有很多, 主要有連結的歡迎程度, 平均連結深度, 網站品質, 歷史權重等主要因素. 連結的歡迎程度主要是由反向連結 (backlinks, 及指向目前 URL 的連結) 的數量和品質決定, 我們定義為 IB(P).

而連結的重要度是由一個關於 URL 字串的函數進行判斷, 例如 ".com" 和 "home" 的 URL 重要度比 ".cc" 和 "map" 高, 我們定義為 IL(P). 而平均連結深度根據上面的寬度優先原則已經包含, 認為距離種子網站越近的重要性越高(ID(P)). 最後如果我們定義網頁重要性為 I(P), 那麼頁面的重要度可以由下面公式決定 :
I(P) = X*IB(P) + Y*IL(P)

其中 X 和 Y 參數用來調整 IB(P) 與 IL(P) 所占比例的大小, ID(P) 則由寬度優先的檢查規則保證, 因此不作為指標函數. 那麼如何實現最佳優化爬蟲呢? 最簡單的方法可以使用 優先順序佇列 來實現 TODO 表, 並且把每個 URL 的重要性作為佇列元素的優先順序. 這樣每次選出來擴充的 URL 就是具有最高重要性的網頁. 至於在 Java 1.5 後, 有提供支援優先順序佇列的資料結構 - java.util.PriorityQueue. 只要將 TODO 的 LinkedList 替換成 PriorityQueue 並且將 URL 實作對應的介面 Comparator 便可實作出帶偏好的爬蟲.

補充說明 :
網路爬蟲(Web Crawler) 扼殺了網站經營者 ?!
爬蟲技術所能創造的商機,當然不僅僅是搜尋引擎而已,像 Google 其實還得再加上搜尋技術才算是真正建立起進入門檻。在 Google 確立了搜尋引擎霸主的地位後,網路爬蟲專家們逐一放棄了將網路上所有的資訊爬下來的野心,轉往利基市場如比價系統(FindPrice)、即時資訊或非web-based的爬蟲 (如 telnet),有的則是站在 Google 巨人的肩膀上,從搜尋結果中再爬出更有價值的資訊,將 search engine 當作是爬蟲中的一個子功能加以利用...
This message was edited 22 times. Last update was at 11/10/2011 17:36:35

4 則留言:

  1. 請教你一下,我不是相關科系的,但是我想學網路爬蟲,我該如何起步?

    回覆刪除
    回覆
    1. 其實是不是相關科系應該沒多大關係, 但跟你的需求比較有關係.
      如果你沒有太多客製化需求, 可以考慮一些套裝工具. Google 爬蟲工具再 Survey 符合自己需求的.
      如果你像我需要做一些客製化的動作, 可以考慮自己寫一個. 爬蟲可以很簡單也可以很複雜, 簡單的可能只爬特定網頁; 複雜的可以像使用分散式來大量處理甚至連網頁上的 link 都會去爬...
      但如果要自己寫, 熟悉語言如 Java, Python etc 可能就不能避免...
      加油 ^^

      刪除
    2. 我之後剛接觸java覺得很困難,而且剛開始有點無趣,要學到把爬蟲寫出來還真要點時間
      你的答覆很詳細,謝謝^^

      刪除
  2. 作者已經移除這則留言。

    回覆刪除

網誌存檔