算法网页检测

摘要随着互联网的发展,大量近似重复的文本广泛存在于现实世界中,如何检测这些近似重复的文本成为了一个研究的热点问题,这一技术在不同领域存在着很多应用:数字图书馆中相似内容的自动链接、数字知识产权保护(剽窃检测)、近似重复网页检测(搜索引擎优化)、数据去重、垃圾邮件检测等.
采用传统的哈希算法(SHA1、MD5等)只能鉴别完全相同的文档,不适用于存在细微修改的近似文档.
当前,近似重复检测的主要方法是生成文本指纹,通过计算文本间文本指纹的距离,衡量文本的相近程度.
本文在研究该领域的三种代表性算法(shingling、I-Match、simhash)的基础上,提出了融合这些算法优点的改进算法并进行了系统实现和验证,主要工作包括三个方面:(1).
提出了基于shingle特征的simhash算法.
Shingling算法以连续词串作为特征,有利于提高检测的准确率,但生成指纹集合、计算集合基于Jaccard相似度的距离,计算量大.
Simhash算法以指纹间的汉明距离度量相似性,计算量小,且指纹占用空间小.
但simhash算法以单词为特征,不能很好的表征文档的语义.
本文将shingles作为simhash算法的输入特征,以提高simhash算法的准确率.
(2).
提出了基于随机词典的多指纹simhash算法.
I-Match算法完全依赖单词的IDF值去除近似重复文本间的不同单词,检测的召回率很低.
基于随机词典的I-Match算法提出利用原始文档集的词典随机生成多个子词典,子词典分别过滤文档,生成多个I-Match指纹,以提高I-Match方法的稳定性.
对于同样是生成单指纹比对的simhash算法,本文引入基于随机词典的I-Match算法的提高召回率的方法,以提高simhash算法的召回率.
(3).
以"中美百万册数字图书馆"中的图书数据构建了一个近似重复文本检测数据集,对上述两种改进算法在该数据集上进行了的实验验证.
在最优参数、F-measure的度量上,基于shingle特征的simhash算法的0.
7469比原simhash算法的0.
6117提高了22%;融合算法的0.
8805比基于shingle特征的simhash算法的0.
7469提高了18%,比原始的simhash算法提高了43%.
实验表明两点改进思路对相应性能的提升都得到了验证,最终的融合算法比原始simhash算法在F-值度量上有较大提升.
本文认为,取得如此性能提升的主要原因是,依据三种经典算法的特点,进行了有针对性的融合,改进了simhash算法的特征选择策略和指纹生成策略,分别有利于simhash算法准确率和召回率的提升.
关键词:近似重复文本检测、网页去重、simhash算法DocumentfingerprintanditsapplicationinnearduplicatedocumentdetectionJunFanMicroelectronicsDirectedbyTieJunhuangWiththerapiddevelopmentoftheWorldWideWeb,disseminationreproducedorplagiarismother'sliteraturewithorwithoutmodificationhasbecomeveryeasy.
Thereareahugenumberofthesekindsofduplicateddocumentsintherealworld.
Howtodetectthesenearduplicatedocumentshasbecomeahotresearchtopic.
Thereisawiderangeofapplications.
Suchas:Automaticallylinkofduplicatedocumentinthedigitallibrary,protectionofintellectualproperty(orcalledplagiarismdetection),nearduplicatewebpagedetection(onekindofsearchengineoptimizationtechnique),datadeduplication,spamdetection.
TraditionalHashalgorithmslikeSHA1,MD5canonlydetectdocumentsexactlythesameornot.
Theycan'thandledocumentswithminormodifications.
Themainmethodinnearduplicatedocumentdetectionisgeneratingdocumentfingerprints,measurethesimilarityofdocumentsthroughthedistanceofthecorrespondingdocumentfingerprints.
Inthisarticle,wedescribedthethree"stateofart"algorithm(shingling,I-Match,simhash)indetail.
Wedidsomefusionbasedonthecharactersofeachclassofalgorithmsmentionedabove,implementedasystemandsomeexperiments.
Ourworksare:1.
Shinglingbasedsimhashalgorithm:theinputfeatureofshinglingalgorithmisk-shingles(wordsequencesoflengthk),itisbenefitfortheprecisionofdetection.
ButthemeasureofdistanceoffingerprintsisJaccardsimilarityofset,haveahighcomputationalcomplexity.
Thedistanceoffingerprintsinsimhashalgorithmishammingdistance;itislowincomputationalcomplexity,andsmallinspace.
Buttheinputfeatureofthesimhashalgorithmiswordsofthedocument;itcan'trepresentthedocumentwell.
Inthisarticle,weusethek-shingles(wordsequencesoflengthk)asthefeaturesofthesimhashalgorithmtoimproveprecisionofsimhashalgorithm.
2.
Multiplerandomlexiconsbasedsimhashalgorithm:theeffectivenessoftheI-MatchalgorithmisbasedonfilteringdifferentwordsinnearduplicatedocumentsbyIDFvaluesofthewordstotally.
Ithasalowrecall.
ThemultiplerandomlexiconsbasedI-MatchalgorithmfilterdocumentsbyrandomlycreatedlexiconsandgeneratemultiplefingerprintstoimprovethestabilityoftheI-Matchalgorithm.
Thismethodisapplicabletoothersingle-signaturebasedalgorithm,suchassimhash.
Wefilterdocumentsbyrandomlycreatedlexiconsandgeneratemultiplesimhashfingerprintstoimproverecall.
3.
Weconstructanearduplicatedocumentdetectdatasetbasedonthebooksinthe"China-USMillionBookDigitalLibraryProject".
Wetestedouralgorithmsinthissyntheticdataset.
Withthebestparameters'setandintheF-measure'sview,fromtheshinglingbasedsimhashalgorithmtothesimhashalgorithm,wegeta22%improvementfrom0.
7469to0.
6117.
Fromthefusionalgorithmtotheshinglingbasedsimhashalgorithm,wegetan18%improvementfrom0.
8805to0.
7469.
Ourfusionalgorithmgetsa43%improvementcomparedwiththesimhashalgorithmintotal.
Theexperimentresultprovestheefficiencyoftheabovetwoalgorithms.
ThefusedintegratedalgorithmperformsmuchbetterthantheoriginalsimhashalgorithmintheF-measure'sview.
Withsuchanimprovement,credittothetargetedfusionbasedonthecharactersofeachalgorithms.
Weimprovedthefeatureselectionstrategyandthefingerprintgenerationstrategyofthesimhashalgorithm,whichhelptoimproveprecisionandrecallcorrespondingly.
Keywords:nearduplicatedocumentdetection、nearduplicatewebpagedetection、simhashalgorithm