從“語(yǔ)義指紋算法”到“網(wǎng)頁(yè)去重算法”，最終在csdn blog上找到部分我想要的資料了。不能直接轉(zhuǎn)載，只好實(shí)施起“人工+智能”。
?
================================================================================================
以下內(nèi)容來(lái)自csdn的"機(jī)器學(xué)習(xí)和我關(guān)注的技術(shù)"
================================================================================================
網(wǎng)頁(yè)去重-比較文本的相似度-Near duplication detection http://blog.csdn.net/beta2/article/details/4974221
Near duplicate detection 的任務(wù)是檢測(cè)重復(fù)的內(nèi)容，這項(xiàng)工作在搜索引擎，版權(quán)保護(hù)，信息展示等方面都有很好的應(yīng)用。在搜索引擎上，主要是去掉重復(fù)的頁(yè)面，圖片，文件，文檔等等。下面就指討論網(wǎng)頁(yè)的deduplication。
?
問(wèn)題是什么？
? ? 據(jù)統(tǒng)計(jì)，網(wǎng)頁(yè)上的大部分相同的頁(yè)面占29%，而主體內(nèi)容完全相同的占22%，這些重復(fù)網(wǎng)頁(yè)有的是沒(méi)有一點(diǎn)改動(dòng)的拷貝，有的在內(nèi)容上稍作修改，比如同一文章的不同版本，一個(gè)新一點(diǎn)，一個(gè)老一點(diǎn)，有的則僅僅是網(wǎng)頁(yè)的格式不同（如 HTML, Postscript）,文獻(xiàn)[Models and Algorithms for Duplicate Document Detection 1999年]將內(nèi)容重復(fù)歸結(jié)為以下四個(gè)類型:
1.如果2篇文檔內(nèi)容和格式上毫無(wú)差別，則這種重復(fù)叫做full-layout duplicate。
2.如果2篇文檔內(nèi)容相同，但是格式不同，則叫做full-content duplicates
3.如果2篇文檔有部分重要的內(nèi)容相同，并且格式相同，則稱為partial-layout duplicates
4.如果2篇文檔有部分重要的內(nèi)容相同，但是格式不同，則稱為partial-content duplicates
?
網(wǎng)頁(yè)去重的任務(wù)就是去掉網(wǎng)頁(yè)中主題內(nèi)容重復(fù)的部分。它和網(wǎng)頁(yè)凈化（noise reduction），反作弊（antispam) 是搜索引擎的3大門神
?
去重在我看來(lái)起碼有四好處：減少存儲(chǔ)；增強(qiáng)檢索效率；增強(qiáng)用戶的體驗(yàn)；死鏈的另一種解決方案。
?
目前從百度的搜索結(jié)果來(lái)看，去重工作做的不是很完善，一方面可能是技術(shù)難度（precision和recall都超過(guò)90%還是很難的）；另一方面可能是重復(fù)的界定，比如轉(zhuǎn)載算不算重復(fù)？所以另一項(xiàng)附屬的工作是對(duì)個(gè)人可寫的頁(yè)面(PWP)進(jìn)行特殊的處理,那么隨之而來(lái)的工作就是識(shí)別PWP頁(yè)面。^_^這里就不扯遠(yuǎn)呢。
?
問(wèn)題如何解決？
網(wǎng)頁(yè)的deduplication，我們的算法應(yīng)該是從最簡(jiǎn)單的開始，最樸素的算法當(dāng)然是
?
? ? ? ? 對(duì)文檔進(jìn)行兩兩比較，如果A和B比較，如果相似就去掉其中一個(gè)
?
然而這個(gè)樸素的算法，存在幾個(gè)沒(méi)有解決的問(wèn)題：
? ? ?0.要解決問(wèn)題是什么？full-layout？full-content？partial-layout還是partial-content？
? ? ?1. 怎么度量A 和 B的相似程度
? ? ?2. 去掉A還是去掉B，如果A ～B（～表相似,!~表示不相似），B～C 但是 A!~C，去掉B的話，C就去不掉。
?
另一個(gè)更深入的問(wèn)題是，算法的復(fù)雜度是多少?假設(shè)文檔數(shù)為n，文檔平均長(zhǎng)度為m，如果相似度計(jì)算復(fù)雜度為m的某一個(gè)復(fù)雜度函數(shù)：T=T（m），文檔兩兩比較的復(fù)雜度是O（n^2)，合起來(lái)是O（n^2 * T(m)) . 這個(gè)復(fù)雜度是相當(dāng)高的，想搜索引擎這樣處理海量數(shù)據(jù)的系統(tǒng)，這樣的復(fù)雜度是完全不能接受的，所有，另外三個(gè)問(wèn)題是：
?
? ? ? 3. 如何降低相似度計(jì)算的復(fù)雜化度
? ? ? 4. 如何減少文檔比較的復(fù)雜度
? ? ? 5. 超大數(shù)據(jù)集該如何處理
第0個(gè)問(wèn)題是，我們要解決的關(guān)鍵，不同的問(wèn)題有不同的解決方法，從網(wǎng)頁(yè)的角度來(lái)看，結(jié)構(gòu)的重復(fù)并不能代表是重復(fù)，比如產(chǎn)品展示頁(yè)面，不同的產(chǎn)品展示頁(yè)面就有相同的文檔結(jié)構(gòu)。內(nèi)容來(lái)看，復(fù)制網(wǎng)站會(huì)拷貝其他網(wǎng)站的主要內(nèi)容，然后加些廣告或做些修改。所以，解決的問(wèn)題是，partial-content deduplication，那么首先要抽取網(wǎng)頁(yè)的主體內(nèi)容。算法變成：
?
? ? ?抽取文檔主體內(nèi)容，兩兩比較內(nèi)容的相似性，如果A和B相似，去掉其中一個(gè)
其次，問(wèn)題2依賴于問(wèn)題1的相似度度量，如果度量函數(shù)具有傳遞性，那么問(wèn)題2就不存在了，如果沒(méi)有傳遞性，我們的方法是什么呢？哦，那就找一個(gè)關(guān)系，把相似關(guān)系傳遞開嘛，簡(jiǎn)單，聚類嘛，我們的框架可以改成：
?
? ? ?抽取文檔主體內(nèi)容，兩兩比較內(nèi)容的相似性，如果A和B相似，把他們聚類在一起，最后一個(gè)類里保留一個(gè)page
最后，歸納為幾個(gè)步驟
第一步：識(shí)別頁(yè)面的主題內(nèi)容，網(wǎng)頁(yè)凈化的一部分，以后討論
第二步：計(jì)算相似度
第三步：聚類算法，計(jì)算出文檔那些文檔是相似的，歸類。
?
核心的問(wèn)題是，“如何計(jì)算相似度？”這里很容易想到的是
? ?1. 計(jì)算內(nèi)容的編輯距離edit distance（方法很有名，但是復(fù)雜度太高）
? ?2. 把內(nèi)容分成一個(gè)個(gè)的token，然后用集合的jaccard度量（好主意，但是頁(yè)面內(nèi)容太多，能不能減少啊？）
?
好吧，但是，當(dāng)然可以減少集合的個(gè)數(shù)呢，采樣，抽取滿足性質(zhì)的token就可以啦，如滿足 mod m =0 的token，比如有實(shí)詞？比如stopwords。真是絕妙的注意.在把所有的idea放一起前，突然靈光一現(xiàn)，啊哈，
? ?3. 計(jì)算內(nèi)容的信息指紋，參考google研究員吳軍的數(shù)學(xué)之美系列http://www.googlechinablog.com/2006/08/blog-post.html
?
把他們放在一起：?
? ? ?
第一步：識(shí)別頁(yè)面的主題內(nèi)容，網(wǎng)頁(yè)凈化的一部分，以后討論
第二步：提取頁(yè)面的特征。將文章切分為重合和或不重合的幾個(gè)結(jié)合，hash out
第三步：用相似度度量來(lái)計(jì)算集合的相似性，包括用信息指紋，Jaccard集合相似度量，random projection等。
第四步：聚類算法，計(jì)算出文檔那些文檔是相似的，歸類。
?
方法分類：
?
按照利用的信息，現(xiàn)有方法可以分為以下三類
1．只是利用內(nèi)容計(jì)算相似
2．結(jié)合內(nèi)容和鏈接關(guān)系計(jì)算相似
3．結(jié)合內(nèi)容，鏈接關(guān)系以及url文字進(jìn)行相似計(jì)算
?
一般為內(nèi)容重復(fù)的去重，實(shí)際上有些網(wǎng)頁(yè)是
按照特征提取的粒度現(xiàn)有方法可以分為以下三類
?
1.按照單詞這個(gè)級(jí)別的粒度進(jìn)行特征提取.
2.按照SHINGLE這個(gè)級(jí)別的粒度進(jìn)行特征提取.SHNGLE是若干個(gè)連續(xù)出現(xiàn)的單詞,級(jí)別處于文檔和單詞之間,比文檔粒度小,比單詞粒度大.
3.按照整個(gè)文檔這個(gè)級(jí)別的粒度進(jìn)行特征提取
?
算法-具體見(jiàn)真知
1. I-Match
2. Shingling
3. Locality Sensitive Hashing.(SimHash)
4. SpotSigs
5. Combined
?
網(wǎng)頁(yè)去重-算法篇 http://blog.csdn.net/beta2/article/details/5014530
前一篇提到了5個(gè)解決網(wǎng)頁(yè)去重的算法，這里我想討論下這些算法
1. I-Match
2. Shingliing
3. SimHashing（ locality sensitive hash）
4. Random Projection
5. SpotSig
6. combined
I-Match算法
I-Match算法有一個(gè)基本的假設(shè)說(shuō)：不經(jīng)常出現(xiàn)的詞和經(jīng)常出現(xiàn)的詞不會(huì)影響文檔的語(yǔ)義，所以這些詞是可以去掉的。
算法的基本思想是：將文檔中有語(yǔ)義的單詞用hash的辦法表示成一個(gè)數(shù)字，數(shù)字的相似性既能表達(dá)文檔的相似性
算法的框架是：
1. 獲取文檔（或者是主體內(nèi)容）
2. 將文檔分解成token流，移除格式化的標(biāo)簽
3. 使用term的閾值（idf），保留有意義的tokens
4. 插入tokens到升序排列的排序樹中
5. 計(jì)算tokens的SHA1
6. 將元組（doc_id,SHA hash) 插入到某一詞典中，如果詞典有沖突，這兩個(gè)文檔相似。
算法有一個(gè)缺點(diǎn)是穩(wěn)定性差。如果文檔的某個(gè)詞改變了，最終的hash值就會(huì)發(fā)生顯著的變化。對(duì)空文檔，算法是無(wú)效的。
有一個(gè)解決辦法是，用隨機(jī)化的方法，參考Lexicon randomization for near-duplicate detection with I-Match。具體細(xì)節(jié)這里就不提了
Shingling算法
Shingling算法說(shuō)，I-Match以詞為單位做hash顯然是不準(zhǔn)確的，因?yàn)樗雎粤宋臋n之間的順序。另，Shingle指的是連續(xù)的若干個(gè)單詞的串。
Shingling算法有個(gè)簡(jiǎn)單的數(shù)學(xué)背景。如果一個(gè)shingle的長(zhǎng)度為k，那么長(zhǎng)度為n的文檔就有n-k+1個(gè)shingle，每一個(gè)shingle可以用MD5或者其他算法表示成一個(gè)fingerprint，而兩個(gè)文檔的相似性Jacard相似性來(lái)表示，Jarcard公式是指兩個(gè)集合的相似性=集合之交/集合之并。為了估計(jì)兩個(gè)文檔的相似性，有時(shí)候n-k+1個(gè)fingerprint還是太大了，所以取m個(gè)fingerprint函數(shù)，對(duì)每一個(gè)函數(shù)fi，都可以計(jì)算出n-k+1個(gè)fingerprint，取其中的最小的fingerprint，稱為i-minvalue. 那么一個(gè)文檔就有m個(gè)i-minvalue。數(shù)學(xué)上，Broder大師說(shuō)：
? ? ? ? 平均來(lái)講，兩個(gè)文檔中相同的唯一single的比率和兩個(gè)文檔中相同的i-minvalue的比率是一樣的
Shingling的算法框架是：
1. 獲取文檔（或者是主體內(nèi)容）
2. 將文檔分解成n-k+1個(gè)shingle，取m個(gè)fingerprint函數(shù)，對(duì)每一個(gè)fingerpint函數(shù)計(jì)算i-minvalue值
3. 將m個(gè)i-minvalue值組合成更少m’個(gè)surpersingle
4.計(jì)算兩個(gè)文檔相同的surpergingle的個(gè)數(shù)a。
5. 如果a大于某一個(gè)值b（say：2），那么兩個(gè)文檔Jarcard 相似
一般的參數(shù)設(shè)置為：m=84，m’=6，b=2
SimHash 算法
locality sensitive hash算法博大精深。基本思想是，如果兩個(gè)東西相似，我可以用一個(gè)hash函數(shù)把他們投影到相近的空間中LSH。用到near duplication detection上，算法框架是：
1. 將文檔轉(zhuǎn)換為特征的集合，每一個(gè)特征有一個(gè)權(quán)重
2. 利用LSH函數(shù)把特征向量轉(zhuǎn)換為f位的fingerprint，如：64
3. 查找fingerprint的海明距離
haha,看，多么簡(jiǎn)單和明朗，這里的幾個(gè)問(wèn)題及時(shí)尋找正確的LSH
Random Projection算法
shingling關(guān)注了文檔順序，但是忽略了文檔單詞出現(xiàn)的頻率，random projection說(shuō)我要討論文檔的頻率。
Random Projection也是很有意思的一種算法，它是一種隨機(jī)算法。簡(jiǎn)單描述為：
1. 將每一個(gè)token映射到b位的空間。每一個(gè)維度是由{-1,1}組成。對(duì)所有頁(yè)面投影函數(shù)是一樣的
2. 每一個(gè)頁(yè)面的b維度向量，是所有token的投影的簡(jiǎn)單加和
3. 最后把b維向量中的正數(shù)表示為1，負(fù)數(shù)和0都寫成0
4. 比較兩個(gè)page的b維向量一致的個(gè)數(shù)
Charikar最牛的地方是，證明，兩個(gè)b位變量一致的位數(shù)的比率就是文檔向量的consine相似性。這里的數(shù)學(xué)基礎(chǔ)還是很有意思的，如果感興趣，可以參考M.S. Charikar. Similarity Estimation Techniques for Rounding Algorithm(May 2002)
SpotSig算法
ref:SpotSigs:Robust and Efficient Near Duplicate Detection in Large Web Collection
SpotSig是個(gè)比較有意思的算法，它說(shuō)，我為什么要關(guān)注所有的單詞啊，我要關(guān)注的單詞是有語(yǔ)義的詞，哪些是有語(yǔ)義的詞呢？哦，想 the a this an 的等虛詞后面的就是我要關(guān)注的東西羅。Spot就是指這些虛詞的后面的詞串。然后呢，每一個(gè)文檔我都有很多很多Spot了，現(xiàn)在一個(gè)文檔就是一個(gè)Spot的集合，兩個(gè)文檔是相似程度就是集合的Jaccard相似度。算法雖然簡(jiǎn)單，但是我想重點(diǎn)是兩個(gè)比較有借鑒意義的工程上的性能考慮。
? ? ?1. Optimal Partition
? ? ?Sim（A，B） = | A B交集| / | A B 并集| <= min(A,B)/max(A,B) <= |A|/|B| say: |A|<|B|
好了，這是一個(gè)很好的枝剪條件，如果文檔spot vector的個(gè)數(shù)比小于某個(gè)值（當(dāng)然是，小 / 大），就可以完全不用求交，并了。Optimal Partition就是說(shuō)，好啊，我把每一個(gè)文檔的spot vector的長(zhǎng)度都投影到相應(yīng)的從小到大的bucket中，保證|d1|/|d2| >=r if |d1| < |d2| . 且不存在這樣的反例。另一個(gè)保證是這個(gè)bucket是滿足條件的最小的。有了這個(gè)partition，我們最多只用關(guān)心相鄰的三個(gè)bucket了
? ?2. Inverted Index Pruning
? ?說(shuō)，兩個(gè)文檔，如果能相似，起碼有一個(gè)公共的spot。逆向索引說(shuō)的就是把spot做為index，包含它的所有文檔作為其value。
?
網(wǎng)頁(yè)去重-鏡像站點(diǎn)的特殊處理 http://blog.csdn.net/beta2/article/details/5028411
基于關(guān)鍵詞的復(fù)制網(wǎng)頁(yè)算法
想前面的提到的算法都是基于這個(gè)文檔的，對(duì)于大型的搜索引擎來(lái)說(shuō)，在性能上有些差距，所以有些優(yōu)化，針對(duì)是網(wǎng)頁(yè)的關(guān)鍵詞，或者網(wǎng)頁(yè)的meta描述部分。所以，必須有以下的技術(shù)做支撐：
1、網(wǎng)頁(yè)中出現(xiàn)的關(guān)鍵詞（中文分詞技術(shù)）以及每個(gè)關(guān)鍵詞的權(quán)重（關(guān)鍵詞密度）；
2、提取meta descrīption或者每個(gè)網(wǎng)頁(yè)的若干(比如：512）個(gè)字節(jié)的有效文字。
在以下算法描述中，我們約定幾個(gè)信息指紋變量：
Pi表示第i個(gè)網(wǎng)頁(yè)；
該網(wǎng)頁(yè)權(quán)重最高的N個(gè)關(guān)鍵詞構(gòu)成集合Ti={t1,t2,...tn}，其對(duì)應(yīng)的權(quán)重為Wi={w1,w2,...wi}
摘要信息用Des(Pi)表示，前n個(gè)關(guān)鍵詞拼成的字符串用Con(Ti)表示，對(duì)這n個(gè)關(guān)鍵詞排序后形成的字符串用Sort(Ti)表示。
以上信息指紋都用MD5函數(shù)進(jìn)行加密。
基于關(guān)鍵詞的復(fù)制網(wǎng)頁(yè)算法有以下5種：
1、MD5(Des(Pi))=MD5(Des(Pj)),就是說(shuō)摘要信息完全一樣，i和j兩個(gè)網(wǎng)頁(yè)就認(rèn)為是復(fù)制網(wǎng)頁(yè)；
2、MD5(Con(Ti))=MD5(Con(Tj)),兩個(gè)網(wǎng)頁(yè)前n個(gè)關(guān)鍵詞及其權(quán)重的排序一樣，就認(rèn)為是復(fù)制網(wǎng)頁(yè)；
3、MD5(Sort(Ti))=MD5(Sort(Tj)),兩個(gè)網(wǎng)頁(yè)前n個(gè)關(guān)鍵詞一樣，權(quán)重可以不一樣，也認(rèn)為是復(fù)制網(wǎng)頁(yè)。
4、MD5(Con(Ti))=MD5(Con(Tj))并且Wi-Wj的平方除以Wi和Wj的平方之和小于某個(gè)闕值a，則認(rèn)為兩者是復(fù)制網(wǎng)頁(yè)。
5、MD5(Sort(Ti))=MD5(Sort(Tj))并且Wi-Wj的平方除以Wi和Wj的平方之和小于某個(gè)闕值a，則認(rèn)為兩者是復(fù)制網(wǎng)頁(yè)。
關(guān)于第4和第5的那個(gè)闕值a,主要是因?yàn)榍耙粋€(gè)判斷條件下，還是會(huì)有很多網(wǎng)頁(yè)被誤傷，搜索引擎開發(fā)根據(jù)權(quán)重的分布比例進(jìn)行調(diào)節(jié)，防止誤傷。
這個(gè)是北大天網(wǎng)搜索引擎的去重算法（可以參考：《搜索引擎--原理、技術(shù)與系統(tǒng)》一書），以上5種算法運(yùn)行的時(shí)候，算法的效果取決于N，就是關(guān)鍵詞數(shù)目的選取。當(dāng)然啦，選的數(shù)量越多，判斷就會(huì)越精確，但是誰(shuí)知而來(lái)的計(jì)算速度也會(huì)減慢下來(lái)。所以必須考慮一個(gè)計(jì)算速度和去重準(zhǔn)確率的平衡。據(jù)天網(wǎng)試驗(yàn)結(jié)果，10個(gè)左右關(guān)鍵詞最恰當(dāng)。
資源：
SCAM (Stanford Copy Analysis Mechanism）=.http://infolab.stanford.edu/~shiva/SCAM/scamInfo.html

總結(jié)

以上是生活随笔為你收集整理的网页去重算法介绍的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。