本文關(guān)鍵詞：一種基于Simhash的文本快速去重算法

  更多相關(guān)文章： Simhash 文本去重 特征向量 海明距離 Hash

【摘要】：在萬維網(wǎng)中，大多數(shù)的網(wǎng)頁都是重復(fù)的，然而，這些重復(fù)的網(wǎng)頁對于搜索引擎返回的搜索結(jié)果是冗余的，搜索結(jié)果大多數(shù)不能體現(xiàn)用戶查詢意圖。如果能將這些冗余的搜索結(jié)果去重，并實現(xiàn)返回結(jié)果按照重復(fù)率最大的網(wǎng)頁進行排序顯示給用戶，，無疑是一種可以滿足用戶查詢需求的方式，那么，網(wǎng)頁去重亟需解決的是使用什么樣的技術(shù)手段判斷網(wǎng)頁內(nèi)容是重復(fù)的最重要，如何能夠去除相同或者相似的網(wǎng)頁可以提高檢索效率、降低存儲開銷。 實際搜索中，搜索引擎返回數(shù)據(jù)會給用戶提供很多相同的查詢記錄，但是如果返回重復(fù)的搜索結(jié)果是不科學(xué)的，因為大多數(shù)返回結(jié)果存在相似度極高的情況，甚至就被檢索到的是同一個網(wǎng)頁，當爬蟲抓取網(wǎng)頁的同時可以判斷下其網(wǎng)址是否在已經(jīng)下載的列表中，如果該網(wǎng)址的前半部分是相同的，可以認為它們可能是重復(fù)性的網(wǎng)頁，這些重復(fù)的網(wǎng)頁直接就不用下載，但是，在網(wǎng)址不相同的情況下，也可能網(wǎng)頁內(nèi)容是重復(fù)的，這種情況下的網(wǎng)頁也不必出現(xiàn)的結(jié)果也中，那么，一個精銳的問題就是：很多重復(fù)的網(wǎng)頁到底選哪一個作為返回結(jié)果呢？ 提到文本相似性計算，首先要想到的應(yīng)該是向量空間模型VSM（VectorSpace Model），這種方法存在的問題是：需要對網(wǎng)頁兩兩比較相似度，無法擴展到海量網(wǎng)頁的處理。傳統(tǒng)的判斷網(wǎng)頁相似度的經(jīng)典方法是“向量夾角余弦”，其主要思想是一篇網(wǎng)頁中出現(xiàn)詞的詞頻構(gòu)成一個二維向量，然后計算網(wǎng)頁之間對應(yīng)的向量夾角余弦，但是，尤其一篇網(wǎng)頁中含有大量的特征詞，導(dǎo)致生成的二維向量的維度特別的高，這樣一來使得計算的代價太大乃至于超出了預(yù)計的時間、空間復(fù)雜程度，那么對于大型的搜索引擎處理上萬億級別的網(wǎng)頁請求是不可接受的。于是，Simhash算法誕生了，其主要思想是“降維”，將高維的特征向量映射成一個唯一“Simhash”值標識，所以比較網(wǎng)頁唯一“指紋碼”標識來確定的網(wǎng)頁的是否重復(fù)。 本文主要方法是一種基于Simhash的文本快速去方重法，一篇網(wǎng)頁提取出網(wǎng)頁內(nèi)容后，必須經(jīng)過基本的預(yù)處理，比如：（中文的，去除停留詞、中文分詞處理、英文的，去除停留詞、詞根還原），最后會得到一個向量，實驗結(jié)果表明，本文提出的方法的實驗結(jié)果良好。
【關(guān)鍵詞】：Simhash 文本去重 特征向量 海明距離 Hash
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP391.3;TP393.092
【目錄】：

• 提要4-5
• 摘要5-7
• Abstract7-11
• 第1章 引言11-15
• 1.1 研究背景11-12
• 1.2 研究意義12
• 1.3 研究現(xiàn)狀12-13
• 1.4 研究內(nèi)容13-14
• 1.5 論文結(jié)構(gòu)14-15
• 第2章 網(wǎng)頁去重算法簡介15-18
• 2.1 文本去重預(yù)處理技術(shù)15-16
• 2.2 獲取重復(fù)文本技術(shù)16-17
• 2.2.1 網(wǎng)頁自動聚類16
• 2.2.2 網(wǎng)頁自動分類16-17
• 2.2.3 基于網(wǎng)頁規(guī)則的算法17
• 2.2.4 基于網(wǎng)頁距離的算法17
• 2.3 小結(jié)17-18
• 第3章 一種基于 Simhash 的文本快速去重算法18-29
• 3.1 文本去重基本概念18-19
• 3.1.1 文本相似基本定義18-19
• 3.1.2 文本相似基本性質(zhì)19
• 3.1.3 文本去重字符表及其含義19
• 3.2 文本去重算法之 IF-IDF 算法19-21
• 3.2.1 IF-TDF 算法19-20
• 3.2.2 基于 TF-IDF 相似度算法描述20-21
• 3.2.3 基于密度的去重算法21
• 3.3 基于 Simhash 文本快速去重算法21-27
• 3.3.1 Simhash 算法22-24
• 3.3.2 Simhash 算法流程圖24-25
• 3.3.3 Simhash 算法應(yīng)用與海量數(shù)據(jù)去重25-27
• 3.4 小結(jié)27-29
• 第4章 實驗結(jié)果及分析29-35
• 4.1 Simhash 和 hash 算法比較29-30
• 4.2 運行時間及壓縮比實驗分析30-34
• 4.2.1 運行時間分析30-31
• 4.2.2 幾種算法去重壓縮比31
• 4.2.3 獲取文本 Simhash 值實驗分析31-34
• 4.2.4 海量文本 Simhash 實驗分析34
• 4.3 小結(jié)34-35
• 第5章 結(jié)論與展望35-37
• 5.1 結(jié)論35-36
• 5.2 進一步研究方向36-37
• 參考文獻37-39
• 作者簡介及在學(xué)期間所取得的科研成果39-40
• 致謝40

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前6條

1 樊勇;鄭家恒;;基于主題的網(wǎng)頁去重[J];電腦開發(fā)與應(yīng)用;2008年04期

2 王小華;盧小康;;基于N-Gram的文本去重方法研究[J];杭州電子科技大學(xué)學(xué)報;2010年02期

3 黃仁;馮勝;楊吉云;劉宇;敖民;;基于正文結(jié)構(gòu)和長句提取的網(wǎng)頁去重算法[J];計算機應(yīng)用研究;2010年07期

4 吳平博,陳群秀,馬亮;基于特征串的大規(guī)模中文網(wǎng)頁快速去重算法研究[J];中文信息學(xué)報;2003年02期

5 曹玉娟;牛振東;彭學(xué)平;江鵬;;一個基于特征向量的近似網(wǎng)頁去重算法[J];中國索引;2009年01期

6 謝蕙;秦杰;胡雙雙;;基于用戶查詢關(guān)鍵詞的網(wǎng)頁去重方法研究[J];現(xiàn)代圖書情報技術(shù);2008年07期

本文編號：622360