1、法律o本課件：演示文稿，示例，代碼，題庫，和聲音等，小象學院擁有完全知識產權的權利；只限于善意學習者在本課程使用，不得在課程范圍外向任何第散播。任何其他人或機構不得盜版、仿造其中的者的權利。創意，保留一切通過法律o課程n咨詢：大數據分析挖掘nHadoop新浪：互聯網新技術在線教育領航者分布式爬蟲互聯網新技術在線教育領航者大綱l文本分詞l爬取l網頁排重互聯網新技術在線教育領航者文本分詞互聯網新技術在線教育領航者網頁排重互聯網新技術在線教育領航者重復網頁類型互聯網大量的內容，也不同域名指向同一的情況，因此抓取回來的網頁會有大量的重復。除了全文重復之外，還存在主要內容重復等情況，關于重復，我們定義以

2、下4種類型： 如果2篇文章內容和格式上毫無差別，則這種重復叫做“完全重復頁面” 如果2篇文章內容相同，但是格式不同，則叫做“內容重復頁面” 如果2篇文章有部分重要的內容相同，并且格式相同，則稱為“布局重復頁面” 如果2篇文章有部分重要的內容相同，但是格式不同，則稱為“部分重復頁 面”互聯網新技術在線教育領航者的目的就能節省一部分對以往搜集空間，提高檢索的質量的分析，預先發現重復網頁，在今后的網頁搜集過就可以避開這些網頁對重復次數多的網頁，給予更高的 page rank提高容錯能力。比如一個網頁的圖片不的網頁上嘗試提取圖片了，我們可以到它類似互聯網新技術在線教育領航者的目的就能節省一部分對以往搜

3、集空間，提高檢索的質量的分析，預先發現重復網頁，在今后的網頁搜集過就可以避開這些網頁對重復次數多的網頁，給予更高的 page rank提高容錯能力。比如一個網頁的圖片不的網頁上嘗試提取圖片了，我們可以到它類似互聯網新技術在線教育領航者算法 文本相似度將一篇文章分詞后，詞匯加權個，稱之為這篇文章的特征向量，如果兩篇文章的相似度很高，那么他們在高比較小里的夾角應該就計算的夾角：𝑣1 × 𝑣2 =𝑣1 |𝑣2|𝑐𝑜𝑠𝜃互聯網新技術在線教育領航者算法 文本相似度從附

4、加賽第三輪以3-0力擒，到小組賽首輪以1-0絕殺首爾FC，再到此役5-1大比分戰流浪者，上海上港在新賽季的亞冠賽場上一舉拿到三連勝，為球隊在賽季初始階段開了個好頭。此役戰流浪者后，上港不但繼續保持，也成為在亞冠改制后，繼泰達、國安和恒大之后第三支前2輪著主場不敗的全勝的球隊。從附加賽以3-0力擒，到小組賽以1-0絕殺首爾FC，再到此役5-1大比分戰流浪者，上海上港在新賽季的亞冠賽場上拿到三連勝，為球隊在賽季開了個好頭。戰流浪者后，上港不但繼續保持著主場不敗的，也成為在亞冠改制后，繼泰達、國安和恒大之后第三支前2輪全勝的球隊。互聯網新技術在線教育領航者文本相似度計算、小組賽、首輪、絕殺、首爾FC

5、、此役、大比分、戰附加賽、流浪者、上海上港、賽季、亞冠、賽場、連勝、球隊、賽季、好頭、戰流浪者、上港、主場、不敗、球隊、亞冠、改制、泰達、國安、恒大、全勝提取特征3023423425234235234232計算夾角𝜃=𝑎𝑟𝑐𝑜𝑠( 𝑣1×𝑣2 )𝑣1𝑣2互聯網新技術在線教育領航者文本相似度計算時間復雜度太高，𝑛2Time Complixity30002500200015001000500001020304050

6、60互聯網新技術在線教育領航者算法- SimHash互聯網新技術在線教育領航者SimHash I 分詞分詞，把需要文本分詞形成這個文章的特征單詞。最后形成去掉噪音詞的單詞序列并為每個詞加上權重，我們假設權重分為5個級別（15）341344555附加賽小組賽首輪 絕殺首爾FC西流浪者上海上港賽季亞冠互聯網新技術在線教育領航者SimHash II Hash通過hash算法把每個詞變成 Hash算為 111000，“上海上港”通過值，比如“亞冠”通過 Hash 算法計Hash 算法計算為 101011。這樣我們的字符串就變成了一串串數字，要把文章變為數字計算才能提高相似度計算性能，現在是降維過程進行

7、時3413555101001101110110001101000101011101100111000附加賽小組賽首輪 絕殺上海上港賽季亞冠互聯網新技術在線教育領航者SimHash III 加權Hash 生成結果，需要按照單詞的權重形成加權數字串，bit為 1，權重值乘以1，bit 位為0，權重值乘以-1，比如“亞冠”的 Hash 值為 111000，通過加權計算為5 5 5 -5 -5 -534135551010011011101100011010001010111011001110003 -3 3 -3 -3 34 -4 4 4 4 -4.附加賽小組賽首輪 絕殺上海上港賽季亞冠5 5 5 -

8、5 -5 -5互聯網新技術在線教育領航者SimHash VI 合并把上面各個單詞算出來的序列值累加，變成只有一個序列串，也就是每一個數字位相加34135551010011011101100011010001010111011001110003 -3 3 -3 -3 34 -4 4 4 4 -41 1 -1 -1 -1 13 -3 3 -3 -3 -35 -5 5 -5 5 55 -5 5 5 -5 -55 5 5 -5 -5 -5附加賽小組賽首輪 絕殺上海上港賽季亞冠26 -24 24 -8 -8 -8互聯網新技術在線教育領航者SimHash V 降維將結果轉換為 0 1 這樣的序列，規則是如

9、果一個位上的和（例如第一位的和是26）> 0，則該位設置為1；否則為 026 -24 24 -8 -8 -81 0 1 0 0 0互聯網新技術在線教育領航者SimHash 圖解互聯網新技術在線教育領航者SimHash 意義將加權值合并的時候進行了第一步的降維，在最后一步根據正負換算為1和0（不考慮數值本身的大小，只考慮正負）進行了第二次降維，因此最終的Hash 值對字符串的改變變得不是很敏感。傳統 Hash 算法，任意字符的變化，都會導致整個 Hash 結果的劇烈變化上港不但繼續保持著主場不敗的上港不但繼續保持主場不敗的，也成為在亞冠改制后，成為在亞冠改制后SimHash01011011

10、010000md5: 68254e797b2bdc7e022b0004649a8c96a500532daefa7bdbc50159fce4687208互聯網新技術在線教育領航者SimHash 海明距離海明距離：兩個二進制串中不同位的數量可以通過異或，然后求bit為1的個數，即A xor B 后二進制中1的個數Library: SimHash init: 構造函數，文本build_by_features(): 輸入一個 dictionary 或者 包含tuple的數組，以key weight 的方式輸入，例如 Apache:20, hadoop:25 或(Apache, 20), (hadoop

11、, 25)distance(another)：計算與另一個Simhash 對象的海明距離互聯網新技術在線教育領航者SimHash 海明距離pip install simhashfrom simhash import Simhashstr0 = 'The Apache Hadoop software library is a framework that allows forthe distributed processing large data'str1 = 'The Apache Hadoop software library is a framework that

12、 allows for the distributed processing big data'# 構造 SimHash 對象sh0 = Simhash(str0) sh1 = Simhash(str1)# 構造特征值，關鍵字加權features = ('Apache', 10),('Hadoop', 15),('framework', 3), ('distributed', 10), ('data', 6)# 不加權計算sh0.distance(sh1) # 加權計算海明距離sh0.build_by_fe

13、atures(features)sh1.build_by_features(features) sh0.distance(sh1)互聯網新技術在線教育領航者處理數百萬的網頁？假設我們需要計算海明距離在3以內的網頁，可以將64位在3以內組合列出來，一共是Hash 所有變化= 64 × 63 × 62𝐶3643 × 2= 41664當海明距離增加，所需要的空間也指數級增加，思考找一種更加高效的方法？互聯網新技術在線教育領航者處理數百萬的網頁？問題：一個80億的64-bit組成的集合Q，對于一個給定64-bit的F，如何在毫秒級找到Q中和 f 至多只有

14、𝑘( 𝑘 = 3 )位 差別的？如果將 f 的 64位 Hash 所有變化在3以內組合列出來，一共是𝐶3+ 𝐶2+ 𝐶1+ 𝐶0= 4374564646464也就是說，所有與文檔F，組成的列表里距離在3以內的文檔一定于這43745個互聯網新技術在線教育領航者兩種簡單的辦法 online，實時把 F 的 43745種距離為3個結果計算出來，然后依次查找，因此需要計算出43745個結果并進行43745次查找 offline，離線把 F 的 43745個距離為3個結果緩存起來。意味著43745個SIMHA

15、SH拷貝，總量，如果一萬個網頁，每個網頁需要為 437,450,000 個 SIMHASH值，這樣可以在𝑂(1)的時間查找出所有相似網頁互聯網新技術在線教育領航者優化查找過程結合一下，不要實時計算所有的 SimHash 可能性并逐把上面的一比較，提前進行一些離線計算，但同時也全部都算出來，以至于43745倍個拷貝，我們做一個折中假設我們計算的是海明距離為3以內的網頁，那么根據抽屜原則，如果把SimHash 的64 位分為4塊，ABCD，如果2個海明距離為3以內的網頁， 它們至少有一個塊是完全一樣的互聯網新技術在線教育領航者分為4等份1100101100100010110010000000001011001111000000100000101100101100根據抽屜原則，如果海明距離為3，那么至少有1個塊會完全重合互聯網新技術在線教育領航者算法復雜度空間會增加到 4 倍，搜索時間，由于排除了16個bit位，因此總的可能性降低從 264 降低到了4