文本复制检测技术综述

摘 要：针对文本复制抄袭现象,分析了文本复制检测技术的发展进展,研究了文本复制检测技术的分类,并对各种复制检测技术进行比较.

关 键 词：复制检测；字符串匹配；词频统计

中图分类号：TP391.1文献标识码：A文章编号：1674-7712（2013）04-0042-02

一、引言

如今,数字产品保护措施主要有两种：一种是通过对数据源加密,使用水印或者使用基于授权的方法等来防止用户的非法拷贝的“阻止法”.另一种是通过建立一个注册文档集库,将给定文档与库中文档进行对比检测,并向用户展示检测结果,通过对抄袭者采用一定的惩罚措施,从而遏制抄袭现象.

从上世纪70年始,文档复制检测技术就已经出现,到了90年代,自然语言文本复制检测技术开始出现.WordCheck软件诞生,其主要用于检测查询基金申请书是否有重复.从那时起,自然语言文本复制检测技术开始迅猛发展,各种复制检测系统开始出现.Mander开发了一款名叫sift的检测工具,主要用于检测查询大规模文件系统.该软件最早使用数字指纹技术来比较文档之间的相似度,数字指纹为论文复制检测技术提供了新思路.Brin等人用数字指纹技术开发了名为COPS的检测软件,可以检测出重度复制和轻度复制,斯坦福大学“数字化图书馆”项目采用了该复制检测软件.COPS软件首次采用文档注册机制,后来的其他复制检测系统多采用该软件的系统架构[1].

同年,Shivakumar等采用相关频率模型（relativefrequencymodel）开发了新的复制检测系统SCAM.SCAM从信息检索技术中的向量空间模型（vectorspacemodel）得到启发,采用优化后的余弦法来计算文档相似度.通过测试发现,SCAM性能要比COPS好.Heintze借助于数字指纹技术开发了基于Web的复制鉴别系统KOALA.Broder等使用“shingling”算法对大约150G字节的网络文档集合进行归类,取得满意结果.针对Latex格式文档,Antonio等建立了复制鉴别软件CHECK.该软件先将Latex文档分解为树型结构,再利用向量点积法来比较文档相似度.Gonostori等采用具有较高识别精度的MDR（matchdetectreveal）方法来确定文档的重叠度.MDR通过使用suffixtree结构来搜索字符串之间的最大公共子串,使用suffixvector结构来存储后缀树,以此提高鉴别效率.Finkel提出SE（signatureextraction）方法检测文档的重叠度.该方法通过使用0modp的方法对文档指纹进行随机抽样,节省了一定存储指纹的空间,改善了算法的效率.但是该方法存在一定的弊端,它适合于检测内容丰富的文档,对内容较少的文档检测效果比较差.Chowdhury等研究了大规模文档集合中重复文档的快速检测方法,该方法包括文本分块、选择、摘 要、分选和对比等步骤,仿照sift的技术研发出了I-Match系统.I-Match优点在于能够很有效的识别相似度很高的文档,提高了系统效率,其通过对数据进行去除高频词和低频词等一系列的预处理来实现,缺点是对相似度较低的文档识别效果不佳.Schleimer等提出数字指纹Winnowing算法来鉴别文档复制,并将其检测软件放置在怎么写作网站MOSS上供用户使用[2].

二、文档复制检测技术分类

根据检测方法的不同,将文档复制检测技术大致分为两大类,分别是基于字符串比较的方法和基于词频统计的方法.

(一)基于字符串匹配的方法

基于字符串匹配方法主要从文档中提取字符串,并将其作为文档检测的基本单位,然后将提取出来的字符串映射到散列表中,每个字符串都与一个数字相对应,最后统计两篇文档中相同的字符串占文本篇章的比率,通过相似度计算公式来计算出两篇文档之间的相似度,进而判别两篇文档间是否存在抄袭现象.如今,很多文档复制检测系统都是使用基于字符串的匹配方法来实现的,如COPS原型系统、MOSS原型系统、MDR原型系统等.下面就对这几个典型的系统做简单的介绍.

COPS原型系统要求每篇要注册到文档库中的文档都必须检测.该系统以标点符号为界,首先将文档按照一个个句子划分,并通过哈希函数将句子转成相应的散列值,并通过同样的方式获得待检测文档中的句子散列值.然后,通过将检测文档中的句子散列值和文档库中文档中的句子散列值对比,通过对比结果来判断注册文档的相似程度,从而度量注册文档是否为抄袭文档.COPS对文档间的重度抄袭具有良好的检测效果,但是该系统对于轻度抄袭现象的检测效果不佳,并且不能准确的划分句子.对于有效句子的提取是一个较大的难点,因为文档中一些术语、公式和单词的缩写等常使COPS对句子的界定造成误判.

基于数字指纹的Winnowing算法,MOSS系统通过基于k-gram算法来将文档指纹提取出来,将所有长度为len的字符串提取出来作为文档的特征项,两个相邻的指纹间有len-1个相同的字符.通过对文档间的指纹进行筛选后,获取文档的特征项,便可根据相似度公式计算文档的相似程度,并判断其是否存在剽窃行为.k-gram虽然有对指纹进行筛选工作,但是依旧会产生大量的指纹,不但耗费大量存储空间并且需要巨大对比量来检测抄袭.MOSS系统通过对k-gram算法的进一步改进,使用随机抽样的方法筛选文档中的指纹.MOSS通过一个limen-len+l大小的滑动窗口提取文档指纹集,并且滑动窗口中都必须选取一个选取哈希码最小的那个指纹作为文档的特征项.当窗口中最小的指纹有多个时,选择最右边的那个指纹作为文档的特征项.采用滑动窗口对指纹集的提取不仅保证了指纹的覆盖率并且保证了指纹的密度.通过测试结果显示,该改进方法效果良好.

基于构建后缀树的MDR原型系统首先把被比较文档构造成一棵后缀树,然后运用匹配统计算法直接在被检测文档中寻找最大匹配字符串.早起MDR的主要缺陷是不适合对大量文本进行检测,其原因是MDR的后缀树需要使用大量存储空间.后来Monostori对MDR原型系统进行了改进,提出用后缀向量存储后缀树.后缀向量也是一种存储方式,需要从后缀树导出有向无环图.这种方式不保存边索引,只保存结点信息,从字符串中获取边标识.这种改进方法节省了大量存储空间.

(二)基于词频统计的方法

该方法源自于信息检索技术,用一组拥有由独立词条的向量空间来表示一篇文档.根据各个词在文档中出现的次数,采用点积法、余弦法等计算两个文档向量之间的相似度,从而判断两篇文档间是否存在拷贝现象.

SCAM改进了COPS,主要用于发现知识产权冲突.SCAM原型系在信息检索技术中的向量空间模型基础上做了改进,使用基于词频统计的方法来计算文档间的相似度.系统首先对文档的词频进行统计,在向量空间模型的基础上,提出了相关频率模型RFM（RelativeFrequencyModel）,用来计算文档的相似度.向量空间模型一般采用点积或者余弦公式来度量相似性,而相关频率模型则对余弦公式进行了改进,试图提高文档复制检测的精度.此外,为加快查找比对效率,SCAM原型系统使用倒排序的索引结构来存储数据库中已有文档的文本块.当有新文档需要检测时,就把新文档注册到数据库中,创建并保留该文档文本块的索引.每个文本块的入口指向若干条记录,每一个记录都有两个属性：document（文档唯一标示符）和frequency（文本块在文档中出现的频率或次数）.SCAM检测机制把文档转化成词袋的形式（bagofwords）,而没有考虑词与词之间的搭配组合,对于同一个专业提交的学生作业来说,由于关 键 词大部分相同,因而误判率高.

CHECK原型系统使用的是基于关 键 词统计的方法.该软件的最大特点就是把待测文档结构信息引入到文档相似性度量中.系统每剖析一篇待测文档,就将获得的结构特征插入注册数据库中.按照要求,系统把一篇文档按照其章、节、段落等方式组织成一棵文档树,树的根结点就是整篇文档,其他结点是文档的一个片断.各个子结点内容之和构成父节点.系统运用信息检索技术中关 键 词提取的方法,根据词频提取整篇文档的关 键 词.统计各个结点上出现的关 键 词及其在该结点上的频率比重,由此得出相应权重.最后,按此方法构成的树就成为该文档的结构特征.