网页查重算法的起源

  早在20世纪70年代初,就有学者研究阻止大规模拷贝程 序的技术和软件。但是这只是用于复制检测,也就是剽
窃检测,其目的在于知识产权的保护,Ottenstein在1976年提出了 基于属性计数法(Attribute Counting)检
测软件剽窃的方法。但是,单纯的属性计数法抛弃了太多的程序结构信息,导致错误 率太高。Verco和Wise 在
1996年指出,对于仅仅使用属性 计数法的检测算法,增加向量维数并不能降低错误率。改进属性计数法的措施就
是加入程序的结构信息,结合结构度量 (Structure Metrics),也称为控制流(Control—flow)来检测剽窃。
现在检测程序复制都是用各种方法综合属性计数和程序结构度量n 。Parker等人 和Clough分别对上述的各种程
序复制检测方法作了详细的介绍和评述。
   在二十年后,出现了自然语言的复制检测,这一部分就涉 及到了网页查重技术。1993年,Arizona大学的
Manber提出了 一个sifl 工具,用于在大规模文件系统中寻找内容相似的文件。 工具提出了近似指纹(Approximate
 Fingerprints),就是 用基于字符串匹配的方法来度量文件之间的相似性。这个思 路被后来很多的文本复制检测
系统所采用。1995年,Stanford大学的Brin和Garcia—Molina 等人在“数字图书馆”工程中首次 提出了COPS(Copy
 Protection System,文本复制检测机制)系统 与相应算法 ,COPS系统框架为以后的自然语言文本复制检测系统
奠定了基础。Garcia.Molina和Shivakumar等人又提出 了SCAM(Stanford Copy Analysis Method) 刮原型改
进c0ps系 统,用于发现知识产权冲突。SCAM借鉴了信息检索技术中的向量空间模型(Vector Space Mode1),使用
基于词频统计的方法 来度量文本相似性。后来Garcia-Molina和Shivakumar等人还在SCAM的基础上提出了dSCAM模
型,将检测范围从单个注册数据库扩展到分布式数据库上以及在Web上探测文本复 制的方法。同期,贝尔实验室的
Heintze开发了KOALA系统用于剽窃检测。KOALA系统采用与Sif基本相同的方法,与之类似的方法还有Broder等人提
出的Shingling方法。到了2000年,Monoatori等人建立了MDR(Match Detect Revea1)原型。MDR采用后缀树
(Sufix Tree)来搜寻字符串之间的最大子串。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: