導航:首頁 > 源碼編譯 > 網頁去重只能通過演算法嗎

網頁去重只能通過演算法嗎

發布時間:2024-05-15 17:33:01

1. 如何計算網站網頁相似度

據統計,網頁上的大部分相同的頁面佔29%,而主體內容完全相同的佔22%,這些重復網頁有的是沒有一點改動的拷貝,有的在內容上稍作修改,比如同一文章的不同版本,一個新一點,一個老一點,有的則僅僅是網頁的格式不同(如 HTML, Postscript),文獻[Models and Algorithms for Duplicate Document Detection 1999年]將內容重復歸結為以下四個類型:
1.如果2篇文檔內容和格式上毫無差別,則這種重復叫做full-layout plicate。
2.如果2篇文檔內容相同,但是格式不同,則叫做full-content plicates
3.如果2篇文檔有部分重要的內容相同,並且格式相同,則稱為partial-layout plicates
4.如果2篇文檔有部分重要的內容相同,但是格式不同,則稱為partial-content plicates
網頁去重的任務就是去掉網頁中主題內容重復的部分。它和網頁凈化(noise rection),反作弊(antispam) 是搜索引擎的3大門神
去重在我看來起碼有四好處:減少存儲;增強檢索效率;增強用戶的體驗;死鏈的另一種解決方案。
目前從網路的搜索結果來看,去重工作做的不是很完善,一方面可能是技術難度(precision和recall都超過90%還是很難的);另一方面可能是重復的界定,比如轉載算不算重復?所以另一項附屬的工作是對個人可寫的頁面(PWP)進行特殊的處理,那麼隨之而來的工作就是識別PWP頁面。^_^這里就不扯遠呢。
問題如何解決?
網頁的deplication,我們的演算法應該是從最簡單的開始,最樸素的演算法當然是
對文檔進行兩兩比較,如果A和B比較,如果相似就去掉其中一個
然而這個樸素的演算法,存在幾個沒有解決的問題:
0.要解決問題是什麼?full-layout?full-content?partial-layout還是partial-content?
1. 怎麼度量A 和 B的相似程度
2. 去掉A還是去掉B,如果A ~B(~表相似,!~表示不相似),B~C 但是 A!~C,去掉B的話,C就去不掉。另一個更深入的問題是,演算法的復雜度是多少?假設文檔數為n,文檔平均長度為m,如果相似度計算復雜度為m的某一個復雜度函數:T=T(m),文檔兩兩比較的復雜度是O(n^2),合起來是O(n^2 * T(m)) . 這個復雜度是相當高的,想搜索引擎這樣處理海量數據的系統,這樣的復雜度是完全不能接受的,所有,另外三個問題是:
3. 如何降低相似度計算的復雜化度
4. 如何減少文檔比較的復雜度
5. 超大數據集該如何處理
第0個問題是,我們要解決的關鍵,不同的問題有不同的解決方法,從網頁的角度來看,結構的重復並不能代表是重復,比如產品展示頁面,不同的產品展示頁面就有相同的文檔結構。內容來看,復制網站會拷貝其他網站的主要內容,然後加些廣告或做些修改。所以,解決的問題是,partial-content deplication,那麼首先要抽取網頁的主體內容。演算法變成:
抽取文檔主體內容,兩兩比較內容的相似性,如果A和B相似,去掉其中一個
其次,問題2依賴於問題1的相似度度量,如果度量函數具有傳遞性,那麼問題2就不存在了,如果沒有傳遞性,我們的方法是什麼呢?哦,那就找一個關系,把相似關系傳遞開嘛,簡單,聚類嘛,我們的框架可以改成:
抽取文檔主體內容,兩兩比較內容的相似性,如果A和B相似,把他們聚類在一起,最後一個類里保留一個page
最後,歸納為幾個步驟
第一步:識別頁面的主題內容,網頁凈化的一部分,以後討論
第二步:計算相似度
第三步:聚類演算法,計算出文檔那些文檔是相似的,歸類。
核心的問題是,「如何計算相似度?」這里很容易想到的是
1. 計算內容的編輯距離edit distance(方法很有名,但是復雜度太高)
2. 把內容分成一個個的token,然後用集合的jaccard度量(好主意,但是頁面內容太多,能不能減少啊?)
好吧,但是,當然可以減少集合的個數呢,采樣,抽取滿足性質的token就可以啦,如滿足 mod m =0 的token,比如有實詞?比如stopwords。真是絕妙的注意.在把所有的idea放一起前,突然靈光一現,啊哈,
3. 計算內容的信息指紋,參考google研究員吳軍的數學之美系列。
把他們放在一起:
第一步:識別頁面的主題內容,網頁凈化的一部分,以後討論
第二步:提取頁面的特徵。將文章切分為重合和或不重合的幾個結合,hash out
第三步:用相似度度量來計算集合的相似性,包括用信息指紋,Jaccard集合相似度量,random projection等。
第四步:聚類演算法,計算出文檔那些文檔是相似的,歸類。
方法分類:
按照利用的信息,現有方法可以分為以下三類
1.只是利用內容計算相似
2.結合內容和鏈接關系計算相似
3.結合內容,鏈接關系以及url文字進行相似計算
一般為內容重復的去重,實際上有些網頁是
按照特徵提取的粒度現有方法可以分為以下三類
1.按照單詞這個級別的粒度進行特徵提取.
2.按照SHINGLE這個級別的粒度進行特徵提取.SHNGLE是若干個連續出現的單詞,級別處於文檔和單詞之間,比文檔粒度小,比單詞粒度大.
3.按照整個文檔這個級別的粒度進行特徵提取
演算法-具體見真知
1. I-Match
2. Shingling
3. Locality Sensitive Hashing.(SimHash)
4. SpotSigs
5. Combined

2. python爬取的數據如何去重說一下具體的演算法依據

要具體問題具體分析的。看你要抓取什麼數據。
最好能找到一個能夠作為重復性區分的欄位值。比如網路知道的所有提問,每個問題都有一個對應的id,樓主這個問題對應的id就是181730605611341844。那在爬取的過程中,可以將所有已經爬取的問題id保存在一個set()中,如果即將爬取的問題id已經存在了,那就跳過,反之則繼續。
不知道樓主用的是什麼資料庫,在資料庫設計中,也可以添加一些約束條件作為約束,保證數據的唯一性。

閱讀全文

與網頁去重只能通過演算法嗎相關的資料

熱點內容
二十八宿的演算法 瀏覽:517
論客的伺服器怎麼設置 瀏覽:571
java中主方法 瀏覽:527
armlinux交叉編譯器 瀏覽:734
ios編程難嗎 瀏覽:660
為什麼叫A演算法 瀏覽:209
安卓手機10塊錢可以買什麼手機 瀏覽:275
怎樣對某一列部分數據加密 瀏覽:364
typecho伺服器怎麼登錄 瀏覽:301
龍雀服源碼 瀏覽:337
網球小恐龍解壓玩具 瀏覽:442
開關電源還是單片機有 瀏覽:201
金得利文件夾是哪產的 瀏覽:924
電腦棕色文件夾打不開 瀏覽:657
微信如何使用網路代理伺服器 瀏覽:327
無線網橋加密技術 瀏覽:286
pdf格式轉化ppt 瀏覽:934
程序設計流程圖表達演算法 瀏覽:539
plc程序員待遇怎麼樣 瀏覽:596
一加主題文件夾商店 瀏覽:494