基于minwise哈希的文檔復(fù)制檢測(cè)的研究及應(yīng)用.pdf

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

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

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

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

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