（教育技术学专业论文）开放式电子文档剽窃检测服务构建技术研究.pdf

摘要 随着信息技术的普及和i n t e m e t 的飞速发展，人们可以越来越容易的从i n t e r a c t 获取各 种电子文档资源，但同时也可以方便地采用“复制粘贴”操作米剿窃电子文档的内容。可以 说i n t e m e t 这一开放性平台在使人们能够方便、快速、高效地获取各种电子文档资源的同时， 也成为了剽窃者窃取信息的温床。在这种背景下，构建开放式电子文档剽窃检测服务系统的 需求呼之欲出。 本文通过分析比较，对开放式电子文档剽窃检测服务系统的现状、结构、特点等给出了 详细的总结和描述，对构建开放式电子文档剽窃检测服务系统所涉及到的主要技术。包括候 选文档获取技术和电子文档剽窃检测技术进行了详细研究。 对于候选文档的获取技术，本文对常用的开放式环境信息获取技术，即网络蜘蛛技术和 元搜索技术，进行了比较和分析，并给出了基于元搜索的候选文档获取技术实现方案。 本文还通过大量比较，分析了现有的电子文档剽窃检测技术，提出了适用于大规模电子 文档检测的s c a d 剽窃检测算法，该算法采用权重较高的关键词来作为a n c h o r ，以此来选 择经预处理过滤后的句子生成指纹，并最终通过比较指纹来计算文档间的相似度。实验表明， s c a d 算法，在生成的指纹数量上，比对效率上以及准确度上均优于传统算法，适合大规模 电子文档的剽窃检测应用。 同时，为了更好地满足剽窃检测服务需求，本文还提出了基于后缀树的一对一比对检测 算法，算法对两篇文档进行比较，找出两篇文档的公共子串，并用高亮的方式显示出来，为 判断是否剽窃提供更宣接的依据。 最后，本文还描述了针对教育类论文进行检测的开放式剽窃检测服务原型系统，给出了 系统的设计方案，并展望了下一步工作。 关键词：剽窃检测、数字指纹、候选文档、后缀树 a bs t r a c t w i t ht h ep o p u l a ro fi n f o r m a t i o nt e c h n o l o g yt o l dt h er a p i dd e v e l o p m e n to fi n t e r n e t ，p e o p l e c a ne a s i e ra n de a s i e rg e ta l lk i n d so fr e s o u r c ef r o mi n t e r a c ta n dc a ne a s i l yp l a g i a r i z et h ec o n t e n to f e - d o c u m e n t sw i t ha “c u ta n dp a s t e a p p r o a c h i tc a nb es a i dt h a tt h eo p e n e di n t e r n e tp l a t f o r m m a k et h ep e o p l ec o n v e n i e n t l yg e ta l lk i n d so fe l e c t r o n i cd o c u m e n t sr e s o u r c e sa n d ，a tt h es a m e t i m e ，i sah o t b e do fp l a g i a r i z e r sw h os t e a li n f o r m a t i o n u n d e rs u c hc i r c u m s t a n c e s ，t h eo p e n e d e - d o c u m e n t sp l a g i a f i s md e t e c t i o ns e r v i c es y s t e mi si nu r g e n tn e e d t h i sp a p e rd e s c r i b e st h e p r e s e n ts t a t i o n ，s t r u c t u r ea n dc h a r a c t e r i s t i c so ft h eo p e n e d e - d o c u m e n t sp l a g i a r i s md e t e c t i o nf l 艘 v i c es y s t e ma n dc o n d u c t sad e t a i ls t u d yo ft h em a j o r t e c h n o l o g i e si n v o l v e di nt h ec o n s t r u c t i o no ft h eo p e n e de - d o c u m e n t sp l a g i a r i s md e t e c t i o ns e r v i c e s y s t e m ，i n c l u d i n gc a n d i d a t ed o c u m e n t sa c c e s st e c h n o l o g ya n de - d o c u m e n t sp l a g i a r i s md e t e c t i o n t e c h n o l o g y f o rc a n d i d a t ed o c u m e n t sa c c e s st e c h n o l o g y , f i r s tt h i sp a p e rc o m p a r e sa n da n a l y z e st h e c o m m o n l yu s e di n f o r m a t i o na c c e s st e c h n o l o g i e si e w e bs p i d e ra n dm e t as e a r c h , t h e ng i v e st h e i m p l e m e n t a t i o no fc a n d i d a t ed o c u m e n t sa c c e s st e c h n o l o g yb a s eo nm e t as e a r c h i nt h i sp a p e r , a na n c h o r - b a s e da l g o r i t h ms c a di sa l s od e v e l o p e dt od e t e c tp l a g i a r i s mo f l a r g es c a l ee - d o c u m e n t s t h i sa l g o r i t h mf i r s ts p l i t sad o c u m e n ti n t os e n t e n c e sa f t e rp r e p r o e e s s i n g a n dt h e ng e t sa na n c h o rs e tb ya na l r e a d yw e i g h t e dk e yw o r d ss e t a c c o r d i n gt ot h ea n c h o rs e t ， s e n t e n c e sc o n t a i n i n gt h ea n c h o r sa r ec h o s e nt og e n e r a t ef i n g e r p r i n t s ，a n dt h e nt h es i m i l a r i t yo fa n y t w od o c u m e n t si sc o m p u t e du s i n gt h ef i n g e r p r i n t s n ee x p e r i m e n tr e s u l ti l l u s t r a t e st h a tt h i s a l g o r i t h mh a sh i g hp r e c i s i o na n ds e p a r a t i o nw h i l et h ef i n g e r p r i n t ss e ti sv e r ys m a l l a tt h es a m et i m e ，i no r d e rt om e e tb e t t e rt h en e e d so fp l a g i a r i s md e t e c t i o ns e r v i c e s ，t h i sp a p e r a l s op r o p o s e dao n e t o - o n ed e t e c t i o na l g o r i t h mb a s e do nt h es u f f i xt r e e t h i sa l g o r i t h mc a l l i d e n t i f yc o m m o ns t r i n g so ft o wd o c u m e n t s ，a n dt h e nw ec a nh i g h l i g h tt h e s es t r i n g st op r o v i d e d i r e c te v i d e n c et ou s e r s f i n a l l y , t h ep a p e ra l s od e s c r i b e sap r o t o t y p es y s t e mo fo p e n e dp l a g i a r i s md e t e c t i o ns e r v i c e f o re d u c a t i o np a p e r s ，a n dg i v e st h ed e s i g na n dm a k e sav i s i o nf o rt h en e x tp h a s eo fi m p r o v e m e n t s k e y w o r d s ：p l a g i a r i s md e t e c t i o n ，f i n g e r p r i n t i n g ，c a n d i d a t ed o c u m e n t ，s u f f i xt r e e i i 学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新 的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成 果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已 经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了 谢意。 。作者签名：狐硅 日 期：垒监：垒丝 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进 行检索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解密后适用本规定。 作者签名：拯经 f t 期：迎吕! 墨丛 第一章前言 1 1 研究背景及意义 电子文档作为种重要的网络资源广泛分布在i n t e r n e t 上，随着i n t e m e t 得匕速发展， 如今它已经成为广人科研人员、教师、学生等研究和学习得重要参考资料。i n t e m e t 的开放 性使得人们可以更方便、快速、高效地获取各种电子文档资源，但是从另一方面来看，它的 这一特性也使它成为了滋生剽窃的温床。当剽窃者从i n t e m e t 轻而易举地获取电子文档并且 进行修改甚至不作任何修改就以自己的名义公开发布时就构成了电子文档的剽窃行为。当 前。对数字产晶剽窃、抄袭的新闻屡见报端，这种违反道德甚至故意侵犯知识产权的不端行 为，已经严重影响了学术研究的健康发展。根据美国c a i ( c e n t e rf o r a c a d e m i ci n t e g r i t y ) 的 调查统计显示，美国大学生中有7 0 承认曾以各种各样的形式抄袭，在这些学生中承认通 过h t e m e t 进行抄袭的就有4 0 ，同时，还有7 7 学生认为从网络上抄袭的行为并不是什么 严重的问题，调查还显示这种状况将继续发展下去【i 】。国内这种现象也不容小觑，根据一份 华东师范大学2 0 0 5 年对沪上部分高校5 0 0 名大学生进行调查而完成的大学生网络道德状 况调查报告显示，5 0 的学生承认在网络上抄袭过论文。由此可以看出电子文档的剽窃行 为已经相当严重，而其中通过i n t e r n e t 获取电子文档进行剽窃的行为占有相当大比重。 对于剽窃行为，我们在揭露、声讨和谴责之余，更应该通过健全的机制加以防范，防止 已发生剽窃行为的数字产品地发布。因此，人们在2 0 世纪7 0 年代便开始了对电子文档剽窃 检测服务系统的研究。目前世界上存在的具有代表性的电子文档剽窃检测系统有c o p s 2 1 、 k a o l a 【3 j 、c h e c k f 4 1 等，这些系统在一定程度上抑制了电子文档的剽窃行为。但是这些电 子文档剽窃检测服务系统大多是“封闭式的”( 基于本地注册文档库并且服务范同非常有限) ， 并且是为英文文档的检测而研究和建设的，支持其它语言的能力差，检测范围小，用户面窄， 不能满足当前更广泛的需求。在这种情况下，研究开放式电子文档剽窃检测服务构建技术是 非常有意义的。 开放式电子文档剽窃检测服务基于i n t e m e t 提供服务，它的服务对象是所有的i n t e r n e t 用户，它的资源库是i n t e m e t 上各式各样的电子文档，这是一种更广泛、更全面的剽窃检测 服务形式。开放式电子文档剽窃检测服务的构建，将为我国的学术界、各级各类学校、出版 部门提供开放、便捷、自动的电子文档剽窃检测服务。对抵制剽窃行为具有积极的作f i 。 开放式电子文档剽窃检测服务将综合使用电子文档的剽窃检测技术、电子文档预处理技 术、候选文档( c a n d i d a t ed o c u m e n t s ) 获取技术等先进技术进行构建，其中电子文档的剽窃 检测技术是核心技术。因为电子文档预处理技术的研究相对比较成熟，并且有现成的研究成 果可以利用，所以，本文主要针对候选文档获取和电子文档剽窃检测这两种技术进行研究。 本文首先对开放式环境下候选文档的获取问题进行了分析研究，并提出了基于元搜索的候选 文档获取技术实现方案，然后，又对电子文档剽窃检测技术中的数字指纹粒度问题、数字指 纹选取问题以及对一比对检测问题等进行了详细研究，提出了新型和高效的针对大规模文 档检测的s c a d 剽窃检测算法和基于后缀树的对一比对检测算法，最后，还实现了开放 式剽窃检测服务原型系统。 1 2 开放式电子文档剽窃检测的界定 上海辞书出版社1 9 9 9 年新版辞海( 缩印本) 将“剽窃”定义为“抄袭( 别人的思 想或言词) ”。由此定义，可以得到两个结论，首先剽窃和抄袋并无本质不同，其次各种各样 的剽窃总地来看可分为思想( 或观点) 的剽窃和文字( 或言词) 的剽窃甄种。我国国家版权 局在1 9 9 9 年回复地方的公函中也曾将剽窃分为“高级剽窃”( 观点剽窃) 和“低级剽窃”( 文 字剽窃) 【s 1 。 所谓电子文档的剽窃检测，就是判断一个文件的内容是否抄袭、剽窃或复制丁另外一 个或者多个文件【6 j 。那么，根据上述剽窃的定义，电子文档的剽窃检测也应该包含针对观点 剽窃的检测和针对文字内容剽窃的检测两种。当然，这里的电子文档是指以自然语言为内容 的电子文档。 然而，从思想观点上对剽窃行为进行认定，这一观点虽然在理论上正确，但是实际的 操作却很难。具体而言有如下几点： l 、科学史上不同个体独立发现同一观点的例子比比皆是( 比如发生在莱布尼茨和牛顿 之间微积分发明权的争论) ，这就使得从观点上判断剽窃不可行【5 l 。 2 、在绝大多数时间内、绝大多数学术界中人都不可能作出实质性创新，这一科学史上 的基本事实使得观点上判断剽窃必要性大大丧失t 5 1 。 3 、从技术的角度来看，虽然目前语义检测有一定的进展，但是无论是检测速度还是精 度都无法满足实际需求。尤其在大规模数据检测的前提下，基于观点的剽窃检测可操作性相 当低。 因此基于以上考虑，以文字内容本身来作为判断剽窃的依据是符合实际的，本文所述 的剽窃检测，也是指在文字层面的剽窃检测。 所谓开放式电子文档剽窃检测就是指在开放式环境下的电子文档剽窃检测。在这里， “开放式”是相对于“封闭式”而言的。传统的剽窃检测服务一股是基于本地注册文档库的， 并且服务范围是有限的，比如图_ 1 5 馆或某个学术机构内部，是封c j l 的，而开放式电子文档剽 窃检测是基于i n t c r n c t 提供服务的，是开放的。它的开放性首先体现在用户类犁的开放性， 即它的服务对象可以是所有连接到i n t c r n e t 的学校、出版部门、机关或个人等：其次体现在 它的资源的开放性，即它的资源不局限在本地范围内，而是i n t a - n e t 上各式各样的电子文档。 这是一种更广泛、更全面的剽窃检测服务形式。 1 3 电子文档剽窃检测系统现状 1 j3 1 国外现状 由于国外信息技术比较发达，并且知识产权等法规相对比较完善，9 0 年代中后期贝尔 实验室、普林斯顿大学等就开始了对数字化环境中利用信息技术保护著作权的研究，并产生 了一些反剽窃原型系统和商业软件系统。其中比较典型的有c o p s 、s c a m f 7 1 、m d r t 引、 s n i t c h n 等。 1 9 9 5 年，斯坦福大学的b r i n 和g a r c i a m o l i a n 等人首先提出了在“数字图书馆”中应用 2 数字文档复制检测机制，并开发出了c o p s ( c o p yd e t e c t i o ns y s t e m ) , k 其相应的算法。c o p s 的系统结构如瞄l l 所示。 t e x 转化为a s c i id v l 转化为a s c i it r o f f 转为a s c ii 土土土 识别句子并a 进行h a s h 映射 上上 文樯处理检索处理 图卜1c o p s 剽窃检测系统絮构 c o p s 是一种封闭式的剽窃检测系统，它的候选文档来自于文档注册机制，即采用本地 的文档注册库，由人工收集文档填充进文档库。在检测算法上c o p s 采用了基于数字指纹的 以句子序列为单位的剽窃检测算法，系统首先将所有文档转化为统一的a s c i i 文本，然后 将句子序列转化为数字指纹，进行检测或存入数据库。这种算法对检测大面积文档复制比较 有效，计算速度比较快。但是它不能有效检测对句子局部复制的现象且句子的边界划分比较 模糊。显然，c o p s 系统在检测范围和服务的用户范围上都是很受限制的，但是其系统框架 为以后的文档复制检测系统奠定了基础。 1 9 9 5 年，g a r c i a - m o l i a n 和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 d c o p ya n a l y s i sm e t h o d ) 原型系统。s c a m 对c o p s 的检测范围和用户范围进行了很大的扩 展，最终使之成为开放式的系统架构，其功能结构如图l 卫所示。 图卜2s c 媳i 剽窃检测系统架构 3 从图l - 2 可以看出，s c a m 候选文档主要来源有两个，一个是i n t e r n e t 上的开放资源， 还一个就是用户通过表单提供的注册文档。这使得s c a m 可以在更火的范围内获取文档， 并可为更多的用户服务，这也是s c a m 开放性的基础。在检测算法上，s c a m 借鉴了信息 检索技术中的向量空间模型v s m ( v e c t o rs p a c em o d e l ) ，使用基丁词频统计的方法来度量文 档相似性，具有较高的准确性。后来g a r c i a m o l i a n 和s h i v a k u m a r 等人还在s c a m 的基础 上提出了d s c a m ( d i s t r i b u t e ds t a n f o r dc o p y a n a l y s i sm e t h o d ) 【1 0 】模型，提供了把单个注册 库扩展到分布式数据库上以及在w e b 上探测文本复制的方法。 2 0 0 0 年，m o n o s t o r i 等建立了m d r 原型系统，这也是一个开放式的电子文档剽窃检测 系统。m d r 主要有四个组件：搜索引擎组件( s e a 玎c h 吒i l g i i l e c o m p o n e n 0 、代理( a g e n 0 、转化 组件( c o n v e r t e rc o m p o n e n t ) 、检测组 f - 牛( m a t c h i n ge n g i n ec o m p o n e n 0 。其中，候选文档的获取 是通过搜索引擎组件和代理完成的，搜索引擎组件利用网络蜘蛛的技术从w e b 上获取文档， 代理则从指定的网站或已提供的数字图书馆中获取资源。转化组件完成对各种文档的预处理 工作，把文档转化成统一格式，提供给检测引擎处理。m d r 的检测引擎采用改造的后缀树 算法来确定文档的重叠度，后来又采用后缀向量存储后缀树来提高识别效率。m d r 识别精 度也较高，但速度太慢，不适合大规模的剽窃检测。 2 0 0 6 年，s e b a s t i a nn i e z g o d a 等构造了名叫s n i t c h 的开放式剽窃检测系统。s n i t c h 利用g o o g l e 的w e b a p i 获取候选文档。剽窃检测采用了“滑动窗口法”，利用数字指纹技术 进行检测，速度较快，但是这种算法对数字指纹的生成方式有特殊要求，对于中文等双字节 存储的文字达不到预期的效果。 另外，一些商业机构也积极介入剽窃检测领域，产生了一些商业系统和软件。根据 c l a r e m o n t m c k e n n a 大学对可用的剽窃检测软件效率的调查显示，在检测“剪切和粘贴”型 的剽窃行为方面，t u m l t l n 具有较好的效果【9 j 。t u m l t l n 提供开放式检测服务，主要是针对在 校学生和教师。学生通过i n t e r n e t 提交作业，t u m l t i n 检测分析后在六个小时内将检测报告 返回给教师，作为评分的依据或反剽窃的证据。t u m i t i n 在国外很受欢迎，当然因为它是一 个商业系统，它的服务也是很昂贵的。 1 3 2 国内现状 和国外相比，我国运用计算机技术进行电子文档的剽窃检测总体上还处于起步阶段。在 开放式电子文档剽窃检测系统方面，国内尚未出现代表性的系统或软件，只有一些处于实验 室的理论原型。具有代表性的是香港理工大学的s i 等人建立的c h e c k 系统模型，c h e c k 采用统计关键词的方法来度量文档相似性，最大特点是把文档结构信息引入到文档相似性度 量中。c h e c k 首先将文档按照章、：箝、段等构建一颗文档树，树的根结点就是整篇文档， 其他节点都是文档的一部分，父节点的内容是其子节点的内容的总和。然后使用词频统计的 方法提取出各个节点的主题信息。在进行文档比较的时候，按照深度优先比较两篇文档相应 的节点，先比较节点对应的主题信息，如果节点的主题信息相似，就继续节点的具体内容以 及节点对应的子结点，否则不进行比较，从而降低了文档无谓比较的次数，提高了程序的性 能。最终以匹配的节点数目作为文档是否具有抄袭嫌疑的依据。c h e c k 用点积法计算关键 4 词向量的相似度，计算公式如下： 眠蚓2 愿丽x a , x b j 其中匕，分别代表文档a ，b 的关键词向量，r = u 楚文档词向量的并集， 属于参考向量，x _ j ，x 鲋分别是经过归一化后的匕，关键词，归一化公式如下： 咒广0 么j 畿，笺 其中j 是关键词口在该节点的权重。 提取各个节点主题信息的过程中，还考虑了特殊格式的单词，如粗体、斜体，对于这些 词一律认为是很重要的词，不论它们出现的频率的多少。c h e c k 统计各个节点上关键词词 频，并以每一个关键词在该节点上的频率比重为相应权重，由此构建成的文档树就代表该文 档的结构特征。但是，由于l a t e x 文档中含有格式信息，c h e c k 原型只检测l a t e x 文件 检测面很窄。 另外，2 0 0 5 年金博等人提出“中文文档复制检测系统”【1 7 1 ，在内容层次的剽窃检测方 面进行了些尝试，由于是在语义层次的检测，检测算法复杂性大大增加，从而导致效率成为 问题。 1 4 开放式电子文档剽窃检测系统基本构成 由已有的这些原型系统我们可以看出，开放式屯子文档剽窃检测系统都具有大体相似的 结构，经过总结分析，本文总结出一种通用系统结构，如图1 3 所示。 图1 - 3 开放式电子文档剽窃检测服务系统一般架构 5 系统有三个主要技术模块组成： ( 1 ) 候选文档获取引擎模块 剽窃检测系统应该拥有自己的候选文档库，所有的待测文档都是通过和候选文档库中的 文档比较来检测的。传统的候选文档获取方法主要是人：l ：收集注册的方式，这种方式效率低 而且资源数量相当有限。开放式剽窃检测服务系统应该能够从开放式电子文档资源库获取文 档，在这里开放式电子文档资源库是指，i n t e m e t 资源、数字期刊提供商提供的电子期刊资 源等。因此该模块应能解决从开放式环境下获取资源的问题，这一点可以通过对现有的信息 获取技术进行一定的改造来实现，比如网络蜘蛛技术和元搜索技术等。同时，传统的人工注 册方式应予以保留并将此功能开放给所有用户，以便汞1 自动获取的资源相互补充。 ( 2 ) 电子文档预处理模块 i n t e m e t 中的存在各种各样的电子文档类型，该模块应针对中文特点解决各种类型的电 子文档格式归一化及基本的语义处理问题。在文档预处理中，主要涉及到文档内容抽取技术、 降噪技术、中文分词技术等。 文档内容抽取是指去掉文档的格式信息并抽取出纯文本内容，以方便完成文档内容的归 一化。比如，对于h t m l 格式的文档，文档预处理过程将在扫描h t m l 文档的时候，去除 多余的h t m l 标记，提取出文档中显示在页面上的文本内容。对于其它文档的格式识别要 根据文档的特定格式进行分析，目前也有一些工具可以帮助抽取常见格式文档的文本内容， 比如o f f i c e 系列文档、p d f 文档等均有相应的抽取工具。i n t e r n e t 中的电子类型繁杂，需要 针对不同类型一一分析。本研究中采用目前已有的抽取工具来完成对大部类型的电子文档的 抽取。 中文分词是剿窃检测的重要基础工作，它使检测能够完成基本的中文语义分析，具有一 定的自然语言理解的功能。与英语文本不一样，英语文本以字为组成单位，然而汉语文本中 有意义的最小构成单位却是词( 当然，有的词可能就是一个字) 。为了让计算机自动地对汉 语文本进行分析处理，一个主要的基础工作就是要将汉语文本中的词提取出米。目前研究得 比较多的中文分词技术主要有：机械匹配法、语义分词法、后缀分词法等。本研究将直接利 用现有的研究成果。 ( 3 ) 剽窃检测引擎模块 7 该模块是票4 窃检测系统的核心。它采用一定的剽窃检测算法对预处理后的文档进行检 测，并生成检测报告反馈给用户，作为判定剽窃的参考依据。在剽窃检测模块要充分考虑大 规模数据情况下检测的速度与精度。另外，该模块还应该能实现高效的一对一比对检测算法。 为用户提供更直观的参考依据。 1 5 主要研究内容 本课题主要开展以下研究： ( 1 ) 适用于开放式电子文档剽窃检测服务系统的候选文档自动获取技术实现方案： ( 2 ) 从指纹粒度划分、指纹特征选取等角度，研究新型的适用于大规模电子文档剽窃 检测的电子文档剽窃检测算法； 6 ( 3 ) 针对两篇文档的一对一剽窃检测的算法，并实现两篇文档相同内容的高亮显示， 为刿断是否剽窃提供一个直接的参考依据； ( 4 ) 开放式电子文档剽窃检测服务系统设计与开发方案，荠实现原型系统。 1 6 论文的主要工作和组织结构 1 6 1 主要工作 ( i ) 在研究国内外各种现有的电子文档剽窃检测系统和电子文档剽窃检测技术的基础 上，对开放式电子文档剽窃检测服务系统的界定、现状、结构特点等给出了详细的总结和描 述： ( 2 ) 通过分析资料，总结出开放式剽窃检测服务系统的实现原理、主要技术模块以及 系统结构，并对各主要技术模块分别进行探讨： ( 3 ) 对候选文档的自动获取方法进行分析，并提出了利用元搜索获取候选文档的构建 和实施方案： ( 4 ) 对电子文档剽窃检测技术进行深入地分析总结，并在此基础上提出了基于a n c h o r 的s c a d 剽窃检测算法，实验证明该算法在精度和效率上具有一定的优越性；一 ( 5 ) 对后缀树算法进行改造，提出了基于居缀树的检泓算法，实现了一对一钓电子文 档剽窃检测并且实现了两篇电子文档间相同部分的高亮显示功能，更直观、精确地显示抄袭 程度； ( 6 ) 设计开发开放式电子文档剽窃检测服务系统原型。， 1 6 2 论文的组织结构 第一章绪论给出了论文研究背景及意义、开放式电子文档剽窃检测的界定、国内外研 究现状分析、开放式电子文档剽窃检测服务系统的基本构成、本文的研究内容以及论文的组 织结构。 第二章候选文档获取技术对候选文档获取技术进行详细分析和总结，并提出了基于元 搜索获取候选文档的工作原理和构建方案。 第三章电子文档剽窃检测技术对现有的电子文档剽窃检测技术进行总结和分析，提出 了适用于大规模检测的基于a n c h o r 的s c a d 电子文档剽窃检测算法，并提出了适用于一对 一剽窃检测的基于后缀树的比对检测算法。 第四章原型系统的设计与实现给出开放式屯子文档剽窃检测服务原型系统的没计方 案，并具体描述了后台并行计算的设计方案。 第五章总结与展望在总结本文研究工作的基础上，对有待研究的： 作进行展望。 了 第二章候选文档获取技术研究 候选文档( c a n d i d a t ed o c u m e n 0 ，是指准备与待测文档进行比较的文档，在实际应_ h j 中 可以采川人：i = 收集候选文档或从网络自动获取候选文档两种形式。对于人：l ：获取的方式，局 限比较明显，无法满足实际应用的需求，只能作为辅助方式应用。随着i n t e m e t 的迅速发展， 利_ j 网络来获取候选文档成为一个较明显的趋势。通常从网络获取文档有两种技术，即肉络 蜘蛛技术和元搜索技术。本章将对这两种技术进行介绍并将提出基丁元搜索的候选文档获取 技术实现方案。 2 1 网络蜘蛛技术 信息获取技术中比较常用的是网络蜘蛛技术。网络蜘蛛是一种自动抓取页面的程序，一 般用于为搜索引擎遍历网页，因此而得名，此类程序的英文名字叫：w c b s p i d e r 或 w e b c r a w l e r 。由于大多数网页包含指向其他页面的链接，所以一个网络蜘蛛程序可以从任何 一个网页开始搜索。大型搜索引擎都有很多个网络蜘蛛程序并行工作。 网络蜘蛛是一种软件，它通常从一个“种子集”( 如用户查询、种子链接或种子页面) 出发，顺着w w w 页面文件间的链接在互联网中漫游，自动在w e b 上按照某种策略进行远 程数据的搜索，并通过h t t p 协议请求和下载w e b 页面或其它电子文档到本地进行文档分 析，从文档中得到新的链接，然后再以循环迭代的方式访问。它记录u r l 、文件的简要内 容、关键字或索引，由于不需要人工参与，它的速度快、覆盖面广、及时性好。它的漫游结 果是形成一个很大的本地数据库，从而为最终实现搜索引擎提供资源基础。我们也可以利刖 这种程序来搜索并获取候选文档为剽窃检测系统准备必要的资源。网络蜘蛛的简单结构如图 2 1 所示。 下载的 的u r l 图2 - 1网络蜘蛛的简单结构 网络蜘蛛技术目前是大多数独立搜索引擎使用的采集网页的技术，在信息获取中是一项 重要技术。但是网络蜘蛛技术也存在不少问题，限$ i j - f 它在电子文档剿窃检测方面的应用。 ( 1 ) 网络蜘蛛并不能访问w e b 上所有的文档资源，w 如上有很多资源库( 如商业电子 期刊库) 中的资源网络蜘蛛是无法获取的，这就严重限制了网络蜘蛛在剽窃检测中的应用。 8 因为这些资源库中的文档，往往正是剽窃检测系统所需要的候选文档。 ( 2 ) 网络蜘蛛必然要存储大量的网页信息，这就会带来超大规模数据库存储和数据库 索引的问题，数据库的管理也是比较棘手的问题。 ( 3 ) 网络蜘蛛程序在遍历w e b 时也存在危险，很可能遇到一个环链接而陷入死循环中。 简单的避免方法就是忽略已访问过的u r l 或限制网站的遍历深度。 ( 4 ) 网络蜘蛛程序是一种比较脆弱的程序，因为它与很多的w e b 服务器、不同的域 名服务器打交道，而这些服务完全在系统的控制之外。由于网络上包含了大量的垃圾信息， 网络蜘蛛程序很可能会收取这些垃圾信息。一个页面出现问题也很可能引至程序中止、崩溃 或其他不可预料的行为。 另外，网络蜘蛛在获取网页时要充分考虑w e b 系统的分布性、相异性，考虑网络请求 响应时间，考虑网页更新速度等等，所有这些因素综合起来使得网络蜘蛛变成一个非常复杂 的系统。因此访问i n t e m e t 的网络蜘蛛程序应该设计得非常强壮，充分考虑各种可能遇至0 的 情况，让蜘蛛程序在遇到各种情况时可以采取相应的处理行为，而不至于获得一些垃圾信息 或者直接就对程序本身造成危害。正如【1 2 】中所说，“利用网络蜘蛛获取网页是一项极富挑 战性的工作”。 2 2 元搜索技术 2 2 1 元搜索概述 随着i n t e r n e t 的飞速发展，i n t e m e t 上的信息量极度膨胀，人们越来越多的依赖于各种 独立搜索引擎来获取信息。但是目前任一种独立搜索引擎又都很难满足用户的需求。这是因 为，就各种独立搜索引擎而言，相对于其能力，w 曲资源数量增长实在太快，以至于其信 息覆盖范围非常有限，根本不可能索引到全世界所有的w e b 资源。表2 1 是2 0 0 5 年清华大 学1 1 r 可用性实验室统计的中文搜索引擎网页覆盖率结果的数据。 表2 - 1 中文搜索引擎网页覆盖率结果数据 g o o g l e 搜百度中搜爱问搜狗 静态网页2 0 0 31 6 l l2 2 8 62 3 7 51 4 8 29 1 3 动态嘲页 1 2 5 45 3 l1 6 9 2 6 5 l4 l1 6 3 全部网页 3 2 5 72 1 4 23 9 7 8 3 0 2 6 1 5 2 3 1 0 7 6 全部网页覆盖率 2 6 6 2 1 7 5 1 3 2 5 2 2 1 7 3 1 2 。4 5 8 ，8 从上面的数据可以看出这些大型的独立搜索引擎，所能从w e b 上获取的信息也只是 小部分。并且网络中还存在着大量有价值的、只对特定人群公开的资源( 比如各种电子期刊 库) 是一般的搜索引擎不可能获取到的。 另外。各种不同的独立搜索其索引的内容、针对的人群不同，机制、范围、算法等也有 较大的差异。根据专家的评测，同样一个查询请求在不同的搜索引擎中的查询结果的重复率 不足3 4 。 因此，要想获得比较全面的、准确的结果，就必须反复调用多个搜索引擎。元搜索技术 9 正是在这种背景下出现的。元搜索技术是指建立在一个或多个已存在的搜索框架之上的搜索 技术，也就是说通过向一个或多个已存在的搜索框架传递特定的检索需求，并对获取的结果 进行合并和进一步的处理，以满足应用需求的技术。利用元搜索来提供服务的模块称之为元 搜索引擎。元搜索引擎依赖于其他搜索引擎，要达到为刚户提供精确而全面的搜索结果，需 要较好的元搜索策略。 元搜索引擎按使用方式可以分为独立的元搜索引擎和功能模块型元搜索引擎。独立的元 搜索引擎是指在网上提供服务的独立的元搜索引擎，客户通过浏览器就可以使刚。而功能模 块型元搜索引擎并不直接提供服务，而是作为系统的一个组件为系统服务的，一般不提供 w e b 调用。本文获取候选文档的元搜索引擎是种功能型元搜索弓l 擎。 综上所述，利用元搜索获取候选文档有以下优势： 1 、信息覆盖面广 元搜索引擎建立在多个搜索引擎之上，从而形成了一个由多个分布的、具有独立功能的 搜索引擎组成的虚拟整体。可以一次让多个目标搜索引擎同时查询，大大扩展了检索范围。 多个搜索引擎的结果，又实现了信息的互补，使搜索结果更加全面。 2 、扩展性好，和各种电子文档资源库结合方便 网络中存在着很多的大型电子文档资源库( 如c 1 1 l 【i 、万方等) ，如果想利用这些资源库的 电子文档进行剽窃检测的话，直接对这些资源库进行改造显然是不现实的，利用网络蜘蛛也 是无法获取的，而元搜索却是一个可行的办法，因为各个资源库基本上都有自己的搜索服务 模块。 3 、构建简单，维护方便 元搜索引擎省去了独立搜索引擎采集和存储网页、建立和存储索引的工作。它所调用的 搜索引擎都是完整的功能实体，不需要维护，只要知道它们的调用接口。元搜索可以将重点 放在查询请求的分布和查询结果的处理上。 2 2 2 获取候选文档元搜索引擎的工作原理 与网络蜘蛛采集网页相比，元搜索不需要维护庞大的索引数据库，也不需要考虑互联网 资源的遍历速度，它把注意力主要放在查询请求处理及过滤从其它搜索引擎返网的相关搜索 结果上。具体来说，获取候选文档的元搜索引擎应该由三个模块组成，即：查询关键词获取 模块、成员搜索引擎调度模块和检索结果处理模块。与一般的元搜索不同的是，获取候选文 档的元搜索引擎多了一个查询关键词的获取模块，并且省去查询结果显示模块。下面对各个 模块分别进行简单的介绍。 ( 1 ) 查询关键词获取模块 一般的元搜索引擎是不具备这个模块的，因为它的关键词是用户直接输入的。但在剽窃 检测服务中，用户输入的最小单元是文档，要想自动从网络中获取相关文档，首先必须能够 从用户提交的文档中自动获取关键词，然后才能提交给搜索引擎进行查询。当然，在这一模 块中也可以让用户指定适当的元搜索关键词，以提高检索精度。 ( 2 ) 成员搜索引擎调度模块 1 0 负责将用户的请求分发给成员搜索引擎。在这里成员搜索引擎包括各种通用搜索引擎、 专业搜索引擎、提供特定资源搜索服务的引擎( 如各种电子期刊网提供的搜索服务) 等。并 决定何时调腭何种弓l 擎，如可以通过分析用户的兴趣和网络的实际情况来选择搜索弓；擎，这 有利于提高查询精确度和响应速度。由于不同的搜索引擎所支持的查询语法不同，即便是同 一个引擎，也有不同的表达方法，所以这一模块还必须将元搜索引擎中的查询请求映射到对 应搜索引擎中，而且使得语义信息不丢失的情况f ，把元搜索的检索语法转化为成员搜索弓1 擎的语法结构。 ( 3 ) 检索结果处理模块 元搜索的搜索结果由多个独立搜索引擎的并集组成，这就难免会产生结果重复、排序混 乱、检索结果相关度不高等问题。检索结果处理模块，对检索结果重新整理、排序，尽可能 的解决这些问题。 获取候选文档的元搜索引擎工作原理如图2 - 2 所示。 图2 - 2 获取候选文档韵兀搜索弓l 擎工作原理国 2 2 3 查询关键词自动生成 在剽窃检测服务系统中用户提交的文档，如果用户在提交文档的同时没有指定关键词， 这就需要系统自动从文档中抽取词语作为查询关键词。查询关键词的提取直接影响到后面的 检索的结果，并不是用户提交文档中所有的词都可以作为关键词，有许多语气词、助词、虚 词等对相关文档的获取没有任何的帮助，应直接过滤掉，而尽量的保留名词及修饰它的形容 词等。假设文本已经过分词及词性的标注，把文本变成了一个词的序列，提取的步骤如下： ( 1 ) 首先将文本中的系词、前置词、冠词、代词等词类去掉，将形容词或副词与其修 饰的词结合在一起当作一个复合词。 ( 2 ) 对文本从头开始逐词顺序往下扫描，并按下列方法进行统计： a 每个词在其第一次出现时设一个相应的计数器，并置成l ，此后该词每出现一次 就在其相应的计数器中加i 。 b 在标题或摘要( 如果有的并能识别的话) 中出现的词，除同a 中的处理外，再在相 应的计数器中外加一个整数t 。 c 在文档首部或尾部出现的词，除同a 中的处理外，再在相应的计数器中外加一个 整数p 。 d 在文档中加粗或字号加大的词语，除同a 和c 中的处理外，再在相应的计数器 中外加一个整数i 。 e 尽量找出文本中的一些“关键句”，例如那些包含诸如“关键在于”，“旨在”， “主要目的( 标) 是”等的句子。对在“关键句”中出现的词，除同上述a 、b 、c 、d 中的 处理外，再在相应的计数器中外加一个整数k 。 f 对于一些专业的领域，还可根据相关经验或专家意见，设立其它方案进行加权。 ( 3 ) 归一化：将所有词的计数器的计分相加得到和数s ，然后每个计数器的计分除以s 再放入计数器。 ( 4 ) 截取关键词，根据权重从高到低选取一定数量的词作为关键词。 采用上述方法可把不够重要的关键词忽略掉，而最终得到一个“查询关键词集”。 2 2 4 选择目标搜索引擎 如何选择目标搜索引擎是在研究实现一个元搜索引擎过程中需要解决的一个关键问题。 元搜索引擎下的每个目标搜索引擎都有自己的由一系列搜索结果所组成的文本数据库，目标 搜索引擎选择就是为每个查询提供最可能包含有用搜索结果的目标搜索引擎，这对于元搜索 引擎的执行效率来说是至关重要的。如果一个元搜索引擎的目标搜索引擎数量不多，可以将 用户的查询送到各个目标搜索引擎。然而，当目标搜索引擎很多，那么将查询送到每个目标 搜索引擎的策略显然不太合理。因为在这种情况下，大多数目标搜索引擎对此查询毫无用处。 假设用户只对l o 个与其提交查询最匹配的结果感兴趣，这l o 个结果显然最多只能来自于 十个不同的数据库。因此，如果目标搜索引擎的数量远远超过