（计算机应用技术专业论文）查重技术及其在信息校验中的应用研究.pdf

摘要 摘要 随着信息社会的发展，与知识产权保护、学术研究、信息检索和各种申报 与统计分析等应用相关的信息越来越多，而在这些应用中需要对大量信息是否 重复或相似进行检查，包括直观的内容重复或相似检查、隐含的内容重复或相 似检查、内在的约束关系校验等，查重方法和技术是解决此类问题的关键，是 建立高效和实用的信息校验系统的基础。 本文以学科和论文类信息采集与评估应用系统为背景，重点研究以中文分 词技术为基础的查重方法和技术，提出一种信息校验系统结构，在此基础上通 过实验方法研究了查重技术及其应用问题，实现了以词法和语法信息为辅助信 息的文本重复与相似的查重算法，并对算法的性能进行了分析研究。 以实际的学科类和论文类信息采集系统为背景，本文介绍了现有的文本查 重技术及方法，总结分析了本领域中相关的概念模型，研究了多种查重算法和 实现技术，具体分析了信息校验系统中需要解决的查重关键问题，研究分析了 不同的经典信息查重算法原理和模型，用实验数据对以词法和语法信息为辅助 信息的文本重复与相似的查重算法进行测试分析，研究查重算法的运行性能等 应用问题，为实现高效和实用的信息校验系统提供参考。 关键词：信息校验查重技术中文分词 a b s t r a c t a b s t r a c t w i t ht h e d e v e l o p m e n to fi n f o r m a t i o ns o c i e t y , t h e r e a r em o r ea n dm o r e i n f o r m a t i o nr e l a t e dt op r o t e c t i o no fi n t e l l e c t u a lp r o p e r t y , a c a d e m i cr e s e a r c h , a n d v a r i o u sd e c l a r a t i o na n ds t a t i s t i c a la n a l y s i s ，i nw h i c hw en e e dt oc h e c kt h ed u p l i c a t i o n o rs i m i l a r i t yo fh u g ea m o u n to fd a t a , i n v o l v i n gd i r e c to ri m p l i c i tc o n t e n td u p l i c a t i o n o rs i m i l a r i t yc h e c k , o rv e r i f i c a t i o no fi n h e r e n tc o n s t r a i n t d u p l i c a t i o nd e t e c t i o n t e c h n i q u e sa r et h ek e yt ot h i sk i n do fp r o b l e m sa n dt h eb a s i so fa ne f f e c t i v ea n d p r a c t i c a ls y s t e mf o ri n f o r m a t i o nv e r i f i c a t i o n a sab a c k g r o u n do ft h ec o u r s ea n dt h e s i sc o l l e c t i o na n de v a l u a t i o ns y s t e m ，t h i s t h e s i sp r o p o s e ss y s t e ma r c h i t e c t u r ef o ri n f o r m a t i o nv e r i f i c a t i o n , w i t hf o c u so n d u p l i c a t i o nd e t e c t i o nt e c h n i q u e sb a s e do nc h i n e s ew o r ds e g m e n t a t i o n ad u p l i c a t i o n d e t e c t i o na l g o r i t h mf o rt e x ts i m i l a r i t yd e t e c t i o nb a s e do nl e x i c a la n dg r a m m a r a n a l y s i s ，w i t hi t sp e r f o r m a n c ea n a l y s i sb ye x p e r i m e n t s ，i sa l s op r e s e n t e d t h et h e s i si sb a s e do nt h ea c t u a lc o u r s ea n dt h e s i sc o l l e c t i o na n ds y s t e m ， i n t r o d u c e st h ep o p u l a rt e x td u p l i c a t i o nd e t e c t i o nm e c h a n i s m s ，s u m m a r i z e sa n d a n a l y z e st h er e l a t e dc o n c e p t u a lm o d e l s ；d o s er e s e a r c h o ns e v e r a l d u p l i c a t i o n d e t e c t i o n a l g o r i t h m s a n di m p l e m e n t a t i o n s ，a n d a n a l y z e sc o n c r e t e l y t h em o s t i m p o r t a n to fd u p l i c a t i o nd e t e c t i o np r o b l e mo fa l li n f o r m a t i o nv e r i f i c a t i o ns y s t e m t h i st h e s i sa l s oi n c l u d e st h er e s e a r c ha n da n a l y s i so ft h ed i f f e r e n tk i n do ft h ec l a s s i c d u p l i c a t i o nd e t e c t i o na l g o r i t h m sp r i n c i p l ea n dm o d e l s ，u s i n gt h ee x p e r i m e n t a ld a t at o t e s tt h ea l g o r i t h m sw h i c hh a ss y n t a x ，s e m a n t i ct ob et h es u p p l e m e n t a r yi n f o r m a t i o n , a n dt h er e s e a r c ho nt h ep e r f o r m a n c eo ft h ea l g o r i t h m s ；i tc a nb eag o o dr e f e r e n c ef o r h i 业p e r f o r m a n c ea n dp r a c t i c a li n f o r m a t i o nv e r i f i c a t i o ns y s t e m k e y w o r d s ：i n f o r m a t i o nc h e c k i n g ，d u p l i c a t ec h e c k i n g ，c h i n e s ew o r d ss e g m e n t a t i o n 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 年月日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年 月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 年月日 第一章绪论 第一章绪论 第一节研究背景和意义 随着社会信息化和网络技术的发展，知识产权保护、学术研究、信息检索 和各种申报与统计分析等应用日渐重要，其数据库信息规模也在不断增长，如 何校验这类应用系统数据库信息是否存在重复是其中的关键问题之一。本文以 学科和论文类信息采集与评估应用系统为背景，重点研究以中文分词技术为基 础的查重方法和技术，提出一种信息校验系统结构，在此基础上通过实验研究 查重技术及其应用问题，实现了以词法和语法信息为辅助信息的文本重复与相 似的查重算法，并对算法的性能进行了分析研究。 查重( d u p l i c a t ed e t e c t i o n ) ，又称为副本检测，也称为剽窃检测( p l a g i a r i s m d e t e c t i o n ) 或者复制检测( c o p yd e t e c t i o n ) ，本文统称为查重技术。 1 1 1 课题的提出 在社会信息化飞速发展的今天，教育信息化成为全社会关注的热点。自2 0 世纪9 0 年代以来，随着网络技术的飞速发展，i n t e r n e t 快速发展，推动了面向社 会的信息改革。所谓信息化是指将信息作为构成某一系统、某一领域的基本要 素，并对该系统、该领域中信息的生成、分析、处理、传递和利用所进行的有 意义活动的总称。 教育信息化包括两层含义【1 】：一是培养适应于信息化社会需要的人才，二是 把信息技术手段有效应用于教育科研和教育管理。随着教育信息化的日渐复杂， 如何通过对迅速膨胀的信息进行有效管理来提高教育信息质量面临重大难题。 而要保证能有效而又有力度的对信息进行管理，这就要求能对信息的准确性， 关联性给予比较精确的定位，快速检测和排除重复的、冗余的知识信息。 在此背景下，本文提出了一种信息校验系统结构，研究以中文分词技术为 基础的查重方法和技术，对各省市，各地区采集上来的学科类和论文类信息进 行处理，实现了以词法和语法信息为辅助信息的文本重复与相似的查重算法， 并对算法的性能进行分析研究。 第一章绪论 1 1 2 研究意义 在教育信息化中，数据库中存储的信息量比较大，单纯靠人工处理，不仅 耗费人力资源，而且时效性比较差。要在大规模数据库中进行查重，不是一件 简单的工作，其时空复杂度非常高，而且一个人对信息的拷贝和抄袭并不是简 单的拷贝，会做相应的修改，比如调换词序、用同义词，造成文本之间近似或 相似，而不是完全相同，所以在这种情况下，简单的字符串匹配算法难以发现 文档之间的相似性。因此本文提出一种信息校验系统结构，利用查重技术，引 入检索模型中的结构信息，节省了网络资源，人力、物力和时间，提高了评估 效率。 1 2 1 研究内容 第二节主要研究内容和难点 ( 1 ) 研究一般信息校验规则，信息的校验方式方法。查重技术是属于信息 校验中的一种，本课题主要针对高维数据进行信息校验。采用高维数据模型解 决查重问题，即主要解决文本查重问题。 ( 2 ) 查重技术又被称为复制检测技术，这项技术分为两大类，一类是程序 复制检测技术，另一类是自然语言复制检测技术。本文主要研究第二类查重技 术，并和第一类研究技术进行对比。研究的主要目标是实现快速、高效的文本 查重。 ( 3 ) 研究国内外所采用的查重方法及其主要算法，进行分析和介绍查重在 不同领域中的应用和研究，对比这些算法之间的优缺点，选取适合本课题的查 重算法。本课题主要是文本查重，对远程传递到服务器的文本进行查重处理， 因此，适当快速的算法将能提高效率，提高准确性。 ( 4 ) 研究文本的预处理阶段。主要为中文分词和文本特征提取。中文分词 主要包括3 种算法：机械分词法( 基于字典、词库匹配的分词算法) ，语义分词 法( 基于词的频度统计算法) 和人工智能法( 基于知识理解的算法) 。采取不同 的分词算法将影响文本特征的提取。而特征提取对后续的查重工作将有重要影 响。 2 第一章绪论 ( 5 ) 详细研究介绍两大类查重的具体算法，并且深入研究文本查重的具体 算法，引入检索模型，将检索模型与选取的查重算法相结合。在本课题的查重 子系统中引入所选取的查重算法。 ( 6 ) 对所选取的查重算法和本课题设计的查重子系统进行建模，选取适当 数据集进行实验分析。 1 2 2 研究难点 本文研究工作主要有以下几个方面难点： 第一，中文分词的研究。在三种中文分词算法中选取最适合于本课题的算 法。恰当的过滤掉冗余信息，对于后期的特征提取是关键步骤。 第二，如何进行特征提取。对高维数据进行信息校验的建模方式直接影响 到查重的速度。所以采取什么样的方式进行特征提取也很重要。 第三，查重需要针对的问题模型。是一对多查重，还是多对多查重。针对 不同模型的查重所采取的方式将有所不同。 第四，查重算法的复杂度。采取不同的查重算法，其所需要的时间复杂度 和空间复杂度不相同，需要结合课题在这两方面进行权衡与取舍。 第三节主要内容组织结构 本文的研究重点是信息校验系统结构中的查重技术及其研究。与实际背景 相结合，在研究国内外查重技术发展趋势的基础上，设计一种信息校验系统结 构。 文中第一章主要介绍本课题的研究背景和重要意义，并阐述主要研究内容 和研究难点。 第二章，对查重技术的一个全面综述，包括此项技术的国内外研究现状， 所采取的模型、方法、定义。并且对已有的查重系统技术进行分析总结优缺点。 介绍查重常用的几种用途并给出每种用途的基本思路和策略。 第三章，介绍为了实现本课题的研究目标，需要重点研究和解决的关键技 术，包括：分词算法，特征的提取，特征加权技术。同时介绍了几种可以应用 于本系统的查重算法，并给出测试分析，最终确定信息校验系统结构中所采取 3 第一章绪论 的查重算法。 第四章，介绍整个信息校验系统结构的设计并对所选取的查重算法进行测 试与分析。 本文最后第五章，介绍和分析本信息校验系统中的不足，总结本系统设计 情况并对本系统的扩展和应用方向进行了展望。 4 第二章文本查重技术概述 第二章文本查重技术概述 第一节查重定义及分类 目前网络上的数字产品主要有文本、图像、音频和视频四种表现形式。查 重技术主要集中在文本查重上。而文本查重主要分为两类，分别是程序文本查 重和自然语言文本查重。 两者在程序开发上有很多相似之处，有的工具就能同时进行程序文本查重 和自然语言查重，例如：y a p 3 。但是程序查重和自然语言查重也有很多不相同 的地方。计算机程序都有严格的语法规则，但是自然语言中的文本变化不受形 式化语法的限制，也可以出现歧义句型，这些原因，使得自然语言查重没有程 序查重好处理，比较难一些。 关于重复的定义一直不明确。例如：重复可以被定义为在没有格式化不同 的条件下，相同的语法规则或顺序，因此重复被认为是没有差异或仅仅有格式 上的不同而内容完全相同，但这种定义局限性比较大。 2 1 1 程序查重定义 由于程序查重相对自然语言查重比较简单，所以关于程序查重的文献比文 本查重的文献也要多。关于程序语言，可以指定和定义完整的语法规则，但是 对于自然语言来说，语法规则则更加复杂，因此对自然语言的抄袭行为并没有 建立准确的判断制度。 程序重复，也叫做程序克隆，所以程序查重，也被称为克隆检测( c l o n e d e t e c t i o n ) 2 】 3 1 。程序重复包括完全重复和近似重复，目前还没有关于程序查重的 具体定义。一般关于程序重复定义如下： 程序克隆是指 4 】程序1 是按照程序2 产生出来，其中程序1 只做了小部分 的例程变化 。 程序克隆【4 】是指“软件系统中存在的相同的或相似的代码片断 。 其中第一条里面的例程变化可以指简单的变化，例如：改变程序的注释或 者更改变量的名称；也可以指复杂变化，例如：等价的改变控制结构，用f o r 代 5 第二章文本查重技术概述 替w h i l e 等变化。 这种变化可以大概分为以下六种： 更改注释。 更改数据类型。 更改标识符。 额外添加代码段和变量。 改变其中的一些结构体的布局和形式。 结合复制过来的和原来的程序语句，例如：将一些相关的代码合并成新 的数据结构等。 克隆程序现在通常是指软件系统中存在的相同或相似的代码片段，会严重 影响软件的可维护性。克隆代码检测技术致力于自动发现软件系统中的克隆现 象并协助开发者消除它们【6 】。 2 1 2 自然语言查重定义 查重( d u p l i c a t ed e t e c t i o n ) ，有人称为副本检测，又称为剽窃检测( p l a g i a r i s m d e t e c t i o n ) 或者复制检测( c o p yd e t e c t i o n ) 【j 7 1 ，在知识产权保护和信息检索中有着重 要应用。目前，查重主要集中在文本查重上，而文本查重在初期体现在程序复 制检测上，现在主要为文本复制检测即自然语言查重上。 所谓复制检测( 查重) ，就是判断一个文件的内容是否抄袭、剽窃或者复制 于另外一个或者多个文件。剽窃不仅仅意味着原封不动照办，还包括对原作的 移位变换、同义词替换以及改变说法重述等方式。从本质上讲，文本查重就是 判断两篇文本内容中是否存在雷同成分，并且给出一个数值评估，这个值也可 以称为相似度瑙j 。 判断一个文档与另一个文档是否有相似性，或者说一个文档是否是另一个 文档的抄袭比较复杂，因为存在很多种形式的抄袭和剽窃引起两篇文档重复。 比如：一个文档也许是另一篇文档的复印版本、传真版本。复制版本的文档之 间有时可以达到视觉上的相同，或者其中有些加入自己的额外的手写内容。如 果原文档是从网上获得的，则其复制的文档也许含有和原文档相同的文本内容， 只在格式方面( 例如：字体，行间距，长度等等) 做相应改变。重复的文档可 能拥有与原文档大致相同的内容，但随着编辑的过程中做出小规模的变化。 6 第二章文本查重技术概述 无论自然语言查重的定义如何，判断两篇文档是否相似，或者判断一篇文 档是否是另一篇文档的复制品，主要包含两个步骤【9 】： 从文档中提取出适当的信息，排出干扰因素；将此信息与原来存储在数据 库中的信息进行特征对比。 对于第一步骤中文档的处理，排出干扰因素，首先要分清楚干扰因素是什 么。这个问题可以分解为两个方面：文本的内容是全部重复，还是部分重复； 文本的格式是与原文本的保持一致，还是有做相应变化。可以对重复模式基本 定义为以下4 种： ( 1 ) 内容格式相同( f u l l 1 a y o u td u p l i c a t e ) ：如果两篇文档在内容和格式上完 全相同。 ( 2 ) 内容相同格式不同( f u l l c o n t e n td u p l i c a t e ) ：如果两篇文档在内容上完全 相同，但是在格式上不同。 ( 3 ) 部分内容相同且格式相同( p a r t i a l 1 a y o u td u p l i c a t e ) ：如果两篇文档有部 分重要的内容相同，并且格式相同。 ( 4 ) 部分内容相同但格式不同( p a r t i a l c o n t e n td u p l i c a t e ) ：如果两篇文档有部 分重要的内容相同，但是格式不同。 嚣靛举髭斑 嚣鼹母麓斑+ 巍霹拥闻 处篼随哮玛。 牺式翱躅 鲢妊陶晦德。 刀人 爱采$ 毛掰簿。 援裘琏掰帮， 谨络知多垂k匏落新多少 ，i 部分内辫柑嗣 椭t 群戤誉霞斑。她致瓣碲哆。 并f t 络式辑j 辫 释戳举跫晓，处链闯稚包。 戎柬琏辫声诧落翱多少， 寝宋飘掰声花嚣如多多， 1 1 1 1 i i 内释桅秘 嚣戤拳嚣晓。箍齄簿峰玛。 格箕榭褥卜 番敬夺甓甓， 矬处翔咯鸭。 援来城辩i 弗。裁鞯幻多静+ 瘦索k 辟f 声， 蓖辫搬多疹。 t 箭务内释摊嗣w 嚣戤蕾就寝，她笼瓣啼岛， 舷琏旃芄不两卜 移鼠夺蹙骁。 = 缝处蛳哮坞。 茜c 露敞擀声。张落知多夸。 瘦泉风雨声， 托籍船多少。 # t 图2 1 四种重复模式 关于4 种不同模式的重复如图2 1 所示。 上述只是基本的判断模式，但是一个文本的复制不一定只是简单的拷贝过 来内容，对格式进行一些变化，也包括对文本内容的改写。 其中一种改写是简单的用自己的语言来重新描述原文章里面的语句。这种 改写需要理解原文的意思并且用自己的风格和词语描述出来，使整篇文章能通 7 第二章文本查重技术概述 顺的表达出原来文章的含义，这种抄袭一般包括如下几种【l l 】： ( 1 ) 使用同义词：改写的一个共同的形式就是使用字典或词库里面相近的 词去替换原来文章里面的词或短语来表达同一个意思。 ( 2 ) 更改句子类型：汉语的语法格式比较复杂，用不同的方式可以表达出 相同的含义。 ( 3 ) 改变句子顺序：不改变原文的意思而颠倒原文句子的顺序。 ( 4 ) 缩减语句：添加或减少动词、名词等，将句子在原意上进行缩减。 ( 5 ) 词语词性变化。 ( 6 ) 模糊概念具体化。 通过上述可以判断两篇文档是否为相似或者抄袭。因此自然语言查重处理 主要从语法相似性和语义相似性两方面来进行度量。 第二节国内外研究发展 查重( d u p l i c a t ed e t e c t i o n ) ，这项技术从2 0 世纪7 0 年代开始研究、发展。初 期的查重技术主要是用简单的属性计数法检测程序复制，现在的程序复制检测 技术都需要综合属性计数和结构度量两方面的信息。自然语言文本检测要难于 程序复制检测技术，所以，文本查重直到2 0 世纪9 0 年代才出现。文本查重检 测有两类基本的检测方法，一类是基于字符串比较的方法，一类是基于词频统 计的方法。文本查重可以借鉴信息检索中的很多方法，在文本查重中引入结构 信息，以实现多粒度检测是提高检测精度的一个重要手段【_ 7 1 。 查重技术和信息检索技术有一定联系，他们不是针对一整篇文档的判断， 而是对每个文档的某一部分区域进行判断，而这个文档的部分区域可以看作是 针对一个文档集合的查询。很多研究者通过各种方法包括从后缀树 ( s u f f i x t r e e s ) ，s h i n g l e 技术，到向量空间计算夹角余弦等方法来达到检测的目的。 查重技术本身也可以看作是文档分类技术的一项延伸工作，所以一些研究人员 利用聚类算法来查找相似性文档。 2 2 1 程序查重研究 最早在2 0 世纪7 0 年代已经有人开始研究程序检测技术来防止大规模拷贝 8 第二章文本查重技术概述 和程序剽窃。1 9 7 6 年，o t t e n s t e i n 首次提出基于属性计数法( a t t r i b u t ec o u n t i n g ) 检 测软件剽窃的方法【8 】。但是，单纯的属性计数法不含有程序结构信息，导致错误 率增加。v e r c o 和w i s e 在1 9 9 6 年指出，对于仅用属性计数法的检测算法，增加 向量维数并不能改善错误率。改进属性计数法的措施就是加入程序的结构信息， 结合结构度量( s t r u c t u r em e t r i c s ) 来检测重复、剽窃。也有人提出用神经网络等方 法来检测程序复制。 国内对于研究程序查重技术的研究目前比较少，国外研究相对比较多，是 最近几年来国际软件维护领域的关注的重点。国外称程序查重，也叫软件抄袭 检测( s o f t w a r ep l a g i a r i s m ) ，也被叫做克隆代码检测( d e t e c t i o no fs o f t w a r e c l o n e s ) 。 此外开始于上世纪9 0 年代的工具有 1 1 】： ( 1 ) s i m ( s o f t w a r es i m i l a r i t yt e s t e r ) ：它能检测出软件系统中存在的抄袭代 码，也能在大的软件工程中检测到可能重复的代码片断。 ( 2 ) s i f t ：这个工具最先是用来在大的文件系统中找出相似文件，后来与其 他技术相结合用来探测j a v a 文件中的相似之处。 ( 3 ) d u p ：这项技术由b r e n d ab a k e r 发明用来查找软件代码之间大的相似片 断。引入了参数匹配( p - m a t c h ) ，不仅可以查找出文本上的相同之处，而且能查 找出逻辑相同但改变了变量名称的变化。d u p 主要利用后缀树( s u f f i xf l e e ) 来实 现参数匹配。 除了上述介绍的这几个工具，目前比较知名的工具有c c f i n d e r t 2 1 ，s i i n j a n 1 2 】， s i m s c a n 【1 3 】，c l o n ed o c t o r l l 4 1 等。 c c f i n d e r 为日本大阪大学( o s a k au n i v e r s i t y ) 计算机软件工程实验室研究成 的一种克隆代码自动检测工具。他们实验室研究成果还包括克隆代码重构支持 工具a r i e s 。c c f i n d e r 基于t o k e n 的比较，支持c 、c + + 、j a v a 、c o b o l 语言， 使用依赖于具体语言的词法分析器，比较容易实现多语言检测。 s i m i a n ，s i m s c a n ，c l o n ed o c t o r 为知名商业的代码检测工具，也得到了广 泛的应用。s i m i a n 支持j a v a 、c 、c 、c + + 、c o b o l 、r u b y 、j s p 、a s p 、h t m l 、 x m l 、v i s u a lb a s i c 语法源代码，甚至支持纯文本文件。 现代软件的发展需要提高程序的可复用性，消除重复代码。检测代码克隆 有助于重构代码，提高软件的质量和可维护性。因此这项技术在最近几年的国 际软件维护领域被重点关注。 9 第二章文本查重技术概述 2 2 2 自然语言查重研究 随着因特网的迅速发展，从网上粘贴复制资源变得更加容易，致使在不同 领域中电子形式的文本越来越多。由于巨大的信息含量，要判断一个文档是否 抄袭其他文档，是否和其他文档重复，是非常耗费时间的问题。 自然语言查重技术源自自然语言文本复制检测技术，自然语言复制检测技 术的出现比程序检测技术的出现晚了2 0 年。早期出现于1 9 9 3 年的s i f l 5 】工具， 使用基于字符串匹配的方法来计算文件之间的相似性。1 9 9 5 年由s t a n f o r d 大学 提出的c o p s ( c o p yp r o t e c t i o ns y s t e m ) 1 6 】系统框架为以后的自然语言复制检测技 术奠定了基础。后来又有人借鉴了信息检索中的向量空间模型提出了c o p s 系 统的改进版s c a m ( s t a n f o r dc o p ya n a l y s i sm e t h o d ) 。同期，贝尔实验室的h e i n t z e 开发了k o a l a 1 7 】系统用于剽窃检测。早先提出的完全用于查重的两种算法是： d s c 算法【1 8 】( d i g i t a ls y n t a c t i cc l u s t e r i n g ) 和d s c - s s 算法( d s c ss u p e rs h i n g l e ) 。 d s c 和d s c s s 还有一个明显的缺点是：处理较小文档的效果很差。在这两个 算法的基础上开发了一个新的系统：i - m a t c h 。 c o p s ，k o a l a 和d s c ，采用s h i n g l i n g 1 9 】技术，把w 个连续的单词称为一 个s h i n g l e ，然后从文档中选取一定量的w 长的s h i n g l e 构成子集合，并且比较2 篇文档之间重叠的s h i n g l e 的数目，就可以计算出2 篇文档的重叠度，不用比较 整篇文档。 香港理工大学的s i 等人建立的c h e c k 原型采用统计关键词的方法来度量 文本相似性，首次把文档结构信息引入到文本相似性度量中。到了2 0 0 0 年， m o n o s t o r i 等人建立了m d r ( m a t c hd e t e c tr e v e a l ) 【2 0 】原型，用后缀树( s u f f i xt r e e ) 来搜寻字符串之间的最大子串。 现在也有很多在线服务和工具来完成这一功能。3 种在线检测服务为： 1 ) p l a g i a r i s m o r g 2 1 】 2 ) i n t e g r i g u a r d 2 2 】 3 ) e v e 2 2 3 】 目前，国内的相关研究中，哈尔滨工业大学信息检索实验室提出了用特征 码的查重方法研究。清华大学也研究了类似的方法：采用“自然语句分隔标志 将文本切成若干“语句 ，再从每个语句中提取若干字符和汉字作为特征提取码， 然后按照“各个语句在文本里面的顺序连接形成特征串。还有研究根据长度 1 0 第二章文本查重技术概述 与文本长度的比值来判断文本内容是否重复的l c s 算法，即计算最长的公共子 序列，但是算法的时间复杂度和空间复杂度较高【引。 第三节查重方法介绍 关于文本查重的定义一直很不明确，比如可以定义查重为具有相同语法规 则的单词文本序列，不包含格式上的不同。即不考虑格式因素内容完全相同的。 这种狭义的查重的实现的可以简单的利用计算哈希值，为每一个文档计算一个 唯一的哈希值。然后在数据库或者所有哈希值中为每个文档查找相似的哈希值。 几种常用的哈希函数为m d 2 ，m d 5 或者s h a 。使用这三个哈希函数的原因在于 他们可以应用于任何格式、长度的文档，方便计算，而且碰撞概率很小。 这种方法虽然快而且易于实现但是很不稳定。文本上格式的稍微变动，词 语的顺序变化，或者是内容上的一点变化都会导致不同的哈希值。所以本文要 考虑的是从文档的相似性入手进行查重。 由于不能很明确的规定在哪种程度上一个文本是另一个文本的重复，研究 人员研究了几种方法用来决定两个文档之间是否相似。其中比较常用的两种方 式如下： ， 相似比值法( r e s e m b l a n c e ) 【1 8 】。如公式( 2 1 ) 所示。如果两篇文档之间含有大 致相同的语义内容，则不管他们是否在语法上相匹配，认为它们为重复文档。 r e s e m b a l a n c e ( d j ，q ) = ( 2 1 ) 计算两个文档之间相似的特征值与两个文档共同特征之间的比值。这种方 法可以判断两个文档之间的模糊相似性。用这种方式需要考虑2 个问题： 1 ) 如何设置极限t ，所有比值超过t 的认为是重复文档。 2 ) 效率优化问题，大批量的文本查重采取这种方法效率会很低。 余弦角( c o s i n e ) 法2 4 1 。如公式( 2 2 ) 所示。 砌峨) - 骗 q 2 ) 这种方法把每个文档用向量的形式表达，所以文档之间的相似性就由两个 向量之间的距离来表示。后来又将此公式扩展，引入词频，t f * i d f 权重等来提 高查重的精确度。其中t f ( t e r mf r e q u e n c y ) 词频，指在一篇文章里面某个词语出 第二章文本查重技术概述 现的频率，而仅仅用词语出现的频率来判断某一篇文章里面最重要的关键词， 只能找出常用字词，但是不是最重要的字词，因此也要引入i d f ( i n v e r s ed o c u m e n t f r e q u e n c y ) 倒排文档频率。d f ( d o c u m e n tf r e q u e n c y ) 表示关键词在n 篇文章里面 出现的次数，i d f ( i n v e r s ed o c u m e n tf r e q u e n c y ) 则是把d f 取倒数，因此t f 乘以 i d f ，就是除以d f 的意思。这样文章里面的每一个关键词都有一个衡量权值， 来表达这个词在某篇文章里面的重要程度。 其核心内容就是判断两篇文本内容中存在的雷同成份，并给出一个数值进 行判定。如果越接近这个数值，或超过这个数值，则说明两篇文档相似度很高， 可以认为重复，如果远小于这个数值，则这两篇文档不能算做重复。 在进行查重前，要对文本进行特征提取，根据提取特征的不同方式，可以 把查重分为两大类。 ( 1 ) 字符串比较的方法也称为基于语法( s y n t a c t i c ) 的方法：从文档中选取字 符串映射到哈希表中，最后统计每个字符串的数目或者比值，作为文本查重依 据。代表计算相似度的查重方法如上所述的公式( 2 1 ) 。代表方法：s i f , c o p s ， k o a l a ，s h i n g l i n g ，m d r 等。 ( 2 ) 基于词频统计的方法也称为基于语义( s e m a n t i c ) 的方法：此方法引白向 量空间的检索模型和信息检索技术相关。首先要统计每篇文档中各个单词的出 现次数，再根据指定规则将单词频度转化为空间特征向量，最后采取度量向量 之间的距离来计算相似度达到查重的目的。如上述公式( 2 2 ) 。代表方法：s c a m ， c h e c k ，c d s d g 等。 2 3 1 检索模型介绍 很多查重技术吸收、借鉴了信息检索中的相关技术。例如上述所说的基于 词频统计的s c a m ，c h e c k ，c d s d g 等就用到了很多信息检索中的技术。像 建立索引、查询扩展和相似度计算都是信息检索中的关键环节。本小节将介绍 信息检索模型，将信息检索中的结构信息引入查重中来。 信息检索( i r ，i n f o r m a t i o nr e t r i e v a l ) 研究如何从大量的信息资源中找到满足 用户信息需求的信息子集，涉及信息的搜集、表示、组织、存储、访问、搜索 等问题。主要分为两种检索，广义的信息检索和狭义的信息检索。 广义的信息检索，从被检索的信息形式来看，包括文本检索、图像检索、 1 2 第二章文本查重技术概述 音频视频检索等；从被检索的信息状态看，主要包括信息是静态的和信息是动 态的两种。信息静态指短期内被检索的信息全集不会发生变化或者变化很少， 而用户的查询是随机不确定的。信息动态是指用户查询是确定的，或者短时间 内用户信息需求不会有大的变化，即一般所说的信息过滤( i n f o r m a t i o nf i l t e r i n g ) 或信息推送( i n f o r m a t i o nr o u t i n g ) 。 狭义的信息检索，指的是文本检索或文档检索，研究如何从相对稳定的文 本数据集中检索出与用户查询相关的文本，并以相关度从高到低的顺序将检索 结果返回给用户。其中用户提交的查询通常可以为关键词或是自然语言描述的 句子。检索的数据源为文档集，其中的每一条记录称为文档，通常为非结构化 或半结构化的自由文档；检索的任务就是从该文档集中找出若干篇与用户查询 相关的文档，并按照相关度从高到低的顺序返回给用户。 从检索模型的狭义的概念上可以看出，查重技术可以借鉴信息检索中的很 多技术，当检索结果中的某篇文档与给定用户查询的文档越相近，说明与给定 查询文档重复的几率越大。首先介绍几个概念【2 5 1 。 文档( d o c u m e n t ) 是检索系统的基本检索对象或检索粒度，通常是由自然语 言所描述的非结构化的自由文本或半结构化的文本。 文档集( c o l l e c t i o n ) 指一定数目文档的集合，也称为数据集。 查询( q u e r y ) 是对用户信息需求的一种描述，是用户信息需求的一种外在表 现形式，有时也称为查询表达式。 查询集( t o p i c s ) ，指的是一定数目的查询的集合。在查重研究中，查询集可 以看成是很多文档的集合，查重可以看作是小部门文档集合对整体文档集之间 的查重。 相关性( r e l e v a n c e 或a b o u t n e s s ) 指的是针对用户提交的查询从文档集中检 出的文档与查询之间的一种匹配关系。对于给定的查询，若某文档与该查询具 有相关性，则称该文档为该查询的相关文档( r e l e v a n td o c u m e n t ) 。相关性越大， 重复的可能性就越大。很多查重算法利用相关性来进行查重。 下面简要介绍几个传统的检索模型，分别是布尔模型，向量空间模型，概 率模型，语言模型。其中查重算法主要利用中间两种模型。本文只简单介绍下 四类模型。 1 3 第二章文本查重技术概述 2 3 1 1 布尔模型 早期的布尔模型是一种建立在集合论和布尔代数上的比较简单的检索模 型，称为经典布尔模型( c l a s s i c a lb o o l e a nm o d e l ) 。在经典布尔模型中，文档被 表示成词语的集合。每个词语在每篇文档中只有两个值：1 和o 。“1 表示该词 在此文档中出现。“0 ”表示该词未出现在该文档中。 对于布尔模型，索引检索词的权重值为二元值，既w “ o ，1 ，查询条件q 为布尔表达式。假定q d n f 是q 的析取范式，并_ rq 。是g 耐的任一合取分量，则文 档d ，与查询条件q 的相似性计算为： r li f j 瓦i ( 云石) 人( v 毛，g ，( 乃) = g ，( 云) ) s i m ( d ，g ) = ( 2 3 ) 、0o t h e r w i s e 其中忽为索引库中的第i 个检索词，索引库中的检索词全集为 k = 玩，也一矗) 。心，文档乃中索引检索词岛的权重值。d j = ( 白也，毛，) 是文 档d ，的索引词向量。蜃函数返回在t 维检索词空间中索引检索词k i 的权重值，即 g , ( d j ) = w ，。 当s i m ( d ，g ) = 1 则布尔模型判定文档d ，与查询条件相关，为0 则为不相关。 经典布尔模型由于没有提供词项的权重信息，而且查询表达式中的不同查询重 要性不同，这些信息都无法体现在模型中，这是经典布尔模型的缺点。而文档 的相关性计算结果是二值的，所以不能对检索出的文档进行一个排名，不能得 知谁更贴近原查询信息。 扩展布尔模型，在该模型中，文档和查询的相关度不是0 和1 ，而是区间 o ， 1 】中的一个实数。扩展布尔模型的主要三种模型有m m m 模型，p a t i c e 模型和 p 范数模型。其中p 范数模型要好于前两者模型。 p 范数模型中，假设用户查询由n 个不同的编，g ：，g 。个关键词组成， 其对应的权重分别为。，：，。设定查询g 为1 1 个词的“a n d 运算，查 询q 2 是n 个词的“o r ”运算，则q 和q 2 与该文档的相关状态值为： r s 。蚴，小i t 芝竺型 ， i = 1 1 4 ( 2 4 ) 第二章文本查重技术概述 r s v o 露( d ，q 2 ) = i 旦_ - 一 l ( 屹p p ) j p ( 2 5 ) 参数p 是可调节参数，不同的取值表示不同的形式。当p 取时，p 范数模 型退化到经典的布尔模型；当p 等于1 时，这两个函数变成同一种形式，与向 量空间模型的权重计算公式较为相似。参数p 的可调节性使得扩展布尔模型相 比经典布尔模型有相当好的灵活性，但是在p 值的选取上增加了扩展布尔模型 的难度。 2 - 3 1 2 向量空间模型 把文本的信息表示成权重信息的词项向量的这种思想正是向量空间模型 ( v s m ， v e c t o rs p a c em o d e l ) t 2 4 1 。这种模型目前在检索领域应用广泛，并被其他 领域也广为引用作为基础模型，比如查重算法中很多都是在向量空间模型的基 础上进行研究。 、 在向量空间模型中，每一篇文本都分别表示成高维向量的形式，在此向量 中，每一维都是文档中相应的词项权重的表示。向量空间模型中把文档和查询 之间的相似度值( r s v ，r e l e v a n c es t a t u sv a l u e ) 与它们之间的相似度联系起来。在 检索中，如果一篇文档和用户的查询越相似，则认为此文档与用户的查询越相 关。在查重技术中，如果一篇文档和用户所给出的文档越相似，则认为两篇文 档之间的重复度越高。 待检索的文档集为c ，设词典为v = ，乞 ，该词典构造成为一个l 维的空间，每个字典里面的词项是空间中的一维。文档中的各个