（计算机软件与理论专业论文）大规模网页相似度算法的研究.pdf

摘要 摘要 互联网的诞生和发展，深刻的改变了人们的生活，激发并促进了人类和社 会的进化。互联网上资源为用户提供大量的信息，大大方便信息的获取和整 合，但是这种传播的便捷性同时也大大降低转载复制的成本，于是这些海量信 息中就会存在大量的重复，给用户带来过多无意义的信息和麻烦。因此，如何 通过相似检索来获取真正有价值的信息成为目前研究的一个热点。 相似度算法问题是信息检索领域的一个重要的研究内容。提高相似网页的 检测对于搜索引擎的抓取、索引、存储和查询都有很大的意义。但是经典的文 本相似度算法在大规模数据集上检测相似网页时，时间和空间复杂度都太高。 本文通过对h t m l 网页进行解析，采用基于文档对象模型和基于视觉特征的方 法抽取网页正文。从基于语法的文本相似度研究出发，采用标引化、去除停用 词、抽取词干等文本词汇分析方法和基于向量空间统计词频、n g r a m 、抽取最 长句子等文本特征选择方法，之后对抽取的特征进行m d 5 和r a b i n 指纹签名。 本文的创新点有两个方面： 第一，提出基于标引词编辑距离的相似度度量方法，发明编辑比例 e d i t r a t e 和编辑相似度e d i t s i m 两个计算公式，并实现算法用于机器标注数据 集，将该度量方法作为其他相似度算法的基线。 第二，提出大规模网页相似度算法f u s i o n s i m 。f u s i o n s i m 算法是在 s i m h a s h 算法的基础上，融合词频统计、n g r a m 、抽取最长句子等一系列算法 来度量网页文档的相似度。f u s i o n s i m 除了特征选择的多样化，还考虑特征在 文本中的位置信息和特征之间的相互关系。通过不同的特征权重设置，可以调 整f u s i o n s i m 度量的严格度。此外，f u s i o n s i m 算法还有很高可扩展性，算法设 计和程序实现都可以很方便的加入新的相似度算法。通过在文本和网页数据集 上的实验，f u s i o n s i m 的查准率和查全率都优于s i m h a s h 算法。 关键词：相似度算法近似检测指纹w e b 搜索引擎信息检索大规模计算 f u s i o n s i m a b s t r a c t a b s t r a c t a st h ee s t a b l i s h m e n ta n dd e v e l o p m e n to ft h ei n t e m e t ，p e o p l e sl i v e sa r e p r o f o u n d l yc h a n g e d i n t e r n e ti ss t i m u l a t i n ga n dp r o m o t i n gt h ee v o l u t i o no fh u m a n a n ds o c i e t y r e s o u r c e so nt h ei n t e r a c th a v ep r o v i d e dt h eu s e r sw i maw e a l t ho f i n f o r m a t i o na n dg r e a t l yf a c i l i t a t ea c c e s st oi n f o r m a t i o n b u ta tt h em e a n w h i l e ，t h e e a s eo fs p r e a da l s og r e a t l yr e d u c e st h ec o s to fc o p ya n dr e p u b l i s h m e n t a sar e s u l t ， t h e r ew i l lb eal a r g en u m b e ro fd u p l i c a t e si nt h em a s so fi n f o r m a t i o nw h i c ha n n o y i n g t h eu s e r sa n db r i n g i n gt o om u c hm e a n i n g l e s si n f o r m a t i o n t h e r e f o r e ，h o wt oa c q u i r e t h er e a lv a l u a b l ei n f o r m a t i o nt h r o u g hs i m i l a r i t ys e a r c hi sb e c o m i n gar e s e a r c hh o t s p o t s i m i l a r i t ya l g o r i t h mi sa ni m p o r t a n tr e s e a r c ht o p i ci ni n f o r m a t i o nr e t r i e v a l i m p r o v i n gt h ed u p l i c a t ed e t e c t i o ni so fg r e a ts i g n i f i c a n c et ot h ef e t c h i n g ，i n d e x i n g ， s t o r i n ga n dq u e r y i n go fs e a r c he n g i n e b u tt h ec l a s s i c a lt e x ts i m i l a r i t ya l g o r i t h m sa r e t o oc o m p l e x i t yi nt i m ea n ds p a c ew h e na p p l y i n gi nl a r g e s c a l ed a t a s e t s t h i st h e s i s u s e sd o m - b a s e da n dv i s i o n - b a s e dm e t h o d st oe x t r a c tw e b p a g ec o n t e n ta f t e rp a r s i n g t h eh t m l p a g e s b a s e do nt h er e s e a r c ho fs y n t a c t i cs i m i l a r i t y , t h i st h e s i sa p p l i e st h e l e x i c a la n a l y s i s ( t o k e n i z a t i o n ，s t o p w o r dr e m o v a la n ds t e m m i n g ) a n dt e x tf e a t u r e s e l e c t i o n ( t e r mf r e q u e n c yb a s e do nv s m ，n g r a ma n dl o n g e s t - s e n t e n c ee x t r a c t i o n ) t o g e tt h ef e a t u r eo fw e bp a g e s ，a n dt h e nf i n g e r p r i n t i n gt h ef e a t u r eb ym d 5 a n dr a b i n t h e r ea r et 、) l ，oi n n o v a t i o n si nt h i st h e s i s ： f i r s t l y , t h i st h e s i sp u t sf o r w a r dt h et o k e n - b a s ee d i td i s t a n c ea st h es i m i l a r i t y m e a s u r e m e n t ，i n v e n t st w oc o m p u t i n gf o r m u l a , e d i t r a t e & e d i t s i m ，w h i c ha r e a p p l i e dt ol a b e l i n gt h ed a t a s e t m e a n w h i l e t h i sm e a s u r e m e n tm e t h o di su s e da st h e b a s e l i n ef o ro t h e rs i m i l a r i t ya l g o r i t h m s 勰w e l l s e c o n d l y , t h el a r g e s c a l ew e bp a g es i m i l a r i t ya l g o r i t h mf u s i o n s i mi sr a i s e d b a s e do ns i m h a s h ，f u s i o n s i mh a sc o m b i n e dm a n ya l g o r i t h m ss u c ha st e r m f r e q u e n c ys t a t i s t i c s ，n g r a ma n dl o n g e s t s e n t e n c ee x t r a c t i o nt oc o m p u t i n gt h ew e b p a g es i m i l a r i t y e x c e p tf o rt h ev a r i e t yo ff e a t u r es e l e c t i o n , i ta l s oc o n s i d e r st h e l o c a t i o na n dr e l a t i o no ff e a t u r e si nt h ed o c u m e n t b ys e t t i n gt h ed i f f e r e n tw e i g h t sf o r i i 垒垒兰皇竺! - _ _ l _ _ _ _ - _ _ _ _ _ _ _ _ _ 一 f e a t u r e ，t h em e a s u r es t r i c t n e s so ff u s i o n s i m c a l lb ea d j u s t e d a d d i t i o n a l l y , f u s i o n s i m h a sh i g hs c a l a b i l i t y t h en e ws i m i l a r i t ya l g o r i t h mc a l l b ee a s i l ym e r g e di n t o f u s i o n s i m a f t e rt h ee x p e r i m e n t sb o t ho nt h et e x ta n dw e bd a t a s e t ，f u s i o n s i m o u t p e r f o r m ss i m h a s hi nt e r m so fp r e c i s i o na n dr e c a l l k e yw o r d s ：s i m i l a r i t ya l g o r i t h m ，n e a rd u p l i c a t ed e t e c t i o n ，f i n g e r p r i n t ，w e b s e a r c he n g i n e ，i n f o r m a t i o nr e t r i e v a l ，l a r g e s c a l ec o m p u t i n g ，f u i o n s i m i i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 年月 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 年月日 第一章绪论 第一章绪论 1 1 引言 互联网的诞生，使得整个世界的信息生存进入一个崭新的时代，深刻的改 变了人类生活的每一个环节，自然也深刻的变革了人类的思维方式。而互联网 的高速发展，又进一步激发并促进人类和社会的进化。 m a y e rt i m l 在2 0 0 5 年8 月公布了y a h o o 公司搜索引擎收集的网页总数有 1 9 2 亿，根据n e c 2 提供的1 9 9 7 2 0 0 2 年网页数统计，绘制了互联网规模发展 图，可以看出网页数是呈指数爆炸增长的。 图1 1 互联网规模的发展 n e t c r a t t c x ) m 在2 0 0 8 年4 月统计得到1 6 5 亿网站相应数，按照其估计的平 均每个网站拥有2 7 3 个网页的标准进行计算，2 0 0 8 年4 月互联网的网页规模大 概是4 5 2 亿。 互联网上资源为用户提供大量的信息，大大方便信息的获取和整合，但是 这种传播的便捷性同时也大大降低转载复制的成本，于是这些海量信息中就会 存在大量的重复，既包括同一站点内网页的重复，也包括不同站点之间的重 1 h t t p ：w w w y s e a r c h b l o g c o m a r c h i v e s 0 0 0 17 2 h t m l 2h t t p ：h y p e r t e x t b o o k c o m f a c t s 2 0 0 7 l o r a n t l e e s h t m l 1 第一章绪论 复。这些重复的网页增加搜索引擎收录时的存储空间和索引时间，降低检索速 度，增加搜索服务的成本，并且给用户带来大量无意义的信息和麻烦。 1 2 研究背景 1 2 1 网页相似度的定义 互联网上重复( d u p l i c a t e ) 的网页有很大部分是完全重复( f u l ld u p l i c a t e ) ，即 h t m l 源文件完全相同，出现这类完全重复网页大部分是因为镜像网站的存 在。另外有些网页文档是被转载到不同的网站，或是同一网站内部的不同版 本，这类网页的h t m l 文件不完全相同，但是它们的网页正文是很相近的。相 关研究表明，互联网近似( n e a r - d u p l i c a t e ) 网页数占网页总数的比例高达 2 9 2 1 1 。 根据上面的描述，本文将网页重复分为两类，定义为完全重复( 向1 1 d u p l i c a t e ) 和近似重复( n e a r - d u p l i c a t e ) 。完全重复的网页可以通过m d 5 或s h a 等 签名方法快速检索出来，但是近似重复的网页通过m d 5 或s h a 产生的哈希值 却会产生巨大的差异。如何从超大规模数据集中快速的找出相似的网页，是本 文研究所关注的问题。这里的近似网页是指不考虑网页的排版格式，并除去网 页导航信息、广告、版权等噪声，正文内容完全相同或大部分相同的网页，其 中还包括内容转载过程中正文部分段落句词的增减。 相似度定义还有三个关系上的特性： 自反的 对称的 非传递的 比如，每一个网页和它自身是最相似的；如果网页a 和网页b 相似，那么 网页b 也和网页a 相似；但是，如果网页b 也和网页c 相似，网页a 并不一 定就和网页c 相似。 1 2 2 网页相似度在信息检索中的应用 对于搜索引擎来说，检测相似网页是一项重要的关键技术。在返回检索结 果前，将近似重复的网页过滤掉，可以更好地提高检索排序的效果和用户使用 的满意度，减少用户无谓的点击时间。并且提供“相似网页 的功能，当某一 2 第一章绪论 网页不能访问时，用户可以通过访问相似网页获取信息。 对于网络爬虫来说，可以忽略掉相似网页的外向链接，减少无用的抓取， 提高网络带宽的利用率。在检测出相似网页的基础上，还可以发现镜像网站。 通过去除镜像网站，可以减少搜索引擎抓取、索引和存储的开销。 通过加入专业领域知识，相似度算法还可以更好的找出专有领域的近似网 页。这样的知识可以大大提高主题抓取( f o c u s e dc r a w l i n g ) 爬虫获取专有领域网 页集合的效率。 网页相似度算法还可以用于信息抽取。通过聚集相似网页集合，可以从中 学习和挖掘出这类网页的共有模版，再通过这类自动生成的模版，从无结构的 网页内容中挖掘出有结构的信息。比如提取i 1 i l d b 上的电影网页，或者提取淘 宝上关于产品介绍的网页。 当然，和文本相似度算法一样，网页相似度算法也可以检测网络上的抄袭 复制，用于保护网络上的知识产权。 1 3 本文研究内容和组织结构 1 3 1 主要研究内容 本文的研究内容主要分成两个部分，第一部分是基于网页内容结构分析的 特征提取，从网页正文抽取、文本词汇分析、文本特征选择和文本距离度量四 个方向进行研究和实验，为第二部分的研究工作提供基础；第二部分是大规模 相似度算法f u s i o n s i m 的设计和实现，并在不同数据集上对不同算法进行对比 和分析。 1 3 2 研究思路 因为本文的出发点是大规模数据集上的相似度算法研究，所以对算法的时 间和空间复杂度都有很高的要求。简单、高效是该类算法设计的核心，算法本 质上就是对高维数据进行降维的过程。目的是使每个文档都会生成一个代表自 身的签名值，并且让相似的文档有相近的签名。在对比经典的文本相似度算法 之后，本文综合考虑网页文档的统计词频、n g r a m 、最长句子等特征，并融合 特征之间的相对位置和相对权重，提出快速高效可扩展的f u s i o n s i m 算法。 3 第一章绪论 1 3 3 本文组织结构 本文分为五章。第二章对相似度算法研究领域进行综述。从文本相似度和 网页相似度两个方向分别介绍该研究领域经典的算法，并对它们进行对比分 析。接着列举相似度度量的评价指标，在最后介绍位置敏感哈希方法。位置敏 感哈希是近邻搜索领域研究的热门，也是本文提出算法的理论基础。 第三章是通过对网页内容结构分析来进行特征抽取。首先从过滤网页噪声 出发，介绍了基于文档对象模型和基于视觉特征分析的两种方法。接着介绍了 本文用到的标引化、去除停用词及词干抽取的文本词汇分析技术，和统计词 频、n g r a m 及最长句的文本特征抽取算法。最后在海明距离和编辑距离的基础 上，提出用基于标引词的编辑距离来度量文本之间的距离。 第四章是本文的重点。先对m d 5 和r a b m 指纹两种签名方法进行理论分析 和实验对比选择。然后创造性提出一种大规模网页相似度算法f u s i o n s i m ，该 算法是在s i m h a s h 算法的基础上融合了统计词频、n g r a m 、最长句子等方法， 文中详细阐述f u s i o n s i m 算法的设计思想和实现过程，并在不同的数据集上进 行实验，f u s i o n s i m 算法获得很高的效率和性能，并且具有很好的可扩展性和 可配置性。 第五章是本文的总结，并提出未来的工作方向。 4 第二章相似度的相关领域研究综述 第二章相似度的相关领域研究综述 2 1 文本相似度的研究 文本相似度计算是自然语言处理、w e b 智能检索、文本聚类和文本分类研 究中一个比较基础的课题。它所研究的是用什么样的方法和度量来计算或比较 两个文本的相似性，该方法也可应用于计算一个文本与某个类别的相似性，并 用于个性化推荐服务( 计算用户目标和文本的匹配程度) 。 对文本相似度的研究可以分为两个方向：语法相似度( s y n t a c t i cs i m i l a r i t y ) 和 语义相似度( s e m a n t i cs i m i l a r i t y ) 。比如下面3 个英语句子【2 】： s e n t e n c ei ：aw e a l t h yt e x a nd e v e l o p e rc o n v i c t e do fk i l l i n gs i m o np r a n k e r d , a b r i t i s hy a c h tc a p t a 讯ia n dh i sf i v ep a s s e n g e r si nah i g h - s p e e dd r i n k - d r i v i n gb o a t c r a s hh a sb e e ns e n t e n c e dt o8 5 y e a r si np r i s o n s e n t e n c e2 ：a na m e r i c a nd e v e l o p e rw h ow a s f o u n dr e s p o n s i b l e f o rt h ed e a t h so f 6 p e o p l ei n v o l v e d 伽ab o a tc r a s hw a ss e n t e n c e dt o8 5y e a r si n j a i l s e n t e n c e3 ：aw e a l t h yc a l i f o r n i a nt o u r i s tc o n v i c t e do f k i l l i n gf r a n c o i sr o b e r t , a f r e n c hb u sd r i v e r , a n dh i s8 p a s s e n g e r si nah i g h - s p e e dd r u n k - d r i v i n gc a rc r a s hw a s s e n t e n c e dt o7 0y e a r si np r i s o n 句子1 和句子3 在语法角度上是相似的，因为它们的表述方式和句法很一 致，但是从内容上它们是在叙述不同的事件。而句子2 是对句子1 的简要描 述，虽然它们从语法上是不相似的，但是从内容和语义上它们是相似的。 语义相似度的研究涉及到自然语言理解，目前还没有比较好的方法来处 理，是研究上的一个待突破的难点。本文后面提到的相似度度量和方法都是基 于语法角度的。 从语法角度计算文本相似度有很多方法，主要分两大类：一类是基于字符 串比较的方法，字符串可以基于不同的粒度，比如段落、句子、连续词、单 词、字符等；另一类是基于词频统计的方法，在向量空间模型的基础上，通过 降维、计算距离等方式来度量相似度。 西安交通大学的鲍军鹏 3 】等人，对自然文档复制检测的方法给出一个研究 综述，按公布时间总结一系列著名的方法。 5 第二章相似度的相关领域研究综述 表2 1 文本复制检测系统汇总【3 】 s e a m 釜龇1 9 9 5 姗嘶硎 啪 2 1 1s i f 1 9 9 3 年，a r i z o n a 大学的u d im a n b e r ( 现g o o g l e 副总裁、工程师) 提出 了s i f t 4 i 具，它主要用于在大型文件系统中查找相似文档，具体应用包括文件 管理、信息收集和去重、程序重用、文件同步、数据压缩和复制检测。它的主 要贡献是提出了“近似指纹( a p p r o x i m a t ef i n g e r p r i n t s ) 的概念，通过这种近似 指纹来表示文本和进行文本相似度计算。近似指纹提供了一种对文档的压缩标 识，在很高的概率下，使得相似的文件的指纹也相似( 但不一定相等) ，而不 相似的文件的指纹则不同。 s i f 工具进行相似度计算的主要过程如下：先提取一定的字符串作为“指 纹 ，通过哈希运算将不同的字符串映射不同的数值，再比较不同文档的数值 集合，如果代表两篇文档的数值组合中相同的数字超过一定的阈值，则判断两 篇文档相似。这样，“近似指纹计算将字符串的匹配问题转换成了数值比较 问题。 核心的处理过程是以5 0 个字节( 字符) 为长度，将文件划分为重叠的一个 个子串，然后计算每一个子串的指纹值。比如把文本文件标识为岛一厶，那么 第一个5 0 字节的字串的指纹值为： 互= ( t l p 4 9 + t 2 p 4 8 + + t 5 0 ) m o d m ( 2 1 ) 6 亨i璺一。 ；一 t 譬面一俄 糊一 糕 ，磊一鼢 避一 第二章相似度的相关领域研究综述 这里p 和m 为常数，根据霍纳法贝, l j ( h o m e r sr u l 曲，优化计算多项式， 鼻= ( p ( ( ( p ( p + t 2 ) + 屯) ) ) + 岛o ) m o dm ( 2 2 ) 而在计算e 时，只需要加上最后一个参数并且减去第一项， e = ( p 鼻+ t 5 l 一p ) m o dm ( 2 3 ) 总的来说，计算的指纹数和文本的字符数成正比，而与指纹的大小无关。 有很多方法可以决定挑选哪些指纹，最简单的方式是选择以k 个0 结尾的指纹 值。近似地看来，2 个字符中会选出一个指纹。文献 4 】将p 设为一个素数，m 设为2 3 0 ，k 设为8 。因为被选到的指纹值最后8 位都是0 ，所以可以将指纹值 右移8 位存储来节省空间。如果系统中的文件数非常多，那么可以通过使用更 大的指纹值( 比如2 3 1 或2 3 2 ) 来减少指纹冲突的几率。 虽然通过上述方法选取了较为稀疏的指纹值，但这个问题并不重要，因为 这些选取的指纹已经足够来标识文本。尤其在不相关的两个文件中出现相同的 5 0 字节子串，这种可能性是相当小的。通过这种近似选择还可以过滤掉噪声信 息。如果两个文件拥有足够数目的相同指纹，那么在一定程度上已经足够证明 两个文件是相似的。 文献 4 】最后列举了两个检索方法：从多个中找与一个相似的( a l l 多个中找与多个相似的( a ua 1 1 ) 。通过对指纹值建立倒排索引和排序等技术， 可以加快检索的速度。 “近似指纹 的思想在以后的文本相似度检测系统中得到广泛的使用，如 1 9 9 6 年提出的k o a l a 系统，b r o d e r 提出的s h i n g l e 系统，都是基于近似指纹 的字符串匹配的算法进行相似度检测的。 这些文本相似度算法都是基于语法级别的( s y n t a c t i cs i m i l a r i t y ) ，而没有考虑 到语义级另l j ( s e m a n t i cs i m i l a r i t y ) 。也就是说对于相同的信息使用不同的词语描 述，从语法级别来看，它们仍旧是不相似的。 2 1 2s c a m 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 dc o p ya n a l y s i s m e t h o d ) 原型【5 6 】改进c o p s 系统，用于发现知识产权冲突。s c a m 借鉴了信息 检索技术中的向量空间模型( v e c t o rs p a c em o d e l ) 1 7 ，使用基于词频统计的方法来 度量文本相似性。后来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 模型【8 】，把检测范围从单个注册数据库扩展到分布式数据库上 7 第二章相似度的相关领域研究综述 以及在w e b 上探测文本复制的方法【9 】。 s c a m 的方法受到了信息检索技术的启示。s c a m 首先统计文档中各个单 词出现的次数，然后按照信息检索中常用的倒排索引存储法( i n v e r t e di n d e x s t o r a g e ) 存储文档与词频信息。最后，s c a m 参照向量空间模型( v e c t o rs p a c e m o d e l ) 提出了相关频率模型( r f m ，r e l a t i v ef r e q u e n c ym o d e l ) ，用以度量文档相 似性。向量空间模型一般采用点积或者余弦公式来度量相似性。而相关频率模 型其实是对余弦公式进行了改动，试图提高文件复制检测精度。令d 表示候选 文档，q 表示待检测( 或者查询) 文档，f ( d ) 表示文档d 的词频向量，f ( q ) 表 示文档q 的词频向量，a 表示各词的权重向量，则v s m 用余弦公式计算的相似 度鼠( d ，q ) 为 一，2 蠹群n2 器 泡4 ， 显然，鼠( d ，o ) = 鼠( q ，d ) 。r f m 首先定义了一个靠近集( c l o s e n e s ss e t ) c ( d ，q ) ，用于选取文档d 和q 中出现频度相近的单词。也就是说，c ( d ，q ) 包 含的单词是d 和q 中都有的单词，并且满足如下公式： s f 型+ 型1 0 ( 2 5 ) l 鼻( q )曩( d ) 其中，s = ( 2 + ，o o ) ，是一个用户可调的参数。然后要计算d 对q 的子集度 或者包含度s u b s e t ( d ，q ) ， 鼢以n 妒鼍一 泣6 ， 显然，d 对q 的包含度与q 对d 的包含度不一样， 即 s u b s e t ( d ，q ) s u b s e t ( q ，d ) 。所以，r f m 最终的相似度母( d ，q ) 为 母( d ，q ) = m a x s u b s e t ( d ，q ) ，s u b s e t ( q ，d ) ) 。如果墨( d ，q ) 1 则令母( d ，q ) = 1 。 现在则有p ，q ) = 母( q ，d ) 。用r f m 方法可以更好地检测子集包含式复制， 并且s 越大，表示对两篇文档中共有单词的容忍度越大，但是无关文档的匹配 机会也会越大，即正误差( f a l s ep o s i t i v e s ) 越大；占越小，正误差越小，但是检测 小程度重合文档的能力也越小。s c a m 并未确定一个普适的g 值，但是认为占 = 2 5 对于网络新闻文章比较合适。 8 第二章相似度的相关领域研究综述 2 13s h i n g l e 1 9 9 7 年，b r o d 一1 0 提出了s h i n g l e 方法，来聚类语法上相似( s y d t a 血栅y s i m i l a t ) 的文档，主要应用于过滤网页搜索结果、更新同步广泛分布的网页资 源、识别知识产权侵权。所谓s m n g l e 就是文档中连续的子序列，类似于自然 语言处理中常用的n g r a m ，就是将相互连续出现窟口大小为n 的单词串作 为一个s h i n 出，两者的不同点在于s h i n g l e 是这些串的集合，相同的串将会合 并为一个，而n - g r a m 则由于考虑的是文本线性结构，所以没有相同合并步 骤。每个s h i n g l e 就是文档的一个特征，一篇文档就是由所有这些s h i n g l e 构成 的。 比如对于( ar o s ei sar o s ei sar o s e ) 这_ 个文本抽取4 - s h i n g l e ，结果集就是 “ t o s g ，i s ，a ) ，( r o ，i s ，r o s e ) ，( i s ，a ，r o s e , i s ) 1 。 b r o d e r 还提出了两个概念：相似度( r e s e m b l a n c e ) 和包含度( c o n t a i n m e n t ) 。记 s ( 一) 为爿的s h i n g l e 集合，为集合a 的元素个数。则a 和占n , n 似度为： 州= 船涮 n ， 一在口中的包含度为： 州= 罐铲 。” 这样为度量设定一个闽值，当两个文档之间超过这个阚值时就可以认为它 们是相似的。 田厂、 l | s h j n 洲m ( 涨s l ，一， f i n g e r p r i n t 图21s h i n g l e 方法计算流程 如图2l ，s h i n g l e 方法( 也称为d s c 算法- d i g i t a ls y n t a c t i cc l u s t e r i n g ) 对 w e b 文档相似度的计算过程如下： 1 先将h t m l 文档去掉格式标签，并且把所有文本中的单词转为小写： 2 设定s h i n g l e 的大小为1 0 ，将文档转化为s h i n g l e 集合： 第二章相似度的相关领域研究综述 3 使用r a b i n 指纹方法将每一个s h i n g l e 转化为一个6 4 位的指纹值； 4 使用最小独立置换或取模方法来挑选s h i n g l e 作为每一个文档的代表； 5 计算文档集合中两两之间的相似值( r e s e m b l a n c e ) ，若超过阈值则标记该 文档对为相似。 这里面s h i n g l e 大小的选择是一个值得讨论的问题，当s h i n g l e 大小取的过 长时，文档中很小的随机变化就会带来巨大的影响：而当s h i n g l e 过短时，一些 不相关的文档可能就会拥有更大的相似度。根据不同的应用和处理模式， b r o d e r 推荐s h i n g l e 的长度为3 到1 0 之间。 为了加快检测和查询的计算速度，d s c 采用倒排索引的方法，建立排序的 列表和三元组 。但是，采用过滤 策略之后被选中的s h i n g l e 也会很多，这样导致比较次数太多，效率将会很低。 所以b r o d e r 又提出了s u p e rs h i n g l e 方法，也称d s c - s s ( d s c ss u p e rs h i n g l e ) 是d s c 的改进版本，d s c s s 将选中的代表文档的s h i n g l e 先排序，之后在这 些s h i n g l e 上再进行一次s h i n g l e ，即把几个s h i n g l e s 合成为一个s u p e rs h i n g l e ， 这样对文档的描述就从很多s h i n g l e 变成只有几个s u p e rs h i n g l e ，比较的时候就 比d s c 减低很多数量级。这样，如果s u p e rs h i n g l e 的大小选择合适的话，两个 相似文档会有很大概率至少拥有一个相同的s u p e rs h i n g l e ，也就是说如果出现 了一个相同的s u p e rs h i n g l e 那么两个文档相似的可能性会很高。d s c s s 最后也 还是根据结果和阈值的比较来判断两篇文档是否相似。不仅因为减少了比较次 数，而且还大大减少了s h i n g l e 的存储，所以d s c s s 的效率比d s c 提高很 多。 除了s u p e rs h i n g l e 的改进，本文认为s h i n g l e 方法还有一些优化的方法，比 如采用分布计算然后再合并的方法来提高计算速度；对超高频的s h i n g l e 进行过 滤；在提取s h i n g l e 之前先对文本进行去除停用词、词干抽取等标准的信息检索 方法过滤噪声信息，来提高选取的s h i n g l e 对文档的描述能力。 因为s h i n g l e 的长度和选取s h i n g l e 时的策略，导致s u p e rs l l i n g l e 方法有一 个明显的缺点：在处理短文档的时候效果很差。而w e b 上的短文档数目很大， 所以如何计算这类文档的文本相似度也是一个需要讨论和改进的问题。 2 1 4i - m a t c h i - m a t c h d l l 算法也是对d s c 算法的一种改进，但是不同于d s c s s ，它并非 l o 第二章相似度的相关领域研究综述 从减少比较次数这方面着手，而是从过滤s h i n g l e s 这方面，尽量过滤掉尽可能 多的重复次数较多的s h i n g l e s 。这种过滤方式有点像矿渺中的a f 的计算方法。 将集合中所有的文档分成s h i n g l e s 后，就开始计算每个s h i n g l e 的出现次数，和 出现该s h i n g l e 的文档的个数，根据每个s h i n g l e 的i a f 值判断取舍，再将每个保 留下来的s h i n g l e 计算出一个哈希值，再比较这些整型的值就可以判断两篇文档 是否相似。 i - m a t c h 不依赖于严格的语法分析。而是使用集合统计( c o l l e c t i o ns t a t i s t i c s ) 的方法来识别哪些连续的字符串被选为比较的基石。 每个词串( t e r r n ) 的a f ( i n v e r s ed o c u m e n tf r e q u e n c y ) 被定义为屯= l o g ( n n ) ， 是集合中的文档数目，l 是包含这个词串的文档数目。i ma t i 出方法同时舍去 a f 数值较高和过低的，因为这些词串并没有增加文档语义上的内容，过滤后生 成的词串能更好的描述文档，来达到识别重复的目的。 输入一篇文档，过滤出一些关键串，并且计算出这篇文档的唯一的哈希 值，那些哈希值相同的文档就是重复的。使用s h a l 作为哈希函数，因为它的 速度很快而且适用于任何长度。s h a l 是专为文本处理设计的，并且产生的哈 希值有平稳的分布。 s h a l 生成一个2 0 字节或者1 6 0 比特的哈希值。并且使用一个安全的冲突 消解算法，使得不同的标引词流( t o k e ns t r e a m s ) 生成相同的哈希值的概率低于 p ( 2 。1 6 0 ) 。 把 元组插入树结构的时间复杂度是o ( d l o g d ) ，这里d 指的是集合中的文档数，如果使用其它更有效率的存储和检索的数据结构，如 哈希表则时间复杂度是d ( d ) 。对重复文档( d u p l i c a t e ) 的识别是就是在将数据插 入树结构或哈希表中进行的，任何的哈希值的冲突就表示检测到一个复制，这 时候冲突的文档d 就会存储在该树的节点或者该哈希桶中。对树或是哈希表 的一次遍历扫描，收集那些多于一个文档d 的节点，就能生成重复文档的类 别列表。 算法过程描述如下： 1 获取文档； 2 去除文档的格式标签，将其解析为一个标引词流( t o k e ns t r e a m ) ； 3 使用词阈值i d f 过滤，只保留那些重要的标引词； 4 将选择的相关标引词插入到以u n i c o d e 升序排列存储不重复标引词的树 1 1 第二章相似度的相关领域研究综述 结构中； 5 遍历整个标引词树( t o k e nt r e e ) ，将出现的每一个标引词加入其s h a l 签 名。当遍历完成后，就生成一个( d o ci d ，s h a ld i g e s 0 元组； 6 将这个( d o ci d ，s h a ld i g e s 0 元组插入到以s h a l 签名做关键词存储的 数据结构中； 7 如果签名值出现冲突，那么这些冲突的文档就是相似的。 算法分析： i - m a t c h 最坏情况下的时间复杂度是o ( d l o g d ) ，这时候集合中所有的文档 都是相同的；最好的情况是d ( d ) ，这时候文档都互不相同。 计算i d f 值的方法有两种：第一种是在去重开始之前，使用训练集来计算 每个词串的d f 值。因为当集合大小改变时，d f 值只会轻微改变，所以这是一 种可以接受的方案。另一种方法是把i - m a t c h 算法分成两个步骤，第一步先整 体计算所有词串的渺值，第二步再利用i - m a t c h 算法来查找重复文档，虽然这 种方法会增加实际的运行时间，但是它的理论复杂度仍旧保持不变。 和d s c s s 算法对比，d s c s s 会产生k 个s u p e rs 1 1 i n 西e 来标识文档，而i - m a t c h 方法只产生一个，因为k 是一个常数，所以这两个算法在理论上复杂度 是相同的，在实际应用上，i - m a t c h 会有更高的效率。 i ma t i 出算法对比d s c s s 的优势并不在于时间效率上的提高，而是因为它 能够计算短文档。d s c s s 对于短文档并不能提取出s h i n g l e 来做去重检测，因 此，即使这些短文档中出现重复，d s c s s 算法也没法检测到，对于很多具体 的文档去重应用领域，忽略短文档会影响算法的查全率，而i - m a t c h 的提出就 是为了解决这一问题。 2 2 网页