（计算机应用技术专业论文）网页查重算法研究.pdf

摘要 i n t e m e t 的迅速普及和飞速发展，使人们面临着一个信息的海洋，快速从中 获得真正重要的信息变得至关重要。搜索引擎( 主要指全文搜索系统) 即是提供 这种功能的一种工具。然而在搜索引擎返回的检索结果中，存在大量的重复网 页，它们主要来自网站之间的转载。这些内容重复的网页既占用了网络带宽， 又浪费存储资源，用户不希望看到一堆内容相同或近似的检索结果，真正有用 的结果往往淹没在这些重复信息之中而不易被发现。如果能够有效消除这些重 复网页，不但会提高检索的准确率，节省用户的时间和精力，而且对搜索系统 本身而言可以节省网络带宽，降低存储成本，提高搜索引擎的性能。 本文主要研究搜索引擎中网页查重的问题。首先简要介绍了搜索引擎的原 理，发展现状，存在的不足和发展趋势，以及本课题研究的背景和意义。其次 对当f i i 国际和国内相关领域的研究动态进行了深入的分析，详尽介绍了网页查 重算法的起源和研究历史，网页查重算法的分类及各个分类的代表性算法，这 些算法对原有算法的改进、性能和优缺点。其中着重介绍了非常优秀和经典的 算法s h i n g l i n g 和s i m h a s h ，许多算法都是基于这两种算法的思想进行的改进。 g o o g l ej 下是利用s i m h a s h 来实现网页查重。c h a r i k a r 的s i m h a s h 算法对检测数力 亿的存储级别的相似网页是非常实用的。作为指纹技术的s i m h a s h 具有相似文 档的指纹只存在很小位数的不同的特性。s i m h a s h 是一种降维技术，可以将高 维向量映射为位数较小的指纹。它在网页中的应用过程如下：首先将文档转化 为特征码的集合，每个特征码附有一个权值。特征码的生成采用i r 技术，比如 分词、大小写转换、停止词去除。一个附有权值的特征码的集合构成一个高维 向量，通过s i m h a s h 可以将这个高维向量转化为f 位的指纹，f 的值很小，比如 6 4 。最后详尽介绍了在很多重要的项目中广泛应用并取得一致好评的丌源项目 c l u c e n e ，以及如何利用c l u c e n e 建立自己的搜索引擎系统，进行索引和检索查 询。c l u c e n e 提供了丰富的a p | 函数， 利用这些a p i 函数可以方便的建立自己 的搜索引擎系统。详细介绍了主要的类，数据结构，系统结构及如何实现索引， 搜索和分析。 关键字：搜索引擎，网页查重，s h i n g l i n g ，s i m h a s h a b s t r a c t t h er a p i dp o p u l a r i z a t i o na n dd e v e l o p m e n to fi n t e m e tm a k e sp e o p l ef a c ea s e a o fi n f o m a t i o n i tb e c o m e se s s e n t i a lt oo b t a i nr e a l l yi m p o r t a n ti n f o r m a t i o nf r o mi t t h es e a r c he n g i n e ( m a i n l yr e f e r r e dt ot h ef u l lt e x ts e a r c hs y s t e m ) i sak i n do ft o o lt h a t p r o v i d e st h i sf u n c t i o n h o w e v e r , i nt h er e t r i e v a lr e s u l t sf r o mt h es e a r c he n g i n e ，t h e r e a r eal a r g en u m b e ro fd u p l i c a t e dw e bp a g e sw h i c hm a i n l y c o m ef r o mt h e r e p r o d u c t i o na m o n g t h ew e b s i t e s t h o s er e p e t i t i v ew e bp a g e sn o to n l yo c c u p yt h e n e t w o r kb a n d w i d t hb u ta l s ow a s t es t o r a g er e s o u r c e s u s e r sd on o tw a n tt os e eap i l e o fs e a r c hr e s u l t sw i t ht h es a m eo ra p p r o x i m a t ec o n t e n t s ，a n dt r u l yu s e f u lr e s u l t sa r e o f t e nd r o 、v n e di n t h i sr e d u n d a n ti n f o r m a t i o na n dc a n t b ee a s i l yd i s c o v e r e d e f f e c t i v er e m o v a lo ft h o s ed u p l i c a t ew e bp a g e sw i l le n h a n c et h ea c c u r a c y i n s e a r c h i n ga n ds a v et i m ea n de n e r g yf o ru s e r s s ot h a tt h e s e a r c hs y s t e mi t s e l fc a n s a v et h en e t w o r kb a n d w i d t h ，r e d u c et h es t o r a g ec o s ta n de n h a n c et h eq u a l i t yo ft h e s e a r c he n g i n e 。 t h i sp a p e rm a i n l ys t u d i e st h ep r o b l e mo fr e m o v i n gd u p l i c a t e dw e bp a g e sf o r s e a r c he n g i n e f i r s to fa l l ，g i v eab r i e fi n t r o d u c t i o no ft h ep r i n c i p l eo ft h es e a r c h e n g i n e ，t h ed e v e l o p m e n ts t a t u s ，t h ee x i s t i n gd e f i c i e n c ya n dd e v e l o p m e n tt r e n d ，a s w e l la st h er e s e a r c hb a c k g r o u n da n ds i g n i f i c a n c e s e c o n d l y , g i v ead y n a m i ca n d d e e pa n a l y s i so nc u r r e n ti n t e r n a t i o n a la n dd o m e s t i c - r e l a t e dr e s e a r c hi nt h i sf i e l d ，a l s o ad e t a i l e dd e s c r i p t i o no ft h eo r i g i na n dh i s t o r yo ft h en e a r - d u p l i c a t e d e t e c t i o n a l g o r i t h m t h ec l a s s i f i c a t i o no ft h ea l g o r i t h ma n d i t sr e p r e s e n t e da l g o r i t h m ，i n c l u d i n g t h ee f f i c i e n c y , a d v a n t a g e ，d i s a d v a n t a g ea n dt h ei m p r o v e m e n t so ft h ea l g o r i t h m s a t t h es a m et i m e ，f o c u s e do nt w og r e a ta n dc l a s s i ca l g o r i t h m ，s h i n g l i n ga n ds i m h a s h ， m a n yo t h e ra l g o r i t h m sa r eb a s e do nt h e i ri d e at oc a r r yo u ti m p r o v e m e n t s g o o g l e e x a c t l yu s es i m h a s ht o a c h i e v en e a r - d u p l i c a t ed e t e c t i o n s i m h a s hi sp r a c t i c a l l y u s e f u lf o ri d e n t i f y i n gn e a r - d u p l i c a t e si nw e b d o c u m e n t sb e l o n g i n gt oam u l t i b i l l i o n p a g er e p o s i t o r y s i m h a s hi saf i n g e r - p r i n t i n gt e c h n i q u et h a te n j o y st h ep r o p e r t yt h a t r i n g e r p r i n t so fn e a r d u p l i c a t e sd i f f e ri nas m a l ln u m b e r o fb i tp o s i t i o n s s i m h a s hi sa d i m e n s i o n a l i t yr e d u c t i o nt e c h n i q u e i tm a p sh i g h - d i m e n s i o n a lv e c t o r st os m a l l - s i z e d f i n g e r p r i n t s i ti sa p p l i e d t ow e b p a g e sa sf o l l o w s ：f i r s tc o n v e aaw e b 。p a g ei n t oa s e t o ff e a t u r e s ，e a c hf e a t u r et a g g e dw i t hi t sw e i g h t f e a t u r e sa l ec o m p u t e du s m g s t a n d a r di rt e c h n i q u e sl i k et o k e n i z a t i o n ，c a s ef o l d i n g ，s t o p w o r dr e m o v a l ，s t e m m i n g a n dp h r a s ed e t e c t i o n as e to fw e i g h t e df e a t u r e sc o n s t i t u t e sah i g h - d i m e n s i o n a l v e c t o r , w i t ho n ed i m e n s i o np e ru n i q u ef e a t u r ei na l ld o c u m e n t st a k e nt o g e t h e r w i t h s i m h a s h w ec a nt r a n s f o r ms u c hah i g h d i m e n s i o n a lv e c t o ri n t oa nf - b i tf i n g e r p r i n t w h e r efi ss m a l l ，s a y6 4 f i n a l l y , g i v ei n t r o d u c t i o na td e t a i lo nao p e ns o u r c ep r o j e c t w h i c hi sa p p l i e di nm a n yi m p o r t a n tp r o j e c t sa n dr e c e i v eu n a n i m o u sp r a i s e ，c l u c e n e ， a n dh o wt ob u i l ds e a r c he n g i n eb yc l u c e n et oi n d e xa n ds e a r c h c l u c e n ep r o v i d e a b u n d a n ta p if u n c t i o n s ，a n dw ec a nb u i l ds e a r c he n g i n ee a s i l yt h r o u g ht h e s ea p i f u n c t i o n s i l l u s t r a t ei nd e t a i lt h em a i nc l a s s e s ，d a t as t r u c t u r e ，s y s t e ms t r u c t u r ea n d h o wt oa c h i e v ei n d e x s e a r c ha n da n a l y z e k e y w o r d ：s e a r c he n g i n e ，n e a r - d u p l i c a t ed e t e c t i o n ，s h i n g l i n g ，s i m h a s h 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权武汉理工大学可以将本学位论文的全部内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存或汇编本学位论文。同时 授权经武汉理工大学认可的国家有关机构或论文数据库使用或收录本学位论 文，并向社会公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：师( 签名) ：日期： 武汉理l ：人学硕十学何论文 第1 章绪论 1 1 研究的现状和背景 1 1 1 搜索引擎原理概述 搜索引擎( s e a r c he n g i n e ) 是指根据一定的策略、运用特定的计算机程序搜 集互联网上的信息，在对信息进行组织和处理后，为用户提供检索服务的系统。 搜索引擎同益成为人们漫游互联网不可或缺的工具。按照技术原理，搜索引擎 分为三大类：全文检索搜索引擎、目录搜索引擎和元搜索引擎。 全文检索( f u l lt e x ts e a r c h ) 是指计算机索引程序扫描文章中的每一个词，为 每一个词建立索引，指明该词在文章中出现的位置和频率，当用户查询时，检 索程序就根据预先建立好的索引进行查找，并将结果返回给用户。这个方式类 似于通过字典前面检索字表查字的过程。采用全文检索的搜索引擎有自己的检 索程序和索引数据库。这类搜索引擎的代表有g o o g l e 、a l t av i s t a 、百度、北大 天网、中搜等。 目录搜索引擎( s e a r c hi n d e x d i r e c t o r y ) 通过人工建立数据库，由专业编辑挑 选和分类的网站结果。它将众多的网页资料分f - j 另t j 类，层层分级。例如新浪的 分类目录就是采取这种方式。著名的目录搜索引擎y a h o o 及搜狐等也采用这种 方式。但它并不是真j 下意义上的搜索引擎。 元搜索引擎( m e t as e a r c he n g i n e ) 不用进行互联网的遍历和爬取，也没有自己 的资源数据库，它充当一个中问代理的角色，提供一个统一的检索界面，在用 户查询时，将用户的查询条件提交给其他的搜索引擎，将这些搜索引擎的返回 结果汇总整理后返回给用户。例如圣博牛搜就是这样的搜索引擎，它将用户的 查询提交给g o o g l e 、百度、有道等搜索引擎。元搜索引擎因为涉及到多个搜索 引擎的数据库从而扩大了用户的查询范围。 一般来讲，一个搜索引擎主要包括搜索、分析索引、检索和用户接口四个 部分。 搜索引擎的搜索功能主要由一个叫做网页搜索器的程序来实现，它又叫做 武汉理l ：人学硕十学何论文 网页蜘蛛( w e bs p i d e r w e bc r a w l e r ) 或者网页机器人( r o b o t ) 。它可以自动在网络 上漫游，从预先定制的u r l 列表出发，自动访问w e b 站点，并将访问的w e b 站点中连接信息分析提取加入到u r l 列表，然后根据u r l 列表进一步访问其 他站点。如此重复同夜不停的搜集网络上的信息，下载并提交给数据库。这一 过程又叫做网页收集，网页爬取等。 分析索引模块将c r a w l e r 爬取到的网页进行比较分析，删除镜像转载等原因 造成的相似及相同网页，对保留的网页进行文档分析，去除h t m l 等的标志符 号，提取网页的相关信息及网页源文件内容，对源文件内容分词并建立索引。 索引是一种将关键词词目映射到相应文档的数据结构。 检索模块的功能是根据用户的查询在索引库中快速检出文档，进行文档与 查询的相关度评价，对将要输出的结果进行排序，并实现某种用户相关性反馈 机制。 用户接口的作用是供用户输入用户查询、显示查询结果、提供用户相关性 反馈机制i lj 。 1 1 2 搜索引擎的现状和不足 3 月5 同，中国互联网络信息中一t 二, ( c n n i c ) 在京发布 2 0 0 8 年搜索引擎研究 报告。报告数据显示，截至2 0 0 8 年底，中国搜索引擎用户规模达到2 。0 3 亿。 现在，搜索引擎已经发展到了第四代。其中第一代以雅虎为代表，通过人 工进行分类归类提供检索功能。第二代的代表是g o o g l e ，通过机器取代人工进 行网页的爬取分析等实现信息检索。第三代以电脑和人的互动为特征，可以根 据用户的输入给出提示信息，可以使用户快速准确的找到想要搜索的信息。第 四代搜索引擎就是主题搜索引擎。通用搜索引擎面对用户提供统一的界面和接 口，但是伴随着信息的飞速增长，这显然不能满足用户更加细致深入的搜索要 求，于是主题搜索引擎应运而生，它分类更加细致准确，信息更加全面深入， 更新也更及时，加入智能化策略，比前几代搜索引擎更加的有效和准确。 尽管搜索引擎发展迅速，但仍然存在着不足和亟待改进的问题。 首先是搜索引擎的抓取和更新速度和网页的增长及更新速度不匹配，更新 不及时。互联网上每同增加更新的网页不计其数，虽然c r a w l e r 可以自动快速 的搜集网页，但仍然相对滞后。对于网上已不存在的网页不能及时删除，因而 出现较多的死链和空链。 2 武汉理i ：人学硕十学位论文 其次是查全率偏低，查准率不高。各个搜索引擎之间自行其事，并不合作 和共享信息，虽然索引的网页数量庞大，但是提供的都是大众化服务，并不能 进行深度搜索，查准率比较低，同时垂直搜索的发展又很缓慢。利用搜索引擎 进行检索时首先要求用户输入检索词，系统首先对用户提问进行分析、处理、 构造出可以操作数据库查询的语句表达式，然后执行查询。由于用户是未受过 用检索语言进行索引训练的。面对这种情况，各家搜索引擎纷纷采用可以支持 以自然语言的自由词检索，选词自由度大，表达方式更随意，交流更具人性化。 但由于自然语言本身的缺陷，如：一词多意、结构化不强等等，再加上现今的 技术还不能很好的支持自然语言检索，一般仍停留在语法层面上，很难实现语 义和语用层面上的检索。若不采用自然语言与控制语言相结合进行检索，便会 降低对用户提问分析的准确性，造成对用户提问理解的偏差，使系统构造的查 询表达式与用户真实想法之间存在差距，使得查询结果不尽人意。而且由于中 文本身的特点，不像英文等其他语言有空格等分隔标志，因此计算机难以识别 句子中字词组合，难以区别有用词和无用词，这就会导致检索出很多不相关的 资料，降低了查准率。 最后，输出的相关信息少，重复信息高。由于搜索引擎采用各自的相关度 排序算法，而不能让用户根据需要选择信息输出的排序方法，排序结果单一。 又由于普遍存在的转载现象，网页的镜像等原因，使得返回的结果存在大量重 复【2 】【3 1 。 1 1 3 搜索引擎的发展趋势 针对上述搜索引擎面临的问题，搜索引擎的发展必将改善这些问题，加深 对自然语言的理解，向着更加智能化和专业化的方向发展，提供更友好的用户 界面，提升用户体验度。 智能搜索引擎。智能搜索引擎是一个基于汉语语法、词的上下文和语义等 中文信息处理技术，自动收集、识别网上的信息，智能化地提取摘要和关键词， 建立索引，提供个性化、专业化信息查询，对不良信息监控、报警的网络信息 自动发现、查询系统，相关技术有： ( 1 ) 加权的启发式搜索方法。系统根据用户配置的领域导向词和资源服务器 所在地域信息，以启发式函数计算每个u r l 的权值，并选择权值高的u r l 优 先访问控制信息资源搜集。 武汉理l ：人学硕十学位论文 ( 2 ) 协同式检索方法。系统不去计算分类项目的相似程度，而是计算用户之 间的相似程度，将其他用户的反应反馈给当前的用户，从而不同地区、专业、 语种、类型的搜索引擎实现数据库有条件共享信息或互相满足对方的信息检索 请求。协同式方法一般用于非文本数据，像电影、音乐等，或用于文本数据的 挖掘，如新闻过滤、电子邮件处理、会议时序安排和娱乐节目推荐等，包括“网 络广播 公司广泛应用的信息推送技术。信息推送是网络公司通过一定的技术 标准或协议，从网上的信息源或信息制作商获取信息，通过固定的频道向用户 发送信息的新型的信息传播技术，是提供信息服务的主要手段。 引入受控语言。自然语言检索由于其灵活性有利于检全率的提高，受控语 言检索由于其规范性和准确性，有利于检准率的提高。多数网络信息检索工具 都采用自然语言标引和检索，检索词是否贴切用户毫无把握，同义词和近义词 得不到控制，最终导致检索结果过多过杂。通过建立同义词典，使用户在提出 一个检索词后可获得一批候选词，用户可以判断、选择其中一部分或全部作为 检索用词，提高信息检索的检全率1 4 j l 引。 垂直搜索引擎的发展，垂直搜索引擎是相对通用搜索引擎的信息量大、查 询不准确、深度不够等提出来的新的搜索引擎服务模式，通过针对某一特定领 域、某一特定人群或某一特定需求提供的有一定价值的信息和相关服务。其特 点就是“专、精、深”，且具有行业色彩，相比较通用搜索引擎的海量信息无序 化，垂直搜索引擎则显得更加专注、具体和深入。 如果能够实现关键词检索、分类浏览检索、概念检索三位一体化，就能大 大提高搜索引擎的检准率和检全率。目前网上绝大多数搜索引擎都使用基于关 键词匹配的全文检索技术。但该技术发展到今天，已不可能从根本上实现检索 结果的质的飞跃，探索智能化、知识化的搜索引擎已经成为十分迫切的要求， 而概念检索就是未来搜索引擎的重要特色。 现有的搜索引擎多采用全文检索技术，其核心是关键字符的机械式匹配。 这种方式的固有缺点是参与匹配的只有字符的外在表现形式，而非它们所表达 的概念。因此，经常出现答非所问、检索不全的结果。另一方面，查询结果 完全依赖于用户所给出的关键字，系统和用户之间并无进一步的交互，也是 造成检索效果比较差的原因之一。概念检索试图突破关键词匹配局限于表面形 式的缺陷，从词所表达的概念意义层次上来认识和处理检索用户的请求。 概念检索的主要内容包括两个方面，即同义扩展检索和相关概念联想检 4 武汉理i ：人。学硕十学f 7 ：论文 索。前者能够提高检索的召回率， 而后者能够加强系统与人的交互，使其具 有一定程度的智能6 1 。 1 2 研究的目的和意义 随着信息时代的到来，尤其是互联网技术的高速发展，网络中信息的数量 呈指数级增长。据统计，互联网上的重复网页约占3 0 - 4 5 ，这其中有由于镜 像转载引起的内容完全相同的网页，也有仅存在微小差别的网页，比如广告， 计数器，时间戳等不同，而这些差别是和搜索的内容无关的。根据中国互联网 络信息中心2 0 0 5 年7 月发布的统计报告显示，用户在回答“检索信息时遇到的 最大问题”这一提问时，选择“重复信息太多”选项的占4 4 。6 ，排名第l 位【7 】。对于搜索引擎来说，重复的网页内容是非常有害的。重复网页的存在意 味着这些网页就要被搜索引擎多处理一次。更有害的是搜索引擎的索引制作中 可能会在索引库罩索引两份相同的网页。当有人查询时，在搜索结果中就会出 现重复的网页链接。所以无论是从搜索体验还是系统效率检索质量来说这些重 负网页都是有害处的。没有用户愿意面对众多内容基本一样的查询结果，浪费 了时间，降低了用户体验度。如果我们能够找出这些重复网页并从数据库中去 掉，就能够节省一部分存储空间，进而可以利用这部分空间来存放更多的有效 网页内容，可以节省网络带宽，减轻网页所在远程服务器的负担，同时也提高 了w e b 检索的质量，即提高查询服务的效率和质量。 武汉理i ：人学硕十学何论文 第2 章网页查重算法概述 2 1 网页查重算法起源 网页查重技术起源于复制检测技术，用来判断一个文件的内容是否存在抄 袭其他文件的技术。 复制检测( c o p yd e t e c t i o n ) 又称剽窃检测( p l a g i a r i s md e t e c t i o n ) ，也有人称为 副本检测( d u p l i c a t ed e t e c t i o n ) ，不但是实施知识产权保护( i n t e l l e c t u a lp r o p e r t y p r o t e c t i o n ) 的一种重要手段，也是提高信息检索( i n f o r m a t i o nr e t r i e v a l ) 效率的一 种手段。所谓复制检测，就是判断一个文件的内容是否抄袭、剽窃或者复制于 另外一个或者多个文件。剽窃不仅仅意味着原封不动地照搬，还包括对原作的 移位变换、同义词替换以及改变说法重述等方式。 文档复制检测分为两类，一类是程序复制检测，另一类是自然语言文本复 制检测。程序复制检测和自然语占文本复制检测有很多方法是相似的，有的检 测工具能够同时检测程序复制和文本复制。例如，悉尼大学w i s e 开发的y a p 3 1 引。 但是，二者也有不同之处：所有的计算机程序都有严格的形式化语法，但是自 然语言文本不受形式化语法限制，含义模糊的表达到处都是；程序中标识名称可 以随意替换而语义不变，但是自然语言中的字词不能任意替换；程序的结构信息 清晰，容易获取，而自然语言文本的结构特征一般不明显。总之，自然语言文 本复制检测技术相对更难一些。 程序源代码复制检测就是判断一段给定的程序代码是否是抄袭、剽窃或者 复制于另一段程序代码的内容，剽窃不仅仅意味着原封不动地照搬，还包括对 原作删除注释、改变所有变量和函数名称、尽可能颠倒相邻语句的顺序、改变 函数块的顺序等操作后作为自己的程序提交。 早在2 0 世纪7 0 年代初，就有学者研究阻止大规模拷贝程序的技术和软件。 目前常用的代码复制检测技术可分为两类：属性计数法( a t t r i b u t ec o u n t i n g ) 和结 构度量法( s t r u c t u r em e t r i c s ) 。 h a l s t e a d 提出的软件科学度量方法是最早和最典型的属性计数法。h a l s t e a d 度量方法以程序中出现的操作符和操作数为计数对象，以它们的出现次数作为 6 武汉理：【= 人学硕十学位论文 计数目标来测算程序容量和工作量。o t t e n s t e i n 在1 9 7 6 年首次将h a l s t e a d 的软 件科学度量方法投入应用，实现了第一个针对于f o r t r a n 程序代码的剽窃检测系 统。但是，单纯的属性计数法抛弃了太多的程序结构信息，导致检测结果的错 误率太高，由其对于非常短小的程序来说是无效的。 v e r c o 和w i s e 在1 9 9 6 年指出，对于仅仅使用属性计数法的检测算法增加向 量维技术来检测剽窃【9 】。m c c a b e 提出的圈复杂度方法是一种典型的结构度量 法。它通过计算执行路径的数量来衡量一个程序中的控制流。圈复杂度只给出 了程序的一个结构特征即控制流，往往需要与其它特征结合使用，因此常作了 属性计数法中的一个度量指标。其他的结构度量法还有分析控制结构、计算代 码嵌套深度、分析数据依赖关系等等。在实际应用中，很多代码剽窃检测系统 将两种度量方法相结合。 自然语言文本复制检测技术的出现比程序复制检测晚了2 0 年。1 9 9 3 年， a r i z o n a 大学的m a n b e r 提出了一个s i f 工具，用于在大规模文件系统中寻找 内容相似的文件。s i f 工具并未明确提出要进行文本复制检测。但是，s i f 工具 提出了“近似指纹( a p p r o x i m a t ef i n g e r p r i n t s ) ”，就是用基于字符串匹配的方法来 度量文件之间的相似性。这个思路被很多后来的文本复制检测系统所采用。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 ) 系统与相应算法。c o p s 系统框架为以后的自然语言文本复制检测系统奠定了基础，后来的检测系统框 架与c o p s 大同小异。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 ( s t a n f o r d c o p y a n a l y s i sm e t h o d ) 原型改进c o p s 系统，用于发现知识产权冲突。s c a 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 n a 和s h i v a k u m a r 等人还在s c a m 的基础上提出了d s c a m 模型，把检测范围从单个注册数据库扩展到分布式数 据库上以及在w e b 上探测文本复制的方法，同期，贝尔实验室的h e i n t z e 开发 了k o a l a 系统用于剽窃检测。k o a l a 系统采用与s i f 基本相同的方法，与之 类似的方法还有b r o d e r 等人提出的“s h i n g l i n g 方法。香港理工大学的s i 和 l e o n g 等人建立的c h e c k 原型采用统计关键词的方法来度量文本相似性。但 是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 ) 原型。m d r 用后缀树( s u f f i x t r e e ) 来搜寻字符串之间的最大子串。后来，m o n o s t o r i 等人又提出用后缀向量 武汉理i ：大学硕十学位论文 ( s u f f i xv e c t o r ) 存储后缀树。西安交通大学宋擒豹等人提出了c d s d g ( c o p y i n g d e t e c t i o ns y s t e mo f d i g i t a lg o o d s ) 系统，这是为了解决数字商品非法复制和扩散 问题而开发的一个基于注册的复制监测原型系统。悉尼大学w i s e 开发了 y a p ( y e t a n o t h e rp l a g u e ) l ，y a p 2 ，y a p 3 系列工具。y a p l 和y a p 2 是用于程序 复制检测的工具，y a p 3 利用程序复制检测的方法，既检测程序复制也检测文 本复制。g l a t t 检测剽窃的方法与众不同，需要被检测人参与测试。g l a t t 认为每 个人都有自己独特的写作风格，这个写作风格就可以作为“指纹”，并且每个人 比其他人更清楚自己的写作风格。所以，g l a t t 在w i l s o nt a y l o r s ( 1 9 5 3 ) 完形填 空程序的基础上建立一个程序，在一篇文档中去掉一些单词留出空白，然后叫 被测试人补空。最后补空的j 下确率就是评估剽窃的依据。这个方法显然不够自 动化，有些繁琐。 根据提取文本特征的方式，我们把文本复制检测方法分为两类。一类采用 基于字符串比较的方法，也称为基于语法( s y n t a c t i c ) 的方法，如s i f ，c o p s ， k o a l a ，s h i n g l i n g ，y a p 3 ，m d r 。这类方法都要求从文档中选取一些字符串， 这些字符串被称为“指纹”( f i n g e r p r i n t ) 。然后把指纹映射到h a s h 表中，一个 指纹对应一个数字。最后统计h a s h 表中相同的指纹数目或者比率，作为文本相 似度依据。 任何一段信息文字，都可以对应一个不太长的随机数，作为区别它和其它 信息的指纹( f i n g e r p r i n t ) 。只要算法设计的好，任何两段信息的指纹都很难重 复，就如同人类的指纹一样。信息指纹在加密、信息压缩和处理中有着广泛的 应用。 另一类文本复制检测采用基于词频统计的方法，这类方法也称为基于语义 ( s e m a n t i c ) 的方法，如s c a m ，c h e c k ，c d s d g 。词频统计法源于信息检索技 术中的向量空间模型( v e c t o rs p a c em o d e l ，除此之外，这三者还吸收了信息检索 中的其他技术。这类方法首先都要统计每篇文档中各个单词的出现次数，然后 根据单词频度构成文档特征向量，最后采用点积、余弦或者类似方式度量两篇 文档的特征向量，以此作为文档相似度的依据【i0 1 。 2 2 网页查重算法分类 2 2 1 同源网页查重 武汉理i ：人学硕十学位论文 首先是同源网页，即网址相同的同一网页的查重。这在网页爬取采集阶段 即可实现。 w e b 信息的采集，通常是利用网络爬虫等工具去遍历网络，它把万维网看 作一个以网页为节点，网页间链接为边的超大规模有向图，然后利用图的遍历 算法对万维网进行遍历。由于网络中一些权威网页可能会被其他多个网页所链 接，且数据下载器一般是循着解析出的超链按广度或宽度优先顺序下载链接到 的网页，因此这些网页可能会被重复下载。在网络遍历的过程中，需要判断待 采集的页面是否已经采集过了，这就需要把已经采集的网页地址记录下来，组 成已采集网页地址集合( 记为：v i s i t e d s e t ) ，当新的采集开始之前，首先判断其 地址是否在v i s i t e d s e t 中，如在其中，表示网页已经采集，否则采集网页，把 网页地址放在v i s i t e d s e t 中，从而避免网页的重复采集，浪费资源。为了实现 集合中数据的快速查找，需要把u r l 映射为集合中的地址，这就需要设计一 种高效且冲突率低的散列算法。 一般来讲，计算机中的集合是用哈希表( h a s ht a b l e ) 来存储的。为了防止 重复下载同一个网页，我们需要在哈希表中记录已经访问过的网址( u r l ) 。但 是如果以字符串的形式将网址存放在哈希表中，非常的浪费内存，而且查找也 很耗费时间。现在的网址又很长，例如，如果在g o o g l e 或者百度在查找数学 之美，对应的网址长度在一百个字符以上。下面是百度的链接 h t t p ：w w w b a i d u c o m s ? i e = g b 2 3l2 & b s = c a f d d1 a 7 d 6 a e c 3 c 0 & s r = & a m p ；z 2 & c l = 3 & f = 8 & w d = c e e 2 b e f c + c a f d d1 a 7 d 6 a e c 3 c 0 & c t = 0 假设网址的平均长度为一百个字符，那么存贮2 0 0 亿个网址本身至少需要 2t b ，即两千g b 的容量，考虑到哈希表的存储效率一般只有5 0 ，实际需 要的内存在4t b 以上。即使将这些网址存放在了计算机内存当中，由于各个 网址长度不同，以字符串的形式查找效率也很差。因此，我们如果能够找到一 个函数，将这2 0 0 亿个网址随机地映射到1 2 8 二进位即1 6 个字节的整数空 间，比如将上面那个很长的字符串对应成一个如下的随机数： 8 9 3 2 4 9 4 3 2 9 8 4 3 9 8 4 3 2 9 8 0 5 4 5 4 5 4 5 4 3 这样每个网址只需要占用1 6 个字节而不是原来的一百个。这就能把存储 网址的内存需求量降低到原来的1 6 。这个1 6 个字节的随机数，就称做该网址 的信息指纹( f i n g e r p r i n t ) 。可以证明，只要产生随机数的算法足够好，可以保 武汉理i ：人学硕十学位论文 证几乎不可能有两个字符串的指纹相同，就如同不可能有两个人的指纹相同一 样。由于指纹是固定的1 2 8 位整数，因此查找的计算量比字符串比较小得多。 网络爬虫在下载网页时，它将访问过的网页的网址都变成一个个信息指纹，存 到哈希表中，每当遇到一个新网址时，计算机就计算出它的指纹，然后比较该 指纹是否已经在哈希表中，来决定是否下载这个网页。这种整数的查找比原来 字符串查找，可以快几倍到几十倍i l 。 同时由于网络上网页数据的巨大，普通的h a s h 算法已经不能满足空间的要 求。哈希表的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问 题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。【l2 】运 用b l o o mf i l t e r 算法设计了一种节省空间的大规模数据表示和查找算法，以应 对海量信息采集的需求。布隆过滤器只需要哈希表1 8 到1 4 的大小就能解决 同样的问题。布隆过滤器是由巴顿。布隆于一九七零年提出的。它实际上是一 个很长的二进制向量和一系列随机映射函数。b l o o mf i l t e r 是一种基于散列的查 找算法，用于查找一个元素是否在集合中，和散列表相比，它的优点是节约空 间，可以对海量数据集进行表示和查找操作。由于散列函数的随机性，可能使 得某个元素不属于集合而被判定属于集合，在此，称其为误判1 1 3 】。 2 2 2 基于聚类的网页查重 其次是对不同源近似网页基于网页内容的查重，即来源网址不同，但内容 相似的网页。这大多是由于网页的转载镜像等引起的。正文间的细微差别可能 是由于转载时的变更，包括丢字、乱码、改变了标题或节略造成的。而这些相 似网页具有以下特点： ( 1 ) 重复率高。网页的重复主要来自转载。网页转载非常容易。由于用户兴 趣的驱动，网络信息流通中人们通过复制方式进行信息共享，经典的文章，以 及新闻网页，很容易引起人们的关注，有时转载竟高达几十次之多。 ( 2 ) 存在噪声。转载时一般都“原样照搬”，保持文本内容和结构的一致， 并尊重版权，在开头加入了引文信息。可是引文会导致复制的文本与原文不完 全一致，我们把这种造成转载文章与原文不同的情况称为网页噪声。还有一些 其他情况引入噪声，如一般各个网站网页的生成环境和版面的风格不同，转载 的文本有时需要还h t m l 语言和x m l 语言内部格式的转换，造成内部格式的 不完全一致。另外，插入的广告图片也是噪声的主要来源。 1 0 武汉理i ：人学硕+ 学位论文 ( 3 ) 局部性明显。主要表现在转载内容的局部性和转载时间的局部性。前者 是指转载的内容主要偏向于人们关注的热点且权威网页，其他网页转载的相对 较少。后者是指转载的时间比较集中，大都在一两天内进行转载，十天以后再 转载则很少1 1 4 1 。 针对这些特点存在不同的网页查重算法。主要有以下几种： 聚类的方法：以6 7 6 3 个汉字作为向量的基，将各个汉字在网页正文中出现 的个数填入向量中，以该向量为这个网页的一个特征，通过计算网页向量与聚 类中心向量的央角余弦值，两向量的模的大小关系，来判断这个网页是否应该 归为该类。特点：方法简单，易于实现。不足：对大规模网页，聚类的类别数 目庞大，难以确定，聚类复杂度o ( n 2 ) ，计算时间长；只计算字频，没有利 用文本的结构信息；实时性差，对于新网页需要重新聚类决定是否重复。因此， 实际应用中难以适用。 2 2 3 基于特征码的网页查重 为了检索出完全相同的网页，需要根据网页的特征建立索引