基于提取关键词的中文文档复制检测研究

CN4321258/ TP ISSN 10072130 X计算机工程与科学COMPU TER EN GIN EERIN G & SCIENCE2007 年第 29 卷第 10 期Vol129 ,No110 ,2007文章编号 :10072130X(2007) 10200632023基于提取关键词的中文文档复制检测研究Research o n Chinese Document Cop yDetection Based on Ext ractingKey Words麻会东 ,刘国华 ,李 旭 ,梁 鹏 ,刘春辉 ,张凌宇MA Hui2dong ,L IU Guo2hua ,L I Xu ,L IANG Peng ,L IU Chun2hui , ZHANGLing2yu ( 燕山大学信息科学与工程学院 ,河北 秦皇岛 066004)( School of Inf ormation Science and Engineering ,Yanshan University , Qinhuangdao 066004 , China)摘 要 :文档复制检测技术在保护知识产权和信息索引中起重要作用 ,它可以防止剽窃事件的发生 ,提高互联网检索 效率 。目前 ,英文复制检测技术已经比较成熟 ,但中文复制检测技术研究还处于起步阶段 。本文提出一种基于关键词的指 纹提取方法 ;提出 k2words 方法分解句子 ;定义了数字指纹树概念 ,并用数字指纹树来存储指纹 。最后 ,用实验验证了所提 出的方法 。Abstract :The technique of copy detection plays an important role in intellectual property protection and information re2 t rieval ,which can prevent plagiarism and improve the retrieval efficiency of the Internet. Now ,the copy detection technique of English has become mature. However ,the copy detection technique of Chinese is in the first step . An extracting finger2 printing method based on key words has been proposed. The K2w ords method is proposed to decompose sentences. The con2 cept of digital fingerprinting t ree which is used to store the fingerprints has been defined. Finally ,the method is validated byexperiments.关键词 :指纹 ;剽窃 ;文本块 ;匹配Key words :fingerp rint ;plagiarism ;chunk ; match中图分类号 : TP309文献标识码 :A1引言因特网的飞速发展使得文档唾手可得 ,为人类共享知 识和创造提供了前所未有的便利 。但是 ,文档的易获性使 得非法复制行为越来越猖獗 。这种行为不仅危及着作者的 切身利益 ,而且影响了科学文化的健康发展 。文档复制检测 ,就是判断一个文件的内容是否抄袭 、剽 窃或者复制于另外一个或者多个文件 ,剽窃不仅仅意味着 原封不动地照搬还包括对原文内容的移位交换 、同义词替 换 、说法重述等 。文档复制检测技术不仅是检测剽窃的有力手段 ,还可 以应用在数字图书馆 、互联网 、网上论文提交系统等来发现 重复文档 。英文文档相似性研究开始于 90 年代 。根据提取文档 指纹的方式将文档复制检测方法分为基于词频统计的方法和基于字符串匹配的方法 。2英文文档复制检测的相关工作21 1基于词频统计的方法该方法借鉴了向量空间模型 1 思想 ,根据词频构成整 篇文档的特征向量 ,然后用点积 、余弦公式等度量文档的相 似度 。采用此方 法具有代表性的系统是 1995 年 Garcia2 Molina 等人提出的 SCAM 2 、2001 年西安交通大学宋擒豹 等人提出的 CDSD G( Copying Detection System of Digital Goo ds ,简称 CDSD G) 1 系统 。基于词频统计的方法忽视 了文档上下文的语义关系 ,同义词 、语义重述等在内容思想 上的重叠不能检测出来 。21 2基于字符串匹配的方法基于字符串匹配方法的一般思想是 :首先按照一定粒3 收稿日期 :2007203229 ;修订日期 :2007207209作者简介 :麻会东(1980 ) ,女 ,河北秦皇岛人 ,硕士生 ,研究方向为数据库安全和信息安全 ; 刘国华 ,教授 ,博士生导师 ,研究向数据 库理论和数据库安全。通讯地址 :066004 河北省秦皇岛市燕山大学信息工程与科学学院 ; Tel ; E2mail : huidongma 126. comAddress :School of Information Science and Engineering , Yanshan University ,Qinhuangdao , Hebei 066004 , P. R. China63度将文档分解成文本块序列 ,再将这些文本块序列进行压 缩编码 ,全部或抽取部分作为文档的数字指纹与数据库中 已注册文档的指纹进行匹配 。具有代表性的是文献 3 中 的 COPS( Copy Protection System ,简称 COPS) 系统 ,系统 将所有句子序列进行 Hash 编码 。但是 ,COPS 原型系统不 能发现句子的部分重叠 。其次是 2000 年 Monostori 等人 建立的 MDR 4 (Match Detect Reveal ,简称 MDR) 原型 ,此 原型采用后缀树或后缀向量来搜索字符串间的最大子串 。 这种方法存储空间需求很大 ,字符串间的匹配时间较长 。 2003 年 ,Saul Schleimer 等人提出 Winnowing 5 指纹提取的 算法 ,采用 k2g rams 方法分解文档 ,利用滑动窗口提取指 纹 ,在每个窗口中选择最小的 Hash 值作为指纹 。此算法 分解后的文本块序列没有实际语义 ,存储开销太大 。3中文文档复制检测技术31 1中文文档复制检测研究现状国内对中文文档复制检测技术起步较晚 。2005 年 ,大 连理工大学的金博 6 等人提出一个基于语义理解的中文复 制检测系统 。该系统首先将文档中的词汇通过语义词典转 换成语义集合 ,然后根据语义之间的关系将语义集合用语 义树表示出来 ,最后将待检测文档生成的语义树和已注册 文档的语义树作比较 ,得出两篇文档的相似度 。由于受语 义理解技术的影响 ,这种方法检测的准确性还较低 。字是汉语中最小的语言单位 ,词是有语义的最小语言 单位 。在书写上 ,词与词之间没有空格符 ;汉语中动词 、名 词 、形容词是句子的主要成分 ,在词典中各占较大比重 ,而 副词 、介词等比重较低 ,使用频率也很低 ;汉语“形异义同” 情况较多 。本文根据汉语语言特点和中文文档复制检测应 满足的特性 ,提出基于抽取关键词的中文文档复制检测 。31 2中文文档复制检测过程本文提出基于抽取关键词的中文文档复制检测方法 ,检测过程主要分为预处理 、指纹提取和指纹匹配 。(1) 预处理 。义词有相同的编码) ,将篇 、段落 、句子和文本块序列通过 Hash 函数映射成数字 (称为数字指纹) ,选择“滚动”而且 冲突最小的 Hash 函数 。指纹表示与存储 。数字指纹树是一棵 B - 树 ,存储 不同粒度的数字指纹 。待检测文档篇的指纹树的结点 Root(V al , P) ,其中 V al 是整篇文档的数字指纹 , P 指向所 有段落生成的指纹树 ;段落的指纹树的结点 Par( V al i , S i , C) ,其中 V al i 是第 i 个段落的数字指纹 , S i 是第 i 个段落 所有句子生成指纹树 , C 指向其他段落结点 ; 句子的指纹树 的结点 Sen(V al i , Ki , C) , 其中 V al i 是第 i 个句子的数字指 纹 , Ki 指向此句子对应的文本块的指纹树 , C 指向其他句 子结点 ;文本块的指纹树的结点 Chu( V al , C) , 其中 V al 是 文本块的指纹 , C 指向其他的文本块结点 。其中 , 段落的指 纹树如图 1 所示 。图 1 段落指纹(3) 指纹匹配 。已注册文档各指纹树生成的方法与待 检测文档的指纹树生成方法相同 。待检测文档与其匹配时 首先从篇的指纹树进行比较 ,若两文档篇的指纹相同 ,则认 为待检测文档是完全复制的 。篇的指纹不同 , 则顺指针找 到段落所在的指纹树并遍历整棵树 , 具有相同指纹的段落 记录其位置信息 , 段落匹配计数器加 1 。若段落的指纹不 同 ,找到其句子的指纹树并遍历句子指纹树 ,指纹相同的句 子记下其位置信息 , 句子匹配计数器加 1 。句子指纹不同 的找到此句对应文本块的指纹树 , 直到遍历完段落树时整 个匹配任务完成 , 统计所有计数器的数值 , 根据公式 ( 1) 、 (2) 和 (3) 计算出不同粒度的相似度 ,由公式 (4) 得出两篇文 档的相似度 。如果相似度大于阈值 Q , 则认为待检测文档 是剽窃的 ,否则将作为一篇新文档注册到数据库中 。段落相似度 :spi| Dp Rp|文档格式转换 。检测前先将各种格式存在的文档转Sim ( Dp , Rp ) = | S u m |(1)换为统一识别的格式 。i = 1| Sums |不敏感信息处理 。进行繁简体和大小写转换 ,去掉 常用习语和长度小于用户设定的阈值 m 的句子 。(2) 指纹提取 。提取关键词 。提取句子中名词 、动词 、形容词代表整其中 , | S ums | 、| S umspi | 分别表示待检测文档包含的句子总数和重叠段落 (第 i 个) 包含的句子总数 , | Dp Rp | 表示两 篇文档中段落指纹相同的个数 。句子相似度 :个句子 ,提取前采用正向最大匹配和词性标注同时进行的 方法分词 。Sim ( D , R= | Ds Rs |ss )| Sums |(2)k2w ords 分解句子 。分解句子的目的是发现句子的 部分重叠 。k2words 方法分解句子的思想是 :将具有语义 的词作为最小单位 , 连续 k 个词构成一个文本块 ,相邻的两 个文本块重叠 k - 1 个词 ,将每个句子分解成 l - k + 1 个文其中 , | Ds Rs | 表示待检测文档与已注册文档句子指纹相同的句子总数 (不包含段落指纹相同的句子) , | S ums | 表示 待检测文档包含的句子总数 。文本块相似度 : c Rc |本块 ( l 为句长) 。例如 , 经过预处理之后的句子 : ( 保护)Sim ( Dc , Rc) = | D| Sumc |(3)(信息) (所有者) ( 知识) ( 产权) 。设 k = 3 , k2words 分解之后为 : (保护) (信息) (所有者) , (信息) (所有者) (知识) , ( 所 有者) (知识) (产权) 。Hash 编码 。根据每个词汇在词典中的唯一编码 (同其中 , | Dc Rc | 表示待检测文档与已注册文档的文本块指 纹相同的文本块总数 ( 不含段落指纹和句子指纹相同的那 些文本块) , | S umc | 表示待检测文档中文本块总数 。(下转第 88 页)息 、对象数据的超链接 。表 1 文档粒度信息统计表5结束语原文档 长度 抽取关 键词后 句子 总数 平均句 子长度 句子包含 词个数 随着电子商务与电子政务的迅速发展 , WWW 上不断 出现大量的数据信息 ,互联网上存在大量的数据传输和交 换需求 ,而这些大量交换与处理的数据是以异构的方式存 在的 。所以 ,要实现互联网上的电子商务 ,必须提供一个异 构信息的融合平台 ,屏蔽下层的数据细节 ,为用户提供一个 统一友好的访问接口 ,方便用户交互和共享海量 、异构 、复 杂的信息资源 。针对电子商务平台信息融合的特点 ,本文探讨并研究 了信息融合中异构数据的语义集成及关键技术 ,提出了一 类基于 XML 的电子商务平台异构信息的语义集成方案 。 由于 XML 的特点 ,本系统模型具有良好的可扩充性 ,它可 以集成新的数据源 ,而不用对系统做大的变动 。参考文献 : 1 Levy A Y. Logic2Based Techniques in Data Integration A . Minker J ,ed. Logic Based Artificial Intelligence M . Kluwer Publishers ,2000 . 2 Draper D ,Levy A Y , Weld D S. The Nimble XML Data Inte2gration System A . Proc of t he Intl Conf on Data Engineer2 ing C . 2001 . 3 Haley A. Enterprise Information Integration : Success , Chal2lenges , and Controversies A . Proc of ACMSIGMOD 05 C . 2005 . 4 Yuan J . Semantic2Based Dynamic Enterprise Information In2tegration A . Database Modeling for Industrial Data Manage2 ment Emerging Technologies and Applications M . Idea GROU P Publishing ,2006 .(上接第 64 页)最后 ,由式 (4) 得出两篇文档之间的相似度 :Sim ( D , R) = Sim ( Dp , Rp ) + Sim ( Ds , Rs ) + Sim ( Dc , Rc)(4)31 3检测的准确性影响准确性的因素分为正误差 、负误差 。 假设冲突检测能够检测出两篇文档的所有重叠信息 。令 X 表示从待检测文档中随机抽取的一篇文档 , Y 是从数 据库中已注册文档中随机抽取的一篇文档 , P 表示概率 , t1 表示剽窃检测 , t2 表示冲突检测 。(1) 正误差指实际上没有剽窃别人内容的文档经过复 制检测被认为是剽窃了别人内容的概率 。计算公式为 Be2 ta( t1 , t2 ) = P( t2 ( X , Y) | t1 ( X , Y) ) 。(2) 负误差指实际上是剽窃别人内容的文档检测中没 有检测出来而被认为没有剽窃别人内容的概率 。计算公式 为 A l pha( t1 , t2 ) = P( t2 ( X , Y) | t1 ( X , Y) ) 。4实验实验选取期刊论文 5 000 篇 , 经过统计得到一些如表 1所示的原文档和预处理后文档粒度信息 。7 5366 60022030136 6535 6803601693 5672 80023019109 9808 5055952811期刊论文经过处理后平均长度为 6 500 个字 ,句子平 均长度为 20 个字 ,平均每个句子切分的词汇个数是 8 个 , 假定句子长度小于 6 个字的是不敏感信息 。在句子分解过 程中 , k 值的大小与产生的文本块个数成反比 ,与丢失部分 匹配几率 、存储文本块的空间开销以及匹配计算时间成正 比 。为了达到更好的检测结果 ,进行了多次实验 ,最终发现 k = 4 是最优选择 。实验中首先注册了几篇文档 : a. txt 、b. txt 、c. txt 、d. txt 和 e. txt ,又选取几篇相近文档作为代检测 文档 。其中 , f . t x t 的检测数据如表 2 所示。表 2 检测结果% 检测文档 检测项目a. txtb. txtc. txtd. txte. txt篇相似度00000段落相似度11051510句子相似度916203024文本块相似度2123264043与此文档相似度4139518577正误差34512负误差23231 显然 ,本文采用的检测方法准确度能达到 90 %以上 。5结束语本文提出了基于提取关键词的中文文档复制检测方 法 ,通过实验验证该方法能够有效地进行中文文档复制检 测 。但是 ,由于受 Hash 函数冲突和分词准确率的影响 ,使 得检测结果还存在一定噪声 。未来的工作就是寻求冲突更 小的 Hash 函数以及进一步完善分词技术 。参考文献 : 1 Song Q B ,Shen J Y. On Illegal Copying and Distributing De2 tection Me