254
網絡爬蟲之網頁排重：語義指紋
引言：網絡爬蟲讓我們高效地從網頁獲取到信息，但網頁的重複率很高，網頁需要按內容做文檔排重，而判斷文檔的內容重複有很多種方法，語義指紋是其中比較高效的方法。
本文選自《網絡爬蟲全解析——技術、原理與實踐》。
現代社會，有效信息對人來說就像氧氣一樣不可或缺。互聯網讓有效信息的收集工作變得更容易。當你在網上衝浪時，網絡爬蟲也在網絡中穿梭，自動收集互聯網上有用的信息。
自動收集和篩選信息的網絡爬蟲讓有效信息的流動性增強，讓我們更加高效地獲取信息。隨著越來越多的信息顯現於網絡，網絡爬蟲也越來越有用。
不同的網站間轉載內容的情況很常見。即使在同一個網站，有時候不同的URL地址可能對應同一個頁麵，或者存在同樣的內容以多種方式顯示出來，所以，網頁需要按內容做文檔排重。
例如，一個企業商品搜索。搜商品名，有一家公司發的商品名字都一樣，結果這家公司發的商品都顯示在前麵，但是要求一家企業隻顯示一條相似的商品在前麵，可以把近似重複的文檔權重降低，隻保留一個文檔不降低權重。
判斷文檔的內容重複有很多種方法，語義指紋的方法比較高效。語義指紋是直接提取一個文檔的二進製數組表示的語義，通過比較相等來判斷網頁是否重複。語義指紋是一個很大的數組，全部存放在內存會導致內存溢出，普通的數據庫效率太低，所以采用內存數據庫Berkeley DB。可以通過Berkeley DB判斷該語義指紋是否已經存在。另外一種方法是通過布隆過濾器來判斷語義指紋是否重複。
提取網頁語義指紋的方法是：從淨化後的網頁中，選取最有代表性的一組關鍵詞，並使用該關鍵詞組生成一個語義指紋。通過比較兩個網頁的語義指紋是否相同來判斷兩個網頁是否相似。
網絡上一度出現過很多篇關於“羅玉鳳征婚”的新聞報道，其中的兩篇新聞內容對比如下表。
對於這兩篇內容相同的新聞，有可能提取出同樣的關鍵詞：“羅玉鳳”“征婚”“北大”“清華”“碩士”，這就表示這兩篇文檔的語義指紋也相同。
為了提高語義指紋的準確性，需要考慮到同義詞，例如，“北京華聯”和“華聯商廈”可以看成相同意義的詞。最簡單的判斷方法是做同義詞替換。把“開業之初，比這還要多的質疑的聲音環繞在北京華聯決策者的周圍”替換為“開業之初，比這還要多的質疑的聲音環繞在華聯商廈決策者的周圍”。
設計同義詞詞典的格式是：每行一個義項，前麵是基本詞，後麵是一個或多個被替換的同義詞，請看下麵的例子。
華聯商廈 北京華聯 華聯超市
這樣可以把“北京華聯”或“華聯超市”替換成“華聯商廈”。對指定文本，要從前往後查找同義詞詞庫中每個要替換的詞，然後實施替換。同義詞替換的實現代碼分為兩步。首先是查找Trie樹結構的詞典過程。
public void checkPrefix(String sentence,int offset,PrefixRet ret) {
if (sentence == null || root == null || "".equals(sentence)) {
ret.value = Prefix.MisMatch;
ret.data = null;
ret.next = offset;
return ;
}
ret.value = Prefix.MisMatch;//初始返回值設為沒匹配上任何要替換的詞
TSTNode currentNode = root;
int charIndex = offset;
while (true) {
if (currentNode == null) {
return;
}
int charComp = sentence.charAt(charIndex) - currentNode.splitchar; if (charComp == 0) {
charIndex++;
if(currentNode.data != null){
ret.data = currentNode.data;//候選最長匹配詞
ret.value = Prefix.Match;
ret.next = charIndex;
}
if (charIndex == sentence.length()) {
return; //已經匹配完
}
currentNode = currentNode.eqKID;
} else if (charComp < 0) {
currentNode = currentNode.loKID;
} else {
currentNode = currentNode.hiKID;
}
}
}
然後是同義詞替換過程。
//輸入待替換的文本，返回替換後的文本
public static String replace(String content) throws Exception{
int len = content.length();
StringBuilder ret = new StringBuilder(len);
SynonymDic.PrefixRet matchRet = new SynonymDic.PrefixRet(null,null);
for(int i=0;i<len;){
//檢查是否存在從當前位置開始的同義詞
synonymDic.checkPrefix(content,i,matchRet);
if(matchRet.value == SynonymDic.Prefix.Match) //如果匹配上，則替換同義詞
{
ret.append(matchRet.data);//把替換詞輸出到結果
i=matchRet.next;//下一個匹配位置
}
else //如果沒有匹配上，則從下一個字符開始匹配
{
ret.append(content.charAt(i));
++i;
}
} return ret.toString();
}
語義指紋生成算法如下所示。
第1步：將每個網頁分詞表示成基於詞的特征項，使用TF*IDF作為每個特征項的權值。地名、專有名詞等，名詞性的詞匯往往有更高的語義權重。
第2步：將特征項按照詞權值排序。
第3步：選取前n個特征項，然後重新按照字符排序。如果不排序，關鍵詞就找不到對應關係。
第4步：調用MD5算法，將每個特征項串轉化為一個128位的串，作為該網頁的指紋。
調用fseg.result.FingerPrint中的方法。
String fingerPrint = getFingerPrint("","昨日，省城淵明北路一名17歲的少年在6樓晾毛巾時失足墜樓，摔在樓下的一輛麵包車上。麵包車受衝擊變形時吸收了巨大的反作用力能量，從而“救”了少年一命。目前，傷者尚無生命危險。據一位目擊者介紹，事故發生在下午2時40分許，當時這名在某美發店工作的少年正站在陽台上晾毛巾，因雨天陽台濕滑而不小心摔下。 記者來到搶救傷者的醫院了解到，這名少年名叫李嘉誠，今年17歲，係豐城市人。李嘉誠受傷後，他表姐已趕到醫院陪護。據醫生介紹，傷者主要傷在頭部，具體傷情還有待進一步檢查。");
String md5Value = showBytes(getMD5(fingerPrint));
System.out.println("FingerPrint:"+fingerPrint+" md5:"+md5Value);
MD5可以將字符串轉化成幾乎無衝突的hash值，但是MD5速度比較慢，MurmurHash或者JenkinsHash也可以生成衝突很少的hash值，在Lucene的企業搜索軟件Solr1.4版本中提供了JenkinsHash實現的語義指紋，叫作Lookup3Signature。調用MurmurHash生成64位的Hash值的代碼如下所示。
public static long stringHash64(String str, int initial) {
byte[] bytes = str.getBytes();
return MurmurHash.hash64(bytes, initial);
}
本文選自《網絡爬蟲全解析——技術、原理與實踐》，點此鏈接可在博文視點官網查看此書。
想及時獲得更多精彩文章，可在微信中搜索“博文視點”或者掃描下方二維碼並關注。
此外，本周正在進行一項熱門活動——
《盡在雙11》的作者樂田、仁重正通過開源問答來答複讀者有關《盡在雙11》這本書的疑問~
更多好問題，期待你來問！
最後更新：2017-05-05 11:31:40