基于计算机数字指纹的文本抄袭检测算法研究

第 1 章 绪论1.1 文本抄袭检测背景及意义随着互联网在生活中各个方面的广泛应用，电子文档已经成为消息传递的重要载体。由于电子文档固有的易篡改、易抄袭等特点，人们能够轻易地非法对其进行传播，导致出现了越来越多的文本抄袭现象，对信息检索、电子资源版权保护等造成了严重影响。为了能够查出电子文档是否存在抄袭现象，越来越多的学者关注于抄袭检测工具的研发，因此，相应的检测算法研究也变得更加重要。根据检测技术的特点，近年来现有的抄袭检测算法包括语义知识、词频统计和数字指纹[1]。基于语义知识的检测算法是使用某种方式表示出文本的语义特征，然后进行文本抄袭检测。词频统计方法是将文本表示为词频向量，在此基础上，利用余弦公式或者内积公式进行文本的相似度检测。虽然以上两种算法的检测结果准确度较高，但是不能很快检测出抄袭文本，不适用于大规模文本集的抄袭检测。近几年，数字指纹技术应用范围越来越广，常用于文本水印、图书馆资源版权保护、视频资源保护等领域[4]。基于数字指纹技术的抄袭检测算法核心思想是：首先根据某种文本块划分策略，从文本中选择一部分字符串（又叫指纹;），然后将其映射为哈希表中的数值，通过计算哈希表中相同的数字指纹数量或者所占总的数字指纹比率来得出文本间的重叠度。由于近似的文本将被映射为近似的指纹，数字指纹技术可以使原文本转换为数字指纹序列，通过计算两个文本的数字指纹重叠度，从而实现文本抄袭检测的目的。其优势是减少了数字指纹的存储空间小、检测速度较快，能够适用于大规模文本集抄袭检测。因此，基于数字指纹的文本抄袭检测不仅在网页去重和信息检索等领域中发挥着举足轻重的作用，也能够应用于图书馆资源保护、软件著作权保护、数据泄漏防护和垃圾邮件过滤等多个领域。特征提取结果的好坏和数字指纹的数量直接影响了文本抄袭检测的效果和计算效率，基于数字指纹的文本抄袭检测存在文本特征数量较多、代表性不强和数字指纹密度大的问题，因此，为了减少文本特征和数字指纹密度、加快检测速率和提高检测结果准确度，研究文本特征选择和数字指纹提取具有重大意义和价值。...........1.2 国内外研究现状目前互联网中电子文档非法传播现象越来越多，因此，不少机构对文本抄袭检测的需求大幅增加，诸多学者对自然语言文本抄袭检测提出了不同的方法。文本抄袭检测的研究最早是由 20 世纪 70 年代初开始的[5]，到目前该研究获得了一定的应用和理论成果。它最初是用于代码抄袭检测，然后是垃圾邮件过滤，后来人们提出将其应用在数字资源版权保护，表明了文本抄袭检测的研究具有一定的应用价值。文本抄袭检测能够通过各种各样的算法来实现，对于不同的应用范围，所使用的算法也不尽相同。由于文本特征提取时使用方式的不同，我们可以将其分为以下两个类别，数字指纹和词频统计。虽然文本特征提取的方式不同，但是这些方法都有一个相同的流程框架，如图 1.1 所示。两类方法的不同之处在于其对应生成的文本特征表示形式和相应的相似度计算方法。国内研究者也提出了一些抄袭检测系统和方法。早在二十世纪末，Si 等人就开发了 CHEC[14]原型系统，采用引进文本的章、节、段落等组织结构，并所建的树形文本结构统计节点中的关键词频的方法，通过词频的比较进行相似度判断。在此基础上，宋擒豹等人研发了 CDSDG 系统[15]，此系统类似于 CHEC 原型，也考虑了文本的树形结构，但是对两个结点进行衡量时，既要衡量两个结点的语义相似程度，又要衡量结构的相似程度。针对特征词数量大、耗时较高的问题，鲍军鹏等人提出了高频向量 HFV 和高包含频率 HIPM 用于文本抄袭检测[16]，该算法利用 HFV 能够检测出子集的相似程度，HIPM 能够降低计算复杂度并节省空间，但是，该算法并未考虑低频词语对文本的影响，检测准确度不理想。基于词频统计的文本抄袭检测算法需要对关键词进行统计并形成文本特征向量，从而进行相似度对比，该算法过程易于理解，但是较多关键词易导致向量维度较高，容易造成维度灾难;，从而影响抄袭检测结果的准确度。而且，该方法在大规模的文本检测环境下，耗时较高。.........第 2 章 文本抄袭检测概述文本抄袭检测是通过某种算法来衡量两篇或者多篇文本间的相似度，进而判断文本是否通过某种手段窃取了其他文本内容[38]。2.1 文本抄袭检测概述2.1.1 文本抄袭检测定义文本内容的表现形式越来越多样化[39]，它不仅包含了文本，也包含了图片、表格、数学公式等，根据内容形式的不同，文本抄袭检测通常分为程序代码抄袭检测和自然语言抄袭检测。计算机程序通常有其明确的组织结构和语法规范，相关研究也较自然语言抄袭检测更早。自然语言文本却通常是由字符流组成，不具备明显的结构特征，该特性决定了其抄袭不易发现，与程序检测相比该文本类型的检测比较困难。本文主要是以自然语言作为研究对象。在进行文本抄袭检测研究之前，我们首先应该明确文本抄袭的概念。所谓文本抄袭，又称文本复制，也有人称文本剽窃，是指将他人的文本通过某种手段据为己有[38]。抄袭，不仅仅是一字不落的拷贝原文，也包含在原文内容的基础上对其所做的更改[39]。aren Fullam[40,41]把文本抄袭手段分为完全复制、段落复制、经典话语复制、同义词替换复制和经典话语结构改变的复述。其检测的难易程度如图 2.1所示：常见的抄袭检测算法是通过提取的文本特征信息，并将其与数据库中文档进行相似度对比，如果超过一定的阈值那么就认为它是抄袭的。文本抄袭检测的目的是发现存在抄袭的文本，对文本进行有效的组织和管理，便于文本资源的管理，可以针对不同的应用环境采取不同的处理措施，通常可以用于网页的去重、论文抄袭检测、知识产权保护、大型文件系统管理。.........2.2 基于数字指纹的文本抄袭检测流程在文本抄袭检测中，数字指纹技术首先将一个文本依据一定的分块策略划分，把文本块中映射为一系列的哈希值作为数字指纹，然后把计算相关指纹的重叠度。在基于数字指纹的抄袭检测算法中，通常包括文本预处理、数字指纹特征提取以及相似度计算等重要部分，其具体过程如图 2.4 所示：首先，进行文本预处理。通常包括删除与文本不相关的字或者词语，比如一些句号、逗号或者停用词等，对文本格式进行统一转换等操作，以减少所产生的相应数字指纹对相似度判断的影响。采用的数字指纹提取方式不同，其相应的预处理操作通常也会有明显差异。其次，数字指纹特征提取。主要是对预处理过的文章按照选定的粒度进行文本块划分进行特征提取，然后使用哈希算法生成数字指纹，接下来进行数字指纹提取，根据某种的数字指纹选取策略（比如选择全部、部分的数字指纹）选出部分数字指纹作为文本相似度比较的依据。最后，根据上一步所选的数字指纹衡量两个文本间的相似度，如果超过给定阈值则存在抄袭情况。............第 3 章 基于依存句法的特征提取算法.....173.1 问题的提出......... 173.2 依存句法简介..... 183.3 基于依存句法的特征提取模型.... 193.3.1 构建新的依存句法结构..... 203.3.2 基于依存句法的文本特征提取模型............ 213.4 本章小结.... 24第 4 章 基于 Winnowing 的数字指纹提取算法..........254.1 Winnowing 算法........... 254.2 基于 Winnowing 的数字指纹提取算法......... 264.3 数字指纹密度分析...... 324.4 本章小结.... 33第 5 章 实验结果及分析...........345.1 实验准备.... 345.2 评价指标.... 355.3 基于句法框架的特征提取算法实验..... 365.3.1 文本特征数量分析.... 365.3.2 基于改进算法的抄袭检测分析........... 375.4 基于 Winnowing 算法的数字指纹提取实验.......... 395.5 本章小结.... 44第 5 章 实验结果及分析为了验证本文所提出的文本特征提取算法和数字指纹特征提取算法的有效性，我们将查准率、查全率和 F1值作为衡量指标。5.1 实验准备在本实验中，使用 Python 爬取新闻网站上的语料，一共搜集了 9487 篇新闻，分为历史、军事、文化、读书、教育、IT、娱乐、社法等八个类别。每篇文本都是经过提取正文内容得到的 txt 格式的文本语料，文件大小为 1 B 8B，96%的文件在 3 B 5B。为了构造抄袭文本集，我们通过人工判断和计算机检测，从 9487 篇新闻中随机选取 1000 篇不存在抄袭的文本作为原生文本，然后通过不同的抄袭形式对其内容进行更改。所构造的文本语料包含以下数据集：Raw Data：1000 篇原生文本；P1-data：完全复制。随机从 Raw Data 选取 10 份文件，不改变文件内容，得到 10 份抄袭文档。P2-data：增删操作。随机从 Raw Data 选取 10 份文件，对其增加词语后得到抄袭文件 10 份；删除词语后得到修改样本 10 份；总共 20 份抄袭文本。P3-data：同、近义词替换。随机从 Raw Data 选取 10 份文件，根据同义词词库将文件中的存在同义词的内容进行替换操作，得到 10 份抄袭文本。P4-data：修改操作。随机从 Raw Data 选取 10 份文件，改变这些文件的经典话语的先后位置得到 10 份抄袭样本；改变文件内容的整个段落的先后位置得到 10份修改样本；重述得到 10 份样本；总共 30 份抄袭文本。P5-data：文本拼凑。随机从 Raw Data 选取 10 份文件，经过几个文本拼接产生10篇抄袭文本；从一个文件中随机选择几个段落重新组合产生10篇样本集；总共 20 篇抄袭文本.

........总结本文主要对数字指纹提取过程中所用到的算法做了两点改进，一是利用经典话语粒度划分和词语间依存关系改进了文本特征提取算法，一定程度上解决了传统算法对依存句法关系考虑不足的问题，在降低了冗余的无效特征数量的基础上，保证了算法的可靠性；另外一点是提出了一种改进的 Winnowing 算法，结合Winnowing 滑动窗口机制，利用最优决策模型和最优约束条件对文本的数字指纹进行提取，有效降低了数字指纹的密度。目前完成的工作有如下几个方面：（1）由于中文汉字的数量繁多和文本编码方式的多样性，本文为了解决中文编码间不同格式在进行哈希映射时结果不同的问题，建立了中文编码模型，来对中文文本的进行编码转换。（2）本文借鉴中文句法结构，根据句法依存关系合并一些能够组合的词语，建立句法框架，将句法框架与数字指纹技术结合起来，提出了基于句法框架的文本特征提取算法。该算法通过句法分析构建句法框架，提取出具有代表性的组合词，有效降低了指纹数量。（3）对 Winnowing 特征提取算法进行了研究和分析，为了解决 Winnowing在提取指纹特征时，选取的特征数量较多，指纹特征密度较大的问题，对Winnowing 算法进行了改进，改进的算法结合了最优决策模型和最优约束条件，将指纹的选取固定在一定的区间范围内，消除了重叠窗口的数字指纹选取情况，了降低数字指纹密度。..........参考文献（略）