（管理科学与工程专业论文）基于匹配统计算法的文本复制检测研究.pdf

中国科学技术大学硕士学位论文摘要 摘要 随着互联网技术的飞速发展和网络数据库资源的日益丰富，海量的信息以及 巨大的搜索功能，让论文抄袭变得轻而易举。针对抄袭行为越来越严重这一现象， 反论文抄袭的研究应运而生。文本复制检测将让那些有抄袭企图者不敢贸然付诸 行动文本复制检测系统能够为用户识别检测对象是否为复制文本提供决策支 持。 本文研究了文本复制检测系统的基本原理及主要的检测策略和检测算法 在复制检测策略研究方面，主要分析了哈希断点分块检测策略，构建了搜索引擎 模块，对不同长度的文本块计算哈希值，进行对比实验，以确定文本块边界。在 复制检测算法研究方面，着重分析了基于字符串比较的匹配统计算法，特别是后 缀树和后缀向量匹配统计算法。针对后缀树算法存在的“内存瓶颈”问题，本文 提出了一种基于紧凑后缀向量表示的匹配统计算法，采用动态节点存储与初始字 符串相关的节点信息，直接从字符串读取边标记。紧凑后缀向量匹配统计算法不 仅节约存储空间，而且消除了后缀树匹配统计算法中的一些冗余比较。 最后，构建了文本复制检测原型系统，对匹配引擎模块和搜索引擎模块进行 测试，设计仿真实验比较了紧凑后缀向量匹配统计算法与后缀树匹配统计算法。 实验结果表明与已有的后缀树复制检测算法相比，紧凑后缀向量匹配统计算法在 测试文档集上表现出较好的运行速度和空间效率。 关键词：复制检测，后缀树，后缀向量，匹配统计，分块 中国科学技术大学硕士学位论文基于匹配统计算法的文本复制检测研究 a b s t r a c t w e b t e c h n o l o g i c a la d v a n c e sh a v er e n d e r e dr e a d i l ya c c e s s i b l er e s o u “；e sm a k i n gt h e t a s ko f c o p y i n gr e s e a r c hw o r ko f o t h e r se a s i e r d i f f e r e n t i a t i n gb 神w e e np l a g i a r i s ma n d o r i g m a lw o r kr e q u i r e sal a r g ea m o u n to f t i m ea n dl a b o ri fi n s p e c t e dm a n u a l l y s ow e n e e daq u a n t i t a t i v ee v a l u a t i o nm e t h o dt of i n do u tw h e t h e rp l a g i a r i s mi sh a p p e n e do r n o t c o p yd e t e c t i o ns y s t e mc o u l dp r o v i d ed e c i s i o ns u p p o r to ni d e n t i f y i n gp l a g i a d s m s m a t c hs t a t i s t i c sa n a l y s i sb a s e do ns t r i n gc o m p a r i s o na n dh a s hc h u n ks t r a t e g yw e r e a n a l y z e di nt h i sp a p e r , w h i l ep o p u l a rd e t e c t i o nt e c h n i q u e sa n da l g o r i t h m sw e l ea l s o d i s c u s s e d 。s e a r c hm o d u l ew a sd e v e l o p e db a s e do nh a s hc h u n ks t r a t e g y w em a i n l y f o c u so ns u f f i xt r e ea n ds u 任，v e c t o rr e p r e s e n t a t i o n s s u f f i xt r e eh a sb e e na p p l i e di n s t r i n gm a t c ho fn a t u r a ll a n g u a g ep 南e e s s i n g t h ee d g ei n d e x e se o n s u m 旧t o om u c h s p a c ea st e x ts i z ea n dc o n t e n ti n c r e a s i n g a sar e s u l tt h es y s t e mp e r f o r m a n c ed e c l i n e - a c u t e l y w ep r o p o s em a t c hs t a t i s t i c sa l g o r i t h mb a s e do bc o m p r e s s e ds u f f i xv e c t o r c o m p r e s s e d 鲫i 伍xv e c t o rr e p r e s e n t a t i o ns t o r e sn o d ei n f o r m a t i o nr e l a t e d t oo r i g i n s 硒n ga n dr e a d se d g es i g nd i r e c t l yf r o ms t r i n g i tn o to n l ys a v e ss p a c e b u ta l s ow i p e s o f fs o m er e d u n d a n c yc o m p a r i s o n sw h i c ho c c u ri ns u f f i xt r e em a t c hs t a t i s t i c s a l g o r i t h m a p r o t o t y p es y s t e mw a sd e v e l o p e dt ot e s tt h ea p p l i c a b i l i t yo ft h em o d e l s e a r c h m o d u l ea n dm a t c hm o d u l ew e r eb u i l tt ot e s ts u 伍xv e c t o rm a t c hs t a t i s t i c sa l g o r i t h m t h ee x p e r i m e n t ss h o wi t sc o m p a r i s o nw i t hs u 位xt r e em a t c hs t a t i s t i c sa l g o r i t h m e x p e r i m e n t a lr e s u l t sr e v e a lt h a tt h ea l g o r i t h mw ep r o p o s e di sm o r eq u a l i f i e dt h a n 舷t r e em a t c hs t a t i s t i c sa l g o r i t h ma sf a ra ss p a c er e q u i r e m e n ta n d 川皿i n gt i m e c o n c e r n e d k e y w o r d s ：c o p yd e t e c t i o n ；s u f f i xu - e e ；s t l 伍a xv 爿炳f ；m a t c hs t a t i s t i c s ；c h u n k n 中国科学技术大学硕士学位论文 基予匹配统计算法的文本复制检酒研究 图3 。l 后缀树图例 图序 2 2 图3 2 稀疏后缀树中的后缀链接2 5 图4 1 字符串s 的后缀向量表示2 8 图4 2 一般后缀向量表示中的框结构3 0 图4 3 紧凑后缀向量表示3 1 图4 4 ( a ) 紧凑后缀向量构建阶段l 一3 5 图4 4 0 叻紧凑后缀向量构建阶段2 3 6 图4 4 ( c ) 紧凑后缀向量构建阶段3 。 图4 4 ( j ) ) 紧凑后缀向量构建阶段4 3 7 图4 4 ( e ) 紧凑后缀向量构建阶段5 3 7 图4 4 ( f ) 紧凑后缀向量构建阶段6 3 8 图4 。4 ( g ) 紧凑后缀向量构建阶段7 3 9 图4 4 c h ) 紧凑后缀向量构建阶段8 - 1 2 3 9 图4 4 ( i ) 紧凑后缀向量构建阶段1 3 4 0 图4 4 ( j ) 紧凑后缀向量构建阶段1 4 4 1 图5 1 文本复制检测原型系统体系结构4 4 闰5 2 文本范式转化流程4 5 图5 3 转化后的a s c i i 文档4 6 图5 4 文本相似度4 s 图5 5 紧凑后缀向量匹配统计算法的运行时间5 0 图5 6 后缀树匹配统谤算法的运行对闻 图5 7 查准率和查全率。5 l 图5 8 复制检测误差5 l v i 中国科学技术大学硕士学位论文图序和表序 表3 1 表3 2 表4 1 表5 1 表5 2 表5 3 表序 采用单个后缀树的匹配统计值2 3 采用多个后缀树的匹配统计值2 3 后缀向量匹配统计表 判真为假( 错误肯定) 4 7 紧凑后缀向量构建算法的运行时问4 8 后缀向量与后缀树匹配统计算法检测性能比较分析4 9 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究 工作所取得的成果。除已特别加以标注和致谢的地方外，论文中 不包含任何他人已经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， 即：学校有权按有关规定向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：刻蛰选 扫门年6r8b 中国科擘技术大学硬士学位论文 第一章绪论 1 1 研究背景与意义 第一章绪论 近年来，随着互联网技术的飞速发展和网络数据库资源的日益丰富，信息 的获取越来越便利。学术研究者和科研人员可以通过互联网方便快速地检索各种 网络学术信息资源和商用数据库，如w e bo f s c i e n c e 、e i 、i n s p e c 、c a 、b p 等 二次文献检索数据库和s c i e n c e 、e l s e v e rs d o s 、k l u w e ro n l i n e 等全文 电子期刊。然而互联网就像是一把利弊参半的双刃剑，一方面，它为学者们从事 科研活动提供了方便快捷的参考信息资源；另一方面，由于电子文档便于编辑处 理的特性，剽窃者只要简单地执行复制粘贴等操作就可以轻而易举将他人的研究 成果据为已有，因而它也助长了抄袭剽窃等不良学术风气。 相比于传统的纸质文档而言，电子文档更容易被抄袭和非法复制，它们的 版权更容易受到侵犯。网络的诞生，海量的信息以及巨大的搜索功能，让论文抄 袭变得容易。抄袭剽窃之风在学术界愈演愈烈几乎是不争的事实，甚至蔓延到一 些学生的作业和论文写作。国外一项对2 3 所学院的调查研究表明t i ：互联网剽 窃在学生当中正日益增加。被调查的3 8 的大学生说他们在过去的一年里，已经 做了一次或多次涉及互联网的“复制粘贴”剽窃，即从网上意释或照搬复制别 人文章的几句话或数段而不引用标明其来源出处。调查中几乎一半的学生说他们 认为这样的行为是微不足道的或根本不算欺骗。在3 年前，一次类似但小得多的 调查中，只有1 0 的学生承认有如此的欺骗行为。文本复制检测面i 函的问题目益 严峻，随着互联网的发展，信息量大大增加，客观上方便了少数人为了某些利益 肆意抄袭剽窃他人的劳动成果，这严重打击了广大科研人员的工作积极性，造成 了恶劣的影响。同时知识产权若得不到良好的保护，必然会有损科学技术的发展。 因此研究文本复制检测技术的意义十分重大。 针对抄袭行为越来越严重这一现象，反论文抄袭的研究应运而生。文本复制 检测将让那些有抄袭企图者不敢贸然付诸行动牛津字典对抄袭的定义是：大量 使用他人的已公开发表的劳动成果来创作新的作品，并且没有给出恰当的引用和 参考标识1 2 1 。抄袭认定的标准是按照著作权法中规定的，撰写的文章有2 5 l 中国辩学技末大学硕士学位论文基于匹配统计算法的文本复镪检涮研究 的内容是别人的，而不标明引用，就已构成抄袭。抄袭检测是判断某论文是否是 另一已发表论文的变体或复制版本，以确立嫌疑个体与源文件之间的相似关联关 系。相似性度量技术主要有两种：基于文本相似性和基于写作风格分析【3 】。本文 的研究对象是检测自然语言文本复制，即判定文本之间是否存在一个编辑序列， 能将文本a 变换为文本b 。 所谓复制检测1 4 i ，就是判断一个文件的内容是否抄袭、剽窃或者复制于另外 一个或者多个文件。复制检测又称剽窃检测，也有人称为副本检测，不但是实施 知识产权保护的一种重要手段，也是提高信息检索效率的一种方式。剽窃不仅仅 意味着原封不动地照搬，还包括对原作的移位变换、同义词替换以及改变说法重 述等方式。 目前保护电子文档的知识产权主要有两种保护措施，一种是“阻止”法， 另一种是“检测”法( 4 j 。“阻止”法就是在复制发生前阻止，这就必须让复制电 子文本变得足够难，通常使用加密、水印、特殊载体等方法，使受保护内容难以 被复制。例如，i e e e 通过光盘发行文集，超星电子图书上的文章需采用专用软 件才能阅读。文献【5 】提出的“主动文档”需要使用专用程序；贝尔实验室提出 了“水印”技术，使用加密的单词空格或者图像，可以鉴定文档授权用户身份i 明； c h o u d h u r ，n 等人提出一个采用非对称加密体系的文档分布系统结构，在此体系 中一个公钥被用来加密文档，在客户端加密文档由一个私钥解密。但是，上述方 法都有可能被破解，而且也缺乏技术手段来防止授权用户使用光学识别( o c r ) 等 办法非法复制、扩散。所以，“阻止”法不能完全解决知识产权保护问题。 数字水印是应用于电子出版物的一种复制检测方法。数字水印并不试图阻 止文档的分布，而是想要检测非法的复制文件其中的一个关键问题是如何识别 文档的初始发布者。即一旦发现非法复件，就追查谁购买了原版文档并将它提供 给其它使用者。数字水印可以被认为是复制检测机制的一个补充工具。 用“检测”法保护知识产权的思路是这样的：它并不关心文件是如何被复制 的，而是首先判断出当前的文件中是否含有复常8 或者剽窃的内容，如果发现了非 法复制或者剽窃行为，那么再对复制源或者剽窃者采取相关措施。“检测”法的 核心就是复制检测技术。显然，“阻止”法和“检测”法不是相互对立的关系， 而应该相互补充、完善才能更好地保护知识产权。 2 中国科学技束大学硕士学位论文纂一章绪论 1 2 文本复制检测技术的研究现状 随着计算机的普及和网络技术的蓬勃发展，论文剽窃已经成为学术界越来越 严重的一个问题。在网络技术蓬勃发展的今天，剽窃别人的研究成果轻而易举， 只要简单的c t r l + c ，c t r l + v 即可完成。与此同时，剽窃行为并不容易被发现。因 此，人们想要使发现剽窃事件的过程自动化，让计算机来完成这一过程。 根据复制检测对象的特点，目前存在的复制检测系统可以大致分为两类：一 类是以计算机程序为主要检测对象的程序复制检测系统，这种检测系统主要采用 对数字正文进行基于语句的穷举比较，以确定是否有复制行为发生主要是用于 防止源程序剽窃和软件重用。另一类检测系统的检测对象主要是文本，这种检测 系统主要在自然语言文本中使用，帮助用户鉴别检测对象是否是复制文本，这些 文本包括了报刊文章、新闻、学术论文等自然语言文本，这种检测系统就是通常 所说的自然语言文本复制检测系统，简称文本复制检测系统。这是本文研究的重 点。 旱在2 0 世纪7 0 年代初就有学者开始研究防止大规模复制计算机程序的技 术。o t t e n s t e i n t 8 在1 9 7 6 年首次提出了基于属性计数法( a t t r i b u t ec o u n t i n g ) 检测软件 剽窃的方法。单纯的属性计数法因为抛弃了太多的程序结构信息，致使误判率太 高，这是其致命缺陷。v e r c o 和w i s e t g 在1 9 7 6 年指出，对于仅仅使用属性计数法 的检测算法，增加向量维数并不能使检测误判率获得改善；引入程序的结构信息 改进属性计数法，结合结构度量( s t r u c t u r em e t r i c s ) 可以更有效地检测复制现象。 现在主流的程序复制检测技术一般都是综合采用属性计数法和程序结构度量法 【l o r 。 文本复制检测技术的出现比程序复制检测技术晚了将近2 0 年。1 9 9 4 年， a r i z o n a 大学的m a n b e r 提出了一个甜工具【1 3 1 ，用于在大规模文件系统中寻找 内容相似的文件。1 9 9 5 年，s t a n f o r d 大学的b r i n 和g a r c i a - m o l i n a 等人在“数字 图书馆”工程中首次提出了文本复制检涮机翩c o p s ( c o p yp r o t e c t i o ns y s t e m ) 系统 与相应算法【1 t “。c o p s t l 埘1 系统框架为以后的自然语言文本复制检测系统奠定了 框架基础。随后，g a r c i a - m o l i n a 和s h i v a k u m a r 等人提出了依托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 ) 原型系统f i 叼。s c a m 借鉴了信息检 索技术中的向量空间模型( v e c t o rs p a c em o d e l ) ，使用基于词频统计的方法来度量 3 中国科学技术大学硕士学位论文基于匹配统计算法的文本复制检测研究 文本相似性。后来g a r c i a - m o l i n a 和s h i v a k u m a r 等人还在s c a m 的基础上提出了 d s c a m 模型i i 7 , l q ，把检测范围从单个注册数据库扩展到分布式数据库上以及在 网络上检测文本复制。 贝尔实验室的h e i n t z e 开发了k o a l a 系统用于抄袭检测。k o a l a 【1 9 1 系统 采用与s i f 基本相同的方法，与之类似的方法还有b r o d e r 等人提出的s h s n g n g 方法删。s i 和l e o n g 等人建立的c h e c k 原型采用统计关键词的方法来度量文本 相似性口”，c h e c k 口1 1 系统将文档结构信息引入到文本相似性测度中。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 ) 原型吲。m d r 采用后缀树存储结 构来搜寻字符串之间的最大子串。2 0 0 1 年，m o n o s t o r i l ”! 等人在后缀树表示方法 的基础上进行改进，提出了后缀树的变形结构，用后缀向量表示方法作为存储结 构 当前，主要的文本复制检测系统有 1 3 , 1 5 , 1 6 , 1 7 1 5 , 1 ”唯1 j ：t u r n i t i n c o m ，e v e ， h t e g r i g u a r d ，p a p e r b i n , c o p y c a t c h ，w o r d c h e c k 和g i a r 等商用系统；y e ta n o t h e r p l a g u e ( y a p ) ，s c a m , d s c a m , c h e c k , c d s d g ，k o a l a ，s h i n g l n g ，c o p s ， m d r 和j p l a g 等原型检测系统。 1 3 论文的研究对象和所做工作 本文的研究对象是自然语言文本复制检测，这里特别指在互联网环境下， 以英文电子文档为主要对象的自然语言文本复制检测系统及检测算法。 由于基于后缀树的匹配统计算法耗费的存储空间较大，算法的运行速度随 之变慢，复制检测性能不够理想。针对这种情况，本文在后缀树表示方法上进行 改进，提出一种基于紧凑后缀向量表示方法的复制检测算法。 在本文中主要做了以下工作： ( 1 ) 分析介绍了已有的文本复制检测技术和算法 对现有复制检测系统中所采用的技术和各种检测算法分别作了详细的分析， 介绍各自的原理，分析其优点和缺点，并指出其各自不同的适用范围。 ( 2 ) 对基于m d 5 算法的哈希断点分块法的研究 分析了复制检测的文本块分块策略，采用基于m d 5 算法的哈希断点分块法 4 串冒科学技木大学硬士学位论文第一章绪论 构建了原型系统中的搜索引擎模块。 ( 3 ) 对基于后缀树和后缀向量的匹配统计算法的研究 在分析后缀树表示和后缀向量表示的实现步骤以及相应技术方法的基础上， 提出了紧凑后缀向量表示方法，设计和分析了复制检测系统中匹配弓 擎模块的构 建和工作方法。 ( 4 ) 构建了基于匹配统计算法的文本复制检测原型系统 构建了文本复制检测系统，检验最终的复制检测结果。实验表明，与已有的 后缀树复制检测算法相比，后缀向量匹配统计算法在测试文档集上表现出较好的 运行速度和空间效率。 1 4 论文的结构安排 本文在绪论部分介绍文本复制检测系统及复制检测技术算法的研究背景和 意义，对文本复制检测系统及复制检测技术作了一个概貌性的描述，在讲述了文 本复制检测系统的研究现状后，介绍本文所做的主要工作。 第二章描述复制检测系统的概念、框架结构。分析了文本块复制检测策略 和技术，并对当前文本复制检测系统中采用的后缀树和后缀向量匹配统计算法进 行文献回顾，比较现有各算法的原理、优缺点及其适用范围等 第三章研究自然语言文本复制检测系统广泛采用的后缀树匹配统计方法， 分析了其构建过程，指出其存在的问题和不足，为下一章引入后缀向量表示方法 作了镳垫。 第四章在对现有后缀树和后缀向量匹配统计方法研究的基础上，提出了基 于紧凑后缀向量的匹配统计方法，详细介绍了该算法的原理和具体步骤。 第五章构建了复制检测原型系统，其中匹配引擎模块基于后缀向量匹配统 计算法构建，搜索引擎模块采用哈希断点分块法构建。对紧凑后缀向量匹配统计 算法进行了实验设计和结果分析。 第六章为本文作最后的总结，提出将来的工作和展望。 5 中国科学技术大学硕士学位论文 基于匹配统计算法的文本复制检测研究 1 5 本章小结 本章介绍了文本复制检测系统研究的背景及目前复制检测的研究进展等， 强调了本文研究的意义。提出了本文研究的对象和所做的工作，并对论文的结构 安排进行了简要的说明。 6 中国科学技术大学硕士学位论文 第二章文本复制检涌系统及箕相关技术 第二章文本复制检测系统及其相关技术 文本复制检测系统是针对电子文档检 狈j 识别复制文本的应用系统。本章将介 绍文本复制检测系统的一些基本概念、体系结构，应用流程等，以及目前主流的 文本复制检测系统中所采用的相关检测技术和算法。 2 1 文本复制检测系统概述 1 文本复制检测系统的概念 文本复制检测系统( c o p yd e t e c t i o ns y s t e m s ) 的正式定义由g a r c i a - m o l i n a 和s h i v a k u i n a r 等人在1 9 9 6 年给出：“文本复制检测系统是以度量文本相似性的 方式来检测复制文本，并为用户提供相关建议，帮助用户决定被检测文本是否为 复制文本，通过自动化模拟人工完成检测过程的系统”0 0 3 文本复制检测系统的检测对象主要是自然语言文本，其为用户鉴别检测对象 是否为复制文本提供决策支持。 2 文本复制检测系统的作用 文本复制检测系统的工作可以概括为；应用相似性分析和匹配统计算法为用 户提供个性化的文本复制检测服务。文本复制检测系统最主要的功能在于它能够 抽取待测文本，通过分析待测文本和候选文本的相似关系，做出决策，以此为用 户提供参考性建议。每当用户提供一篇待测文本后，文本复制检狠8 系统就会按照 关键字抽取挖掘与当前待测文本相似，可能为复制文本的候选文本，并且根据一 定的比较规则来比较其相似度，依据比较结果给出相似度，为用户判断文本是否 为复制文本提供决策支持。 3 文本复制检测系统的构成 文本复制检测系统主要由以下三个模块组成：文本转化模块、搜索引擎模块、 匹配引擎模块。 ( 1 ) 文本转化模块 文本转化模块主要负责将文本转化成普通形式，并确保微小的改动不会阻止 7 中国科学技术大学硕士学位论文基于匹配统计算法的文本复制检测研究 复制检测。首先，文本转化必须将不同文件格式的文档转化成a s c i i 纯文本。文 本转化模块能够将p d f , p s , i v l sw o r dd o e 文档转化成a s c i i 纯文本。格式化信息 将被从文本中移除，转化过程之后的处理结果是文档以范式表示。转化所得的范 式是明确统一的，两个同源的文档应该拥有相同的范式。 ( 2 ) 搜索引擎模块 搜索引擎模块作为一个预过滤器运作，其只将与提交文档潜在相似的文档提 交给匹配引擎模块，以供匹配引擎模块进行下一轮的精确匹配比较。搜索引擎模 块采用文本分块策略，提取文本的信息指纹。 ( 3 ) 匹配引擎模块 匹配引擎模块是整个文本复制检测系统的核心部分，它直接决定着复制检测 系统的性能优劣。匹配引擎模块以复制检测算法为技术支撑，采用基于后缀树和 后缀向量的匹配统计算法识别文档间的复制现象。具体检测技术和检测算法将在 第三章和第四章中详述。 4 文本复制检测系统的整体框架及应用流程 文本复制检测系统的完整框架主要由基础文档集、文本数据库、匹配引擎、 用户交互等构成。 ( 1 ) 基础文档集：操作文档集中存储与用户操作密切相关的文档，包括搜索 引擎检索到的候选文档、用户手动注册的文档等。 ( 2 ) 文本数据库：用来存储规整的经过清洗和初步转化处理后的文本信息指 纹，是检测系统直接操作的数据。 ( 3 ) 匹配引擎：主要功能是接收用户请求，运行匹配统计算法，产生检测结 果。匹配引擎对内在检测算法提供了统一的运行环境，方便了检测算法 的编制，对外则提供了统一的检测服务接口。 ( 4 ) 用户交互：一方面接受用户具体的检测要求，另一方面提供给用户检测 结果。 文本复制检测系统需要完成从候选文档搜索到生成复制检测结果的完整的 系统应用流程，具体来说，包括以下几个部分： ( 1 ) 文档清洗、转换处理：从源文档中提取文本信息，使用文本转化模块把 所选择的文档加载到文本数据库中，成为范式文本。选择什么样的文本 8 中国科学技木大学硕士学位论文第二章文本复制检测系统盈其相关技术 是由具体的复制检测应用决定的，不同的疑似文档需要不同的检测机制。 ( 2 ) 模型生成：根据具体的检测应用，选择所对应的规整文本，使用合适的 模型产生检测模型，存储在模型库中。如何选择合适的模型，生成相应 的检测模型也是由具体的检测应用决定的。 ( 3 ) 检测策略配置：检测策略是检测过程的配置，其中包括检测算法和检测 模型。具体的检测功能是由匹配引擎运行对应的检测策略来实现的。复 制检测系统提供检测服务，必须有已经配置好的检测策略。配置工作主 。要是修改检测策略，采用新的检钡4 模型，然后根据具体的检测应用配置 检测策略，并请求匹配引擎启动或重载此策略。 ( 4 ) 检测结果提交：复制检测系统直接向匹配引擎提供当前候选文档的信息， 并请求用指定的检测策略产生疑似文档的候选列表。匹配引擎则根据文 本复制系统的请求运行对应的检测策略，产生合适的检测结果。 5 文本复制检i 财系统的研究问题 文本复制检测系统的研究主要围绕四个方面的问题： ( 1 ) 设计高效的文本复制检测算法 要实现被用户接受和认可的文本复制检测系统，设计准确、高效的文本复制 检测算法是文本复帛4 检测的核心问题。目前的检测技术有基于内容的检测、基于 文档结构信息的检测、基于匹配统计的检测等等。基于匹配统计的复制检测是自 然语言文本复制检测中研究和应用最多的方法 ( 2 ) 文本复制检测系统性能的评估 要让文本复制检测系统被广大用户所接受，必须对检测系统做出客观、综合 的评价，需要从准确性、健壮性、安全性等多方面进行评价。对检测系统总体性 能的评价是文本复制检测系统研究的重要组成部分，但目前大都只是采用准确 率、召回率、运行速度、空间要求等评价指标对检测算法进行评价，并没有真正 意义上的提升到对整个检测系统进行的评价，尤其缺乏从系统的安全性以及稳健 性等多方面的对检测系统综合的评价。 ( 3 ) 文本复制检测系统的应用问题 文本复制检测系统的应用十分广泛，不仅可以提高用户进行信息检索的效 率，而且可以为用户判断文本抄袭提供决策支持。目前对文本复制检测系统的应 9 中田科学技术大学硕士学位论文基于匹配统计算法的文本复制检测研究 用研究方面主要集中于电子文档的抄袭检测，还较少从更广阔的范围和更深入的 专门领域，例如从网页查重、信息过滤等角度研究讨论文本复制检测系统的应用。 2 2 文本复制检测中的文本块分块策略 文本复制检测中判断复制文本一般都基于这么一个思想：为每个文本计算出 一组信息指纹( f i n g e r p r i n t ) ，若两个文本有一定数量相同的信息指纹，则认为这 两个文本的内容重叠性很高，也就是说发生了文本复制洲。 什么是信息指纹呢? 信息指纹就是将文本中的正文信息，提取一定的信息， 可以是关键字、词、句子或者段落及其在文本中的权重等，对它进行加密，如 m d 5 加密，从而形成的一个字符串。信息指纹如同人的指纹，只要内容不相同， 信息指纹就不一样。 m d 5 是一种散列算法( h a s hf u n c t i o n ) ，又称为哈希算法、消息摘要算法，它 的作用是获取数字信息的特征( 一般称之为“信息指纹) 。一个任意长度的任意数 字信息，通过散列算法运算后，会产生一串固定长度的数字信息，称为散列值或 哈希值哈希算法具备以下的特点： 1 】两个不同数字信息产生同样的散列值的概率是非常小的( 小到现实中几 乎无法发生) ； 2 】仅从散列值无法推演出原信息； 3 】原信息的微小改变，哪怕只改变一个位，将导致散列值的很大变化。 对两篇文档进行复制检测时，比较其相似关系的基本单位通常称为文本块。 基本思路是将从文档中选取一些字符串，这些字符串被称为“指纹”。然后把指 纹映射到哈希( h a s h ) 表中，一个指纹对应一个数字。最后统计h a s h 表中相同 的指纹数目或者比率，作为文本相似度依据。计算文本相似度的决策函数有很多 种，最简单的两种如下嗍： 令f ( a ) 表示文本a 的指纹集，f 表示文本b 的指纹集，s ( a , b ) 表示文本 a 和b 的相似度，则第一种决策函数为： s ( 彳，研：! 兰! q 兰! 旦 ”7 f c a ) u ，( b ) 1 0 中国科学技术大学硕士学位论文第二章文本复制检蔫系统及其相关技术 第二种决策函数为：岛似，b ) = ，( n f ( 功 目前文本复制检测中大量采用的信息指纹抽取方法有分段签名算法和哈希断 点分块法 2 2 1信息指纹抽取方法 分段签名算法是按照一定的规则把文本切分成段，对每一段进行签名， 形成每一段的信息指纹。如果这个信息指纹里面有m 个为相同指纹时( 肌是 系统定义的阈值) ，则认为两者是复制文本。这种算法对于判断小规模的复制文 本是很好的一种算法，但是对于大规模的复制文本，其检测性能并不是很好。 哈希断点分块法叫将任意长度的二进制值映射为周定长度的较小二进制值， 这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形 式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希值都将产 生不同的值。要找到散列为同一个值的两个不同的输入，在计算上是不可能的， 所以依据文本的哈希值可以检验文本间的复制关系。 哈希表是根据设定的哈希函数h 0 c e y ) 和复制检测方法将一组关键字映象到 一个有限的地址区间上，并以关键字在地址区间中的象作为记录在表中的存储位 置，这种表称为哈希表或散列，所得存储位置称为哈希地址或散列地址。 2 2 2文本块分块粒度 对两篇文档进行复制检测时，比较处理的基本单位一般称为文本块( c h u n k ) 文本块分块粒度划分现有方法可以分为以下三类： ( 1 ) 按照单个单词这个级别的粒度进行信息指纹提取。 ( 2 ) 按照若干个连续出现的单词组合这个级别的粒度进行信息指纹提取。 其级别处于文档和单词之间，比整个文档粒度小，比单个单词粒度大。 ( 3 ) 按照整个文档这个级别的粒度进行信息指纹提取。 最极端的情况是把整个文档作为一个文本块，这是最大的粒度，但是粒度太 大带来的问题是只能检测出完全重复的复制文本，对于细微的变化无法检测，不 能识别部分复制文本。最精细的分块方法是把单个字符作为一个文本块，这是最 小的粒度。粒度越大，算法的运行速度越快；而粒度越小，算法的运行速度越慢。 1 1 中国科学技木大学硕士学位论文基于匹配统计算藏的文本复制检铡研究 因此需要平衡运行速度和匹配精确程度，找到合适的文本块粒度。 本文中在第五章中将针对不同的粒度进行文本块分块实验，探讨不同粒度的 文本块分块效果。在搜索引擎阶段，应用哈希算法进行分块策略实验；以发现部 分相似的潜在候选文档，然后针对检测到的潜在候选文档采用匹配引擎以单词级 别的细小粒度进行精确匹配比较。 2 2 3m i 5 算法 g u d i v a d a 提出的m d 5 算法嘲，定义以下几个信息指纹变量： 只表示第i - t - 文本； 该文本中权重最高的n 个关键词构成集合z - - t 。，t 2 ，厶) ，其对应的权重为 形= m ，w z 一) ； 摘要信息用d e s ( p 1 ) 表示，前一个关键词拼成的字符串用c o n ( 互) 表示，对这 一个关键词排序后形成的字符串用s o r t ( t 1 ) 表示。将以上信息指纹用m d 5 函数进 行加密。 基于关键词的m d 5 文本复制检测算法有以下5 种： l 、m d 5 ( d 甜( 只) ) 钋仍5 ( 上枷( e ) ) ，就是说摘要信息完全一样，f 和_ ，两个文 本就被认为是复制文本： 2 、m d 5 ( c o n ( t , ) ) = m d 5 ( c o n ( 乃) ) ，两个文本前h 个关键词及其权重的排序一 样，就认为是复制文本； 3 、m d 5 ( s o r t ( t , ) ) = m d 5 ( s o r t ( t , ) ) ，两个文本前”个关键词一样，权重可以不 一样，也认为是复制文本。 4 、m d 5 ( c o n ( t , ) ) = 地5 ( o 刁) ) 并且形一形的平方除以形和形的平方之 和小于某个阙值a ，则认为两者是复制文本。 5 、m d 5 ( 勋玎 ) ) = m d 5 ( 勋，r ( 乃) ) 并且彤一形的平方除以彬和的平方之 和小于某个阙值a ，则认为两者是复制文本。 1 2 中国科学技术大学硕士学位论文第- - t 文本复制检涎系统及其福关技术 m d 5 算法描述： 、 算法输入是一个字节串，每个字节是8 个b i t o 算法的执行分为以下几个步 骤： 第一步，补位： m d 5 算法先对输入的数据进行补位，使得数据的长度( 以b y t e 为单位) 对6 4 求余的结果是5 6 。即数据扩展至id 归置+ 6 4 + 5 6 个字节，k 为整数。 补位方法：补一个l ，然后补0 直到满足上述要求。相当于补一个o x 8 0 的 字节，再补值为0 的字节。这一步里总共补充的字节数为o 6 3 个。 第二步，附加数据长度： 用一个6 4 位的整数表示数据的原始长度( 以b i t 为单位) ，将这个数字的8 个 字节按低位的在前，高位在后的顺序附加在补位后的数据后面。这时，数据被填 补后的总长度为：l e n = k “+ 5 6 + 8 = ( k + i ) 6 4 字节。 第三步，初始化m d 5 参数： 有四个3 2 位整数变量( a ，b ，c ，d ) 用来计算信息摘要，每一个变量被初始化 成以下以十六进制数表示的数值，低位的字节在前面。 w o r d a ：0 12 3 4 56 7 w o r d b ：8 9 a b c d e f w o r d c ：f e d c b a 9 8 w o r d d ：7 65 4 3 21 0 第四步，定义四个m d 5 基本的按位操作函数： x ，y ，z 为3 2 位整数。 f y ，z ) = 岱a n d y ) o r ( n o t ( x ) a n dz ) g o ( ，耻) = 岱a n dz ) o r ( y a n d n o t ( z ) ) f i o ( ，y ，刁= x x o r y x o r z i y ，刁= y x o r o r 雌功 再定义四个分别用于四轮变换的函数。 设m ，表示消息的第j 个子分组( 从0 到1 5 ) ，“礴表示循环左移s 位，则 四种操作为： 中国科学拄束大学硕士学位论文 基于匿配统计算法的文本复制捡测研究 f f ( a , b cdm j , s ，t 。) 表示a ：b 一( a _ 晒( b ，c ，d ) + m j “) “确) g g ( a , b ，c ，d , m j , s , t i ) 表示a - b + “a + ( g ( b ，c ，d 卜m j - it i ( s ) h h ( a , b , e , d ，m j , s , t i ) 表示a 咖( ( a + 但 c ，d 刈鸭+ t ) s ) i i ( a , b ，c ，d ，m j , s ，t i ) 表示a - b + ( ( a + o ( b c ，妒m j 托声“s ) 第五步，对输入数据作变换： 处理数据，n 是总的字节数，以6 4 个字节为一组，每组作一次循环，每次 循环迸行四轮操作。要变换的6 4 个字节用1 6 个3 2 位的整数数组m o 1 5 】表示。 而数组t 【l 6 4 】表示一组常数，t 【i 】为4 2 9 4 9 6 7 2 9 6 a b s ( s i n ( i ) ) 的3 2 位整数部分， i 的单位是弧度，i 的取值从l 到6 4 。 2 3 文本复制检测系统中采用的技术 文本复制检测技术主要可以分为两大类：基于词频统计的方法和基于匹配统 计的方法。 基于词频统计的方法弧1 l 2 1 纠，也称为基于语义的方法，其代表性的原型系 统有s c a m t “，d s c a m f l 1 1 ，c h e c k 【2 ”，c d s d g 册。基于词频统计的方法主要基于 信息检索技术中的向量空间模型构建算法，统计文本中各个单词的出现次数，根 据单词出现频度建立文本特征向量，最后采用点积、余弦等方法度量两篇文本的 特征向量，以此作为判定文本相似度的依据。 在s c a m 系统中【“，文本中各个单词出现的次数被统计，其采用倒排索引 结构存储文本中的词频信息，依据向量空间模型提出了相关频率模型，用以判定 文本相似性。s c a m t ”i 中还比较了不同的分块策略，分析不同文本块大小的影响， 对单词、五个词、十个词和句子等不同长度的分块策略做了实验。实验表明为了 达到最优的粒度，去除停用词可以使词语分块得到改进。 c h e c k l 2 1 1 系统将文档结构信息引入了文本复制检测中。其把每一篇文档按 照章、节、段落等构建成一棵文档树。树的根节点就是整篇文档，其它节点是文 档的一个结构单元，父节点内容恰好是其子节点内容之和。c h e c k 统计各个节 1 4 中置科学技束大学硕士学位论文箍二章文本复制检滔系统及其榴关技禾 点上出现的关键词，并以关键词在节点上的频率比重赋予相应的权重。由词频提 取构成的树组成该文档的结构特性。首先比较文档层面的关键词，若文档层面的 节点被检测为是相似的，则继续比较下一层的树结构。比较进程结束后，相关的 复制段落被检测出。c 脏c k 系统不是基于精确匹配统计的算法，因此小于段落 的复制文本块将很难被检测出。 c d s d g t r n 运作方式与c h e c k 2 1 1 相似，其将文档的章、节、段等按不同的粒 度构建成一棵结构树，按照从大n d , 的粒度次序逐级比较节点，只有当语义重叠 度和结构重叠度均小于绘定阈值时。才判定节点匹配，进入下一级节点的比较。 当到达叶子节