1、習題課習題課Proj1+hw3LiYingDec 2, 2009heritrix系統使用系統使用n要求：配置、安裝Heritrix，抓取指定的網站: http:/n限制抓取范圍：修改Modules、 Submodules 和Settings ：nSelect Crawl Scope選擇DecidingScope；n用正則表達式完成對抓取的網頁的url的匹配；n限定只抓取文本類型的內容，n縮短爬取時間：nProfiles中setting修改 ”max-delay-ms”、”min-delay-ms”、”max-retries”、”retry-delay-seconds”的數值，提高抓取效率n設置

2、-Xmx運行參數增加JVM內存（256M-1024M）heritrix系統使用系統使用n只有一個線程在工作： n原因：Heritrix的url隊列以hostname為key，所有相同key的url放置在同一個隊列里面，也就是說同一個host下面的所有url都放在一個隊列里面，當線程獲取url時候，會將該隊列放置到同步池中，拒絕其他線程訪問。n思路：將url平均分配到Queue里面，實現更好的多線程同步，n實現方法：采用ELF hash算法平均分配url。heritrix系統代碼分析系統代碼分析要求:按Week2的web crawler系統結構,尋找Heritrix系統里面的crawler的下面

3、四個部分: npage fetchingnisPageKnownnisUrlVisitednPoliteness分析它們的主要數據結構和算法.寫一個簡短的報告文檔.Page fetchingn從Frontier獲取到一個URI之后，處理鏈對URI進行處理，包括Prefetch,Fetch,Extract,Write,PostPrecess。其中Fetch主要是完成從web中獲取網頁。Heritrix提供了3種Fetch方法：FetchHTTP,FetchFTP,FetchDNS。FetchDNS 的功能主要是為當前URI 解析域名，FetchHTTP 和FetchFTP 的功能是來抓取數據。n

4、數據結構：nCrawlURI 存儲一個URI的相關信息nHttpRecorder存儲一次http交互過程的獲取到的頁面信息或文件信息。HttpRecorder 作為一個ToeThread 參數將貫穿整個Processor ChainPage fetchingn算法：以FetchHTTP為例n判斷能否抓取網頁n預處理過程。將在抓取過程中獲得的網頁信息寫到HttpRecordern根據URI創建HttpMethod，區分為POST和GETn經過抓取網頁得到的抓取內容，從中提取內容并根據選定算法計算摘要值，一般是SHA1和MD5算法，默認為SHA1。isPageKnownnHeritrix提供了三種

5、網頁去重的策略n策略一：n先抓取一次網頁，把URI和網頁的摘要值保存到Hash表中。在第二次抓取相同URI的網頁的時候，根據URI索引并比較與之前存在Hash表中的摘要值是不是相同。n策略二：n是先抓取一次網頁，把URI和網頁的摘要值保存到Hash表中。在第二次抓取相同URI的網頁的時候，根據HTTP請求返回的content-length來比較第一次記錄的content-length是否有變化，如果有變化則抓取并存儲網頁，如果沒有變化則放棄該網頁。策略三策略三在一個抓取過程中，把當前網頁的摘要值放到Hash表里作為KEY值，如果當前網頁鏈接到了一個相同摘要值的網頁（KEY值相同）并且URI不同

6、，就不再抓取和存儲這個網頁。n數據結構： ncurrentDigest:當前uri的摘要nA_VIA_DIGEST:前一個uri的屬性n算法：norg.archive.crawl.extractor.TrapSuppressExtractor通過注意一個網頁的內容摘要是否與它的A_VIA_DIGEST內容摘要相等來判斷。isUrlVisitedn作用：在將鏈接加入隊列之前需要查看鏈接是否已經被處理過了。nHeritrix中isUrlVisited 的實現有如下需求：n支持多線程讀寫，大容量。nBerkeleyDB：n實質是一個按照”key/value”方式保存數據的HashTable。它支持兩

7、段鎖技術和先寫日志策略來保證數據的正確性和一致性，遠比簡單的HashTable 的Synchronize 強大。n數據庫和應用程序在相同的地址空間中運行，所以不需要和應用程序進行進程間通信，節省了大量的開銷，不會在isUrlVisited的階段形成性能瓶頸。nHeritrix 的BdbFrontier 采用了Berkeley DB 來解決問題，具體做法是將isUrlVisited 部分實現為BdbUriUniqueFilter 類。isUrlVisitedn數據結構：BdbUriUniqFilternalreadySeen數據庫： (key,value)組合， heritrix采用了將url的

8、主機名和整個url分別計算fingerprint，以免破壞url的局部性。n算法：n當使用BdbFrontier的時候，默認使用BdbUriUniqFilter作為alreadyIncluded存儲url信息，可選的存儲方式還有BloomUriUniqFilter等nHeritrix調用frontier的schedule方法將任何一個url添加到alreadyIncluded中。當url添加進alreadySeen的時候，判斷數據庫中是否已經有相應的key存在Politeness線程資源的約束線程資源的約束n通過對politeness 設置閾值，Heritrix 可以使用以實現抓取對被訪問服務

9、器造成的壓力的控制。ndelay-factor 再次訪問服務器應當間隔上次訪問服務器時間的倍數nmin-delay-ms 兩次訪問同一個服務器最小的時間間隔nmax-delay-ms 等待服務器響應的最大時間nrespect-crawl-delay-up-to-secs 當讀取robot.txt 時推遲抓取的時間nretry-delay-seconds 兩次嘗試抓取頁面的時間間隔nmax-retries 鏈接嘗試最大數n上述有關politeness 參數的使用集中在AbstractFrontier 中，用以判斷抓取現狀，從而采取相應的動作。Politenessrobots.txtnrobots

10、.txt 聲明了網站不想被robot 訪問的部分。根據抓取得到的robot.txt進行文檔解析，然后把文檔中的內容解析并且傳入的crawler的設定當中，把允許和不允許的內容和對應的agent進行比較，并且最后得到本身agent所限定或者不限定的內容。n數據結構：nRobotstxt：n從robots.txt中解析出user agent、robots指示(即disallow，crawl-delay，allow)并用list和一個對應的map結構存儲nRobotsHonoringPolicy:crawler對robots尊重的5個程度nClassic：完全尊重robot.txt的限定nIgnor

11、e：直接跳過robot.txt的限制進行抓取ncustom：用戶來定于限制的情況nmost-favored：每一個爬蟲有多個user-agent，當全部agent都得到權限時才抓取nmost-favored-set：對于多個user-agent,有一個能夠抓取就允許crawler去抓取。Politenessrobots.txt（2）nRobotsDirectives： n為每個user-agent需要維護一個允許和不允許訪問的數據結構，disallows & allows記錄robot.txt中對應的指令 nRobotsExclusionPolicy：n將這些抓取內容的禁止范圍的進一步

12、設定到每一個user-agent中，在RobotsHonoringPolicy的基礎上，實現最終的policy，提供一些接口函數n由于并不是每個網站都會存放robots.txt 這樣的文件，在這種情況下Heritrix 會花上大量時間試圖去訪問這樣一個文件，大大降低了抓取效率。因此，為了提高抓取效率，可以考慮將對robots.txt 的訪問部分去除。搜集搜集web數據的數據的graph link analysisn要求：回答以下問題，并給出方法的說明這個網站有多少網頁？入度、出度分布情況如何？top 10的最重要頁面是哪些？n方法：Pagerank方法（關于PR值收斂的判斷）n網頁數量：176

13、00左右n入度、出度以及top10頁面情況：基本滿足power law分布的特點。 獲得鏈接之間的鏈出關系的方法獲得鏈接之間的鏈出關系的方法n方法一：分析crawl.log：通過觀察crawl.log，可以看到url與url之間的關系。n從原始的log 文件取出鏈接的目的地址和源地址n從相對的鏈接地址得到絕對地址n轉換utf-8 編碼n當連接可能存在多個來源，即多個頁面中都存在該鏈接時，crawler.log不能提供足夠的信息來提供鏈接之間的關系。獲得鏈接之間的鏈出關系的方法獲得鏈接之間的鏈出關系的方法n方法二：分析抓取得到的網頁，從網頁中找到鏈接關系。n一種是以網站鏡像的方式存儲，抓取的頁面

14、存儲在jobs/mirror文件夾下，可以對抓取到的頁面源碼直接進行分析，解析出每一個頁面的鏈出關系。n將文件名映射為鏈接地址。n一種是以arc文件的方式存儲。由于arc文件中包含頁面內容，可以從arc文件中提取出頁面內容，再在頁面內容中把它包含的鏈接提取出來。n從頁面中提取鏈接不易實現n讀取arc文件不易實現，雖然heritrix提供了arcreader方法，但是該方法只能讀出arc文件中每個網頁的元數據。獲得鏈接之間的鏈出關系的方法獲得鏈接之間的鏈出關系的方法n方法三：修改Heritrix源碼，在抓取過程中存儲鏈接關系nExtractorHTML是在HTML頁面中抽取鏈接，在抽取鏈接之后添

15、加代碼，從而將當前頁面以及當前頁面包含的鏈接以一定格式輸出到文件。n利用heritrix抽出鏈接關系n能夠控制鏈接關系的輸出格式，從而減少后期處理工作。文件預處理的實現文件預處理的實現n在出鏈中去掉不在站點內部的鏈接。在對沒有處理的文件分析時發現很多錯誤網頁都連接到：http:/ n網站架構、內容的單一使得CCER在某些方面不符合web的一般特性，而且CCER站點與web的規模有很大差距。n鄰接表 & 鄰接矩陣nBoolean的鄰接矩陣與HW-week3-11 PPT23頁的例子，矩陣C經過SVD和降維近似映射到了2維平面。請把這個過程做一遍(按PPT上的說明，使用MATLAB很方便，

16、畫圖也很方便)。把5個詞映射到LSI空間中，把它們的向量畫出來。把查詢query=(boat voyage)映射到LSI空間中去，把它的向量畫出來。查詢結果是什么？最后請嘗試說明一下LSI空間的這兩個維度dim1,dim2大概的含義。答案要點：n把矩陣變換的過程寫出來，并且畫出圖來HW-week3-1(2)n通過將五個Term映射到LSI空間的公式可以求出這五個詞在LSI空間中的映射。n查詢query=(boat voyage)對應的矩陣為 0，1，0，1，0通過將Query映射到LSI空間的公式 可以求出這Query在LSI空間中的映射。1kkTkUqq1kktVtHW-week3-1(3)

17、n查詢結果根據向量之間的點乘來計算，點乘值越大則兩個向量代表的文檔越相關：d1和d5應該排在前面ndim1和dim2 是比term層次更高的兩個特征，可能包含了詞的同義、近義等綜合因素。如果Query映射的向量與某一個dim很相關（靠得很近），則表示Query與該維度聚集的那些term相關度高2 Bob(上次那個上次那個Bob)跑來感謝你，上一次建跑來感謝你，上一次建ccer網頁庫的網頁庫的inverted index，查詢效果很好。談話間，查詢效果很好。談話間，Bob問：聽說問：聽說現在現在Language Model很很popular，你建的，你建的inverted index可以用來支持可以用來支持LM嗎？你覺得呢？嗎？你覺得呢？答案要點：n可以用來支持LM。但只能支持Unigram Language Model，因為無法計算term之間的條件概率。n可以給出語言模型的公式，對于公式中的參數，說明如何得到，或者如何計算。P(w|d) = Pmle(w|Md) + (1 )