1目標工作
信息抽取并結構化網頁
網頁銷重
中文分詞
PageRank計算
html語言
用于創(chuàng)建存儲在www服務器上的文件并且能由瀏覽器瀏覽,簡單易用,不需要編譯.
瞄文本(anchor text)
關于鏈接的一段描述,通常以文本或者圖片方式存在.指向文本中的某一位置或者其他網頁.
eg:<a >走進搜索引擎</a>用來描述一個鏈接
半結構化數(shù)據(jù)
html語言的基本特點:標簽方式標識網頁信息
2 信息抽取及網頁信息結構化
對于分析系統(tǒng)來說,基礎工作就是分門別類的從半結構化網頁中提取有價值的能夠代表網頁的屬性.eg:瞄文本,標題,正文等,并將這些屬性結合組成網頁對象.
這種處理稱為"網頁結構化"
2.1 網頁結構化的目標
針對搜索的需要,將HTML網頁數(shù)據(jù)按照基本屬性抽取,而后打包(wrap)出一個網頁對象
1)瞄文本
2)標題(title)<title>網頁制作者編寫
3)正文標題(content title)<titile>網頁編輯者編寫
4)正文(content)<div><table><p>等
5)正向鏈接(link)
一個結構化過程
注:這個過程分為兩個步驟
1)建立html標簽樹
2)通過投票方式識別正文的文本塊,并按深度優(yōu)先遍歷的規(guī)則組織為正文
2.2 建立HTML標簽樹
基于html標簽成對出現(xiàn)的問題,利用棧來進行處理.
2.3 投票方式得到正文.
正文比較復雜,沒有明顯的標簽標記正文;正文可能分割在多個html標簽中.
三類文本塊
1)主題文本塊(topic)
2)目錄性文本塊(hub)
3)圖片型文本塊(pic)
判斷哪個文本塊是正文采用"投票算法"計算方法,類似權重問題.
獲取文本塊之后的工作就是組織文本塊了.采用深度遍歷標簽樹的方式進行處理.
網頁存儲采用結構化方式進行處理.類似文件壓縮.分析過程使用標簽樹(BeautifulSoup...)
3.1?網頁查重
重復情況
1)內容和格式完全相同
2)內容相同,格式不同
3)部分重要內容相同并且格式相同
4)部分重要內容相同但是格式不
基本方案是使用簽名值的方式進行判別
3.2 查重實現(xiàn)方法
I-Match算法:假設 最高頻,最低頻詞不能代表文檔本質.,所以,去掉最高,最低詞頻詞,然后進行簽名處理
Single算法:抽取多個特征詞匯,通過比較兩個特征詞集的相似度來實現(xiàn)文檔查重.
Single算法結論:
對于長度為L的文檔,每隔N個漢字取一個Single這樣一共得到L-N+1個Single,可見N的取值對效率和效果影響很大.N取值2-L.
大規(guī)模文檔查重使維護一個hashtable或者bloom就可以.
Single算法略麻煩:Jaccard系數(shù),用來判斷集合的相似度J = (A&B)/(A|B)
然后定義一個標準相似度值eg:0.2判定為相似.
方案比較
I-Match:需要提取分詞,并計算詞頻,提取特征比較復雜,但是是否相似的計算計較簡單
Single算法:提取特真簡單,但是文檔是否相似計算 復雜.
Single算法性能上表現(xiàn)優(yōu)異,所以廣泛使用
總結:網頁查重三個步驟:
1)特征抽取
2)相似度計算
3)消重
4 中文分詞
1.目前的分詞手段依賴字典和統(tǒng)計學方法
2.通過查字典實現(xiàn)分詞
三種難以區(qū)分類型
1)交集型歧義
"從小學": ?從小/學/電腦 ?從/小學/畢業(yè) ?
2)組合型歧義
"中將" : 美軍/中將/竟然... ? ?新建地鐵中/將/禁止商業(yè)擺攤
3)混合型歧義
"人才能": 人才/能 ? ? 人/才能 ? ? 人/才/能
對于字典方式進行分詞:
字典采用前綴樹或者后綴樹的結構存儲
注:雙圓圈表示一個詞尾
注:對于后綴樹:雙圓圈表示一個詞頭
兩種匹配方式
"最大正向匹配法(MM法)"
"逆向最大匹配法(RMM)"
這類分詞方法稱為貪婪算法:最大匹配最優(yōu)
貪婪算法導致局部最優(yōu)
"N-Gram方法":可以滿足由于錯分詞帶來的損失.
eg:2-Gram.類似Single方式,獲取2步長的所有分詞作為索引.
N-方法雖然有效避免錯誤詞典分詞導致索引不完整,可能導致過多的關鍵詞成為索引項.不經濟
ps:沒有一種方式能夠解決所有的問題.然,字典分詞方式作為主流分詞方法解決大部分分詞問題.但是字典總是滯后于語言的發(fā)展.
所以,如果能夠及時,自動的,準確的發(fā)現(xiàn)新詞,才能最大化字典分詞方案.新詞發(fā)現(xiàn)主要通過統(tǒng)計推斷來實現(xiàn).
基于統(tǒng)計的新詞發(fā)現(xiàn)
5 PageRank(網頁排名)
5.1 基本思想
網頁重要性:
1)認可度越高backlink越多
2)反向連接的源網頁質量越高,所指向的網頁越重要
3)鏈接數(shù)越少的網頁越重要
具體實現(xiàn)依賴數(shù)學高度.參考
PageRank算法簡介及Map-Reduce實現(xiàn)
6 分析系統(tǒng)結構圖
分析系統(tǒng)主要承擔:網頁結構化,網頁消重,文本分詞及pageRank等4項基本任務.
結構圖:
注解:Page庫是通過爬蟲下載到的原始網頁,分析系統(tǒng)通過以下步驟進行網頁分析:
1)結構化過程:建立標簽樹,并提取有價值的樹形,完成從原始網頁打包為網頁對象的過程
2)網頁消重模塊
3)文本分詞將文本切分為以詞匯為單位的集合
4)將分析的結果發(fā)往索引模塊,進行索引入庫
