基于minwise哈希的文檔復制檢測的研究及應用.pdf

1、WEB正經歷著爆炸性增長，海量文檔中存在大量的相似信息，這些相似性文檔一方面消耗了高額的檢索資源，另一方面影響了用戶的使用。文檔的數(shù)字化和易獲性也使得非法復制、剽竊等行為越來越猖獗。為保護知識產權和提高信息檢索效率，文檔復制檢測技術應運而生并得到迅速發(fā)展。
　　文檔復制檢測就是判斷給定文檔是否抄襲、剽竊或者相似于一篇或多篇文檔的內容。論文以某基金項目相似性檢測為實際應用背景，為了在海量數(shù)據(jù)環(huán)境中快速而準確地檢測出文檔的相似性，主要

2、研究相似性檢測系統(tǒng)中涉及的關鍵技術，重點研究相似度估計算法、相似度檢索算法和基于SIMD優(yōu)化的相似度比對等關鍵技術，具體進行了如下的研究工作:
　　(1)針對文檔相似性檢測系統(tǒng)中精度和存儲空間只能取離散值、粒度過粗的問題，提出了分數(shù)位minwise哈希算法，驗證了分數(shù)位minwise哈希算法的可行性，構造了使得估計方差最小的最優(yōu)分數(shù)位。分數(shù)位minwise哈希算法將整數(shù)位minwise哈希擴展到分數(shù)位，突破了b整數(shù)位的限制，使得相

3、似度可以使用分數(shù)位來估計，不僅完善了minwise哈希算法的理論體系，也為實際系統(tǒng)中的用戶對于相似度估計的精度和存儲空間更加細粒度可選擇性需求提供支撐。
　　(2)針對文檔相似性檢測效率不高的問題，提出了連接位minwise哈希算法。連接位minwise哈希算法將位連接起來進行相似性度量，證明與推導及實驗結果顯示算法雖然犧牲5％精度，卻能成倍地減少比對的次數(shù)，大大提升算法的時間性能。一方面，連接位無需任何復雜的操作，方便構建;另一

4、方面，億萬級文檔的相似度的估計，通過損失一定的精度誤差，獲得了性能的成倍提升具有很強的實際應用意義。
　　(3)針對海量文檔相似性檢索中相似度閾值不能設置過低，初始指紋數(shù)少等問題，提出了指紋分組合并檢索算法，理論推導及實驗結果表明算法能夠在低相似度閾值（比如70％）下快速地從已有的文檔集中檢索目標文檔，從而實現(xiàn)相似性文檔查詢的實時性，并且由于降低了相似度閾值，也增大了相似性檢索的應用范圍。
　　(4)針對某基金對相似性證據(jù)快

5、速采集和清晰呈現(xiàn)的特殊需求，提出了基于SIMD優(yōu)化的相似性比對算法。通過使用SIMD指令集和OpenCL框架對相似度比對算法進行了一系列的優(yōu)化，實驗結果表明優(yōu)化算法提升了可提升11.6％-170％的時間性能，一方面使得相似性有跡可循;另一方面也有利于人工復審工作。
　　(5)針對某基金項目相似性檢測系統(tǒng)中存在的項目數(shù)據(jù)難以準確快速提取、海量項目數(shù)據(jù)比對時間超長、比對結果難以清晰呈現(xiàn)等關鍵問題，論文論述了如何采用所研究的關鍵技術形成