下载文档原格式
网络爬虫中的页面去重技术实现与改进随着互联网的快速发展和信息的爆炸式增长，网络爬虫成为了一种重要的工具，用于自动化地获取和处理互联网上的大量数据。
然而，由于网页的重复性和冗余性，网络爬虫在很大程度上浪费了时间和资源。
为了解决这个问题，页面去重技术应运而生。
页面去重技术实现主要涉及两个方面：判断页面是否重复和对重复页面进行去重处理。
判断页面是否重复是页面去重的第一步。
常见的判断页面是否重复的方法有两种：基于内容的去重和基于特征的去重。
基于内容的去重方法是通过比较网页的内容来判断页面是否重复。
它使用hash函数将网页内容映射为一个固定长度的字符串表示，并将其存储在数据库中。
当爬虫访问新的网页时，同样使用hash函数将其内容映射为字符串，然后与数据库中已存在的hash值进行比较。
如果已存在相同的hash值，则说明页面重复，爬虫将不再对该页面进行处理。
这种方法的优点是简单高效，但存在一定的误判率，因为不同的网页内容可能会生成相同的hash值。
基于特征的去重方法是通过提取网页的特征来判断页面是否重复。
网页特征可以包括网页的URL、标题、关键词、正文等。
首先，对网页进行特征提取，然后将特征存储在数据库中。
当爬虫访问新的网页时，同样提取特征，并与数据库中已存在的特征进行比较。
如果已存在相同的特征，则说明页面重复，爬虫将不再对该页面进行处理。
与基于内容的去重方法相比，基于特征的去重方法更加精确，但也更加复杂和耗时。
在实际应用中，为了提高去重的准确性和效率，可以结合使用基于内容和基于特征的去重方法。
首先利用基于内容的方法进行初步判断，将网页按照不同的hash值分组。
然后，在每一组内部再使用基于特征的方法进行细分去重，以进一步提高去重的准确性。
除了页面去重技术的实现，还可以通过改进页面去重算法来提高去重的效果。
首先，可以采用布隆过滤器来改进去重算法。
布隆过滤器是一种高效的数据结构，用于判断元素是否存在于集合中。
它使用一个位向量和多个哈希函数来判断元素的存在性。
从html中提取正文的方法从HTML中提取正文的方法随着互联网的发展，网页内容呈现多样化的趋势，其中HTML是最常见的网页编程语言之一。
但是在浏览网页的过程中，我们往往只关注页面的主要内容，即正文部分。
如何从HTML中提取出正文内容，成为了一个非常重要的问题。
本文将介绍几种常用的方法来实现这一目标。
一、基于标签的提取方法HTML文档通常由一系列的标签组成，不同的标签有不同的作用和语义。
在提取正文时，我们可以根据标签的特点来进行筛选。
常用的标签有p、div、span等，这些标签通常用来包裹正文内容。
我们可以通过解析HTML文档，找到这些标签，并提取出其中的文本内容。
同时，我们还可以根据标签的属性进行筛选，比如class属性、id 属性等。
通过这种方法，我们可以较为准确地提取出正文内容。
二、基于文本密度的提取方法正文通常具有较高的文本密度，即正文部分的文字数量较多。
而其他非正文的内容，比如导航栏、广告等，通常具有较低的文本密度。
基于这个特点，我们可以通过计算页面中每个标签的文本密度，来判断其是否属于正文内容。
具体的方法可以是统计标签内文本的字符数或词数，然后除以标签的总字符数或词数，得到文本密度的比值。
根据这个比值的大小，我们可以判断标签是否为正文内容。
通过这种方法，我们可以较为准确地提取出正文内容。
三、基于机器学习的提取方法除了基于标签和文本密度的方法，还可以利用机器学习的方法来提取正文内容。
通过训练模型，我们可以将HTML文档中的各个标签和属性作为特征，将其对应的正文内容作为标签，然后利用已有的正文和非正文数据进行训练。
训练完成后，我们可以使用这个模型来预测新的HTML文档中的正文内容。
这种方法的优势在于可以适应不同的网页结构和样式，提取效果较为准确。
从HTML中提取正文内容是一个比较复杂的问题，但是通过合理的方法和技术手段，我们可以实现较为准确地提取。
基于标签、文本密度和机器学习的方法都具有一定的优势和适用场景，可以根据实际需求选择合适的方法。
网页爬虫解决方案标题：网页爬虫解决方案引言概述：随着互联网的快速发展，网页内容的数量也在不断增加，为了从海量数据中获取有用信息，网页爬虫成为了一种重要的工具。
然而，网页爬虫在实际应用中也面临着各种问题和挑战。
本文将介绍一些常见的网页爬虫解决方案，帮助读者更好地应对这些挑战。
一、反爬虫策略1.1 频率限制：网站通常会设置访问频率限制，防止爬虫过于频繁地访问网站，可以通过设置访问间隔时间来规避这种限制。
1.2 User-Agent检测：网站可以通过检测User-Agent来判断请求是否来自爬虫，可以通过设置User-Agent来模拟正常用户的请求。
1.3 IP封锁：网站可能会封锁频繁访问的IP地址，可以通过使用代理IP来避免IP封锁。
二、数据清洗和去重2.1 HTML标签处理：爬取的网页内容通常包含大量的HTML标签，需要对其进行清洗，只保留有用的文本内容。
2.2 去重处理：在爬取大量网页数据时，可能会遇到重复内容，需要进行去重处理，保证数据的唯一性。
2.3 数据格式化：对爬取的数据进行格式化处理，便于后续的数据分析和处理。
三、动态网页处理3.1 使用Selenium：对于动态加载的网页内容，可以使用Selenium等工具模拟浏览器行为，获取完整的页面内容。
3.2 Ajax请求处理：一些网页使用Ajax请求加载数据，可以通过分析Ajax请求的接口，直接获取数据。
3.3 JavaScript渲染：部分网页内容通过JavaScript动态渲染，可以使用PhantomJS等工具来解决JavaScript渲染的问题。
四、数据存储和管理4.1 数据库存储：爬取的数据需要进行存储，可以选择合适的数据库进行数据存储，如MySQL、MongoDB等。
4.2 文件存储：对于一些小规模的数据，可以选择将数据存储在文件中，如CSV、JSON等格式。
4.3 数据管理：对于大规模的数据，需要建立合适的数据管理系统，保证数据的安全和可靠性。
从HTML代码中提取文字,去掉HTML的标记public static string NoHTML(string Htmlstring){//删除脚本Htmlstring=Regex.Replace(Htmlstring,@"<script[^>]*?>.*?</script>","", RegexOptions.IgnoreCase);//删除HTMLHtmlstring=Regex.Replace(Htmlstring,@"<(.[^>]*)>","",RegexOptions.IgnoreCase);Htmlstring=Regex.Replace(Htmlstring,@"([\r\n])[\s]+","",RegexOptions.IgnoreCase);Htmlstring=Regex.Replace(Htmlstring,@"-->","",RegexOptions.IgnoreCase);Htmlstring=Regex.Replace(Htmlstring,@"<!--.*","",RegexOptions.IgnoreCase);Htmlstring=Regex.Replace(Htmlstring,@"&(quot|#34);","\"", RegexOptions.IgnoreCase);Htmlstring=Regex.Replace(Htmlstring,@"&(amp|#38);","&",RegexOptions.IgnoreCase);Htmlstring=Regex.Replace(Htmlstring,@"&(lt|#60);","<",RegexOptions.IgnoreCase);Htmlstring=Regex.Replace(Htmlstring,@"&(gt|#62);",">",RegexOptions.IgnoreCase);Htmlstring=Regex.Replace(Htmlstring,@"&(nbsp|#160);","", RegexOptions.IgnoreCase);Htmlstring=Regex.Replace(Htmlstring,@"&(iexcl|#161);","\xa1", RegexOptions.IgnoreCase);Htmlstring=Regex.Replace(Htmlstring,@"&(cent|#162);","\xa2", RegexOptions.IgnoreCase);Htmlstring=Regex.Replace(Htmlstring,@"&(pound|#163);","\xa3", RegexOptions.IgnoreCase);Htmlstring=Regex.Replace(Htmlstring,@"&(copy|#169);","\xa9", RegexOptions.IgnoreCase);Htmlstring=Regex.Replace(Htmlstring,@"&#(\d+);","",RegexOptions.IgnoreCase);Htmlstring.Replace("<","");Htmlstring.Replace(">","");Htmlstring.Replace("\r\n","");Htmlstring=HttpContext.Current.Server.HtmlEncode(Htmlstring).Trim();return Htmlstring;}。
<<信息技术国内网页去重技术研究:现状与总结李志义 梁士金华南师范大学经济与管理学院 广州5100061摘要2针对国内2000-2010年之间有关网页去重技术的研究成果进行计量分析,重点从网页结构、网页特征、网页内容、同源网页、元搜索等方面总结和分析去重技术的基本研究现状,并兼论基于布尔逻辑模型与傅立叶系数的网页去重以及网页去重技术在一些特殊领域的应用研究。
1关键词2重复网页 同源网页 网页去重1分类号2TP391NationalR esearch on D eleti n g DuplicatedW eb Pages:Stat us and Su mm ary L i Zh iyi L iang Sh ijinEcono m ic &M anagement Co ll ege o f Sout h Ch i na N or m al U niversity ,G uangzhou 5100061Abstract 2Th is paper uses the bi b lio m etric m ethod t o ana l yze the nati ona l resea rch fi ndi ngs on the technology o f de leti ng dup licated w eb pag es i n the y ea r of 2000-2010,s umm aries and ana l yzes its basic status fro m structure ,character istics ,conten ts ,hom o l ogy w eb pages ,m eta search ,e tc .It also d i scusses t he techno l ogy o f de l e ti ng dup licated w eb pages based on Boolean log i c m ode l and F our ier coe fficien t ,and its app lied resea rches i n som e spec ial fie l ds .1K ey word s 2duplica ted web pages ho m o l ogous pages de l e tion o f dup licated w eb pages收稿日期:2010-10-15 修回日期:2010-12-20 本文起止页码:118-121,93 本文责任编辑:徐 健互联网发展至今,就其开放性、共享性等特点和对人类的影响而言,无疑成为20世纪最伟大的创造。
搜索引擎对⽹页去重技术算法-⽤来解析伪原创与⽹页相似度⾸先，搜索引擎对所索引的所有⽹页进⾏页⾯净化和内部消重。
任何⼀家搜索引擎在尚未进⾏复制⽹页判断这⼀操作之前都定然会有个⽹页净化和内部消重的过程。
搜索引擎⾸先要清除噪⾳内容，对⽹页内部的⼴告、版权信息、共同的页眉页脚部分等进⾏净化，然后提取出该页⾯的主题以及和主题相关的内容，⽤以排名⼯作，噪⾳内容是不计⼊排名权重之中的。
消重也差不多是这个意思，搜索引擎对其所收集的⽹页集⾥⾯主题相同或极端相似的，⽐如同⼀模板之中多次出现的共同代码，将其作为冗余内容，进⾏消除。
我们可以这样理解，最理想的状态之下，⼀篇原创⽂章，搜索引擎仅将标题和内容计⼊排名之中，其他全部都消除。
DocView模型就是⼀个⾃动分类和消重的模型，当然，不是⾮常准确。
⼤家可以简单了解⼀下，DocView模型包括⽹页表识、⽹页类型、内容类别、标题、关键词、摘要、正⽂、相关链接等要素，它通过提取DocView模型要素的⽅法应⽤在⽹页⾃动分类和⽹页消重之中。
通过了解以上内容，我们就能⼤致明⽩，同⼀篇⽂章，为什么放到两个完全不同模板的站点之上，搜索引擎仍然能够正确识别出这是⼀个复制页⾯的原因了吧。
其次，搜索引擎对净化的页⾯进⾏重复内容的判断。
那么搜索引擎具体是如何判断复制页⾯的呢?以下内容是北⼤天⽹搜索引擎的去重算法，⼤部分来⾃对《搜索引擎——原理、技术与系统》相关知识的整理，⼤家可以⾃⾏参考相关⽂档。
现有⽅法⼤致可以分为以下三类：1、利⽤内容计算相似2、结合内容和链接关系计算相似3、结合内容，链接关系以及url⽂字进⾏相似计算现有绝⼤部分⽅法还是利⽤⽂本内容进⾏相似识别，其它两种利⽤链接关系以及URL⽂字的⽅法还不是很成熟，⽽且从效果看引⼊其它特征收效并不明显，所以从实际出发还是选择利⽤内容进⾏相似计算的算法。
搜索引擎判断复制⽹页⼀般都基于这么⼀个思想：为每个⽹页计算出⼀组信息指纹(信息指纹，英⽂是Fingerprint，就是把⽹页⾥⾯正⽂信息，提取⼀定的信息，可以是关键字、词、句⼦或者段落及其在⽹页⾥⾯的权重等，对它进⾏加密，如MD5加密，从⽽形成的⼀个字符串。
文本批量去除html标签的方法
文本批量去除HTML标签有多种方法，下面我将从几个角度来回答这个问题。
首先，可以使用正则表达式来匹配和替换HTML标签。
例如，可以使用类似于`<.?>`的正则表达式来匹配所有的HTML标签，然后将其替换为空字符串即可去除标签。
这种方法适用于小型的HTML文本处理。
其次，可以使用专门的HTML解析库，如BeautifulSoup、lxml 等，将HTML文本解析为DOM树，然后提取其中的文本内容。
这种方法更适用于处理大型复杂的HTML文本，因为它可以处理各种嵌套和特殊情况。
另外，一些文本编辑器和IDE也提供了批量处理文本的功能，可以通过搜索和替换功能来去除HTML标签。
这种方法适用于不需要编写代码的简单文本处理任务。
总的来说，去除HTML标签的方法可以根据实际情况选择合适的
工具和技术。
无论选择哪种方法，都需要注意保留文本内容的完整性和格式。
希望这些信息能帮助到你。
基于关键长句及正文长度预分类的网页去重算法研究摘要：伴随互联网所包含网页数目的剧增，转载现象变得相当普遍。
作为提高搜索引擎服务质量的关键问题之一，网页去重技术已经成为网页信息处理最为重要的环节。
在对传统网页去重技术进行研究的基础上，针对网页正文的结构特征，提出了一种基于关键长句及正文长度预分类的网页去重算法的核心思想。
实验证明，该算法具有较高的召回率及准确率，在重复网页的过滤中有着较好的应用前景与较高的研究价值。
关键词：网页去重；关键长句；预分类0引言互联网的持续高速发展致使网站数目及其包含的网页数目均呈爆炸式增长。
为了使用户在海量信息中快速找到自己感兴趣的内容，搜索引擎应运而生，其重要使命在于准确、高效地为用户反馈有用的搜索结果。
而在网页数目剧增的同时，转载现象也变得相当普遍。
据统计，中国互联网中网页的重复率高达40%，搜索引擎的搜索结果中常会出现很多重复记录，这些重复信息不仅增加了搜索引擎的存储负担及查询效率，也使用户的体验度大大降低。
因此，如何快速、准确地发现内容相似的网页已经成为提高搜索引擎服务质量的关键问题之一，而网页去重技术也无疑成为网页信息处理最为重要的环节。
1网页去重技术的主要流程网页去重即是将所搜集到网页中的镜像及转载网页去掉的过程。
几乎所有的网页去重技术都是基于这样一个基本思想：为每个网页文档计算出一组指纹，若两个文档拥有一定数量的相同指纹，则认为这两个文档的内容重叠性较高，也即二者是重复网页。
网页去重的主要流程包括网页去噪、特征提取、编码压缩、网页相似度计算及相似文档聚类等5个基本步骤，如图1所示。
其中，网页去噪负责剔除网页中的干扰信息（导航、广告等）并提取文档的正文信息，以便提高网页解析的准确度；特征提取则是从网页文档中提取出可以表征网页信息的特征值，它可以是网页中的若干个片段或若干个词语，这些特征值组成一个特征向量，该特征向量主要用于计算网页间的相似度。
为了便于向量间相似度的计算，所得到的特征向量通常都需要进行编码压缩处理（如用哈希函数将文字特征串转化为数字串），这样不仅便于文档的特征存储，也可以提高相似度的计算效率。
文章编号：1007-757X(2009)8-0030-03基于HTML标记和长句提取的网页去重算法刘四维 章轶 夏勇明 钱松荣摘 要：提出了一种高效的算法来去除互联网上的重复网页。
该算法利用HTML标记过滤网页中的干扰信息，然后提取出能表征一张网页的长句作为网页的特征。
通过分析两张网页所共享长句的数量，来判断两张网页是否重复。
该算法还利用红黑树对网页的长句进行索引，从而把网页去重过程转换为一个搜索长句的过程，减小了算法的时间复杂度。
实验结果表明该算法能够高效，准确地去除重复的网页。
关键词：网页去重；页面去杂；长句；红黑树中图法分类号：TP393文献标志码：A0 引言在信息时代里，互联网上丰富的网页信息被广泛的应用到了各个领域，如信息检索，数据挖掘等等。
然而互联网上存在大量重复的网页信息，重复的网页会给这些应用带来很大的问题。
例如，在搜索引擎方面，重复的网页会无谓的增加索引的开销；在使用网页信息构建语料库时，重复的网页也会降低语料库的质量。
因此如何检测并去除这些重复的网页就显得十分必要。
本文介绍了一种基于HMTL标记和特征句提出的算法来判断网页是否重复。
该算法首先利用HTML标记对网页进行必要的“去杂”处理，以去除干扰信息，净化网页。
然后提取出能表征这个网页的特征句，最后通过分析两张网页所共同拥有的特征句的数量来判断网页是否重复。
1 相关工作目前很多页面去重算法通过分析网页的内容，提取出网页的特征来判断网页是否重复。
例如文献[2]中所提出的基于shingle的聚类算法。
该算法把文章中连续的k个单词组成一个shingle，如果同时出现在两篇文章里的shingle的数量足够多，那么就认为这两篇文章是相似的。
同时文献[2]还提出了一个用文章中shingle的子集来表征文章的方法，这样可以减小需要计算和存储的数据。
文献[3]对文献[2]做了进一步的扩展。
本文中所提出的算法利用HTML标记去除网页中的干扰信息，然后通过分析比较两张网页的特征句来判断网页是否重复。
2 基于HTML标记的页面去杂2.1 干扰信息的定义每张网页除了正文外，还有很多其它的“干扰信息”。
这里我们把干扰信息定义为网页中与正文无关的内容。
由于这些信息和网页的正文无关，因此比较它们是没有意义的。
并且不同的网页具有的干扰信息差异很大，会影响比较结果的正确性。
网页上的干扰信息可大致分为以下三类：1，导航信息和广告信息。
2，HTML标记。
3，正文中，转载者引入的额外信息。
例如，在一篇文章的开头可能会有关于这篇文章的介绍，来源等等；在文章的末尾也可能会有一些转载者的评论。
为了避免干扰信息的影响，就需要先去除这些信息，我们把这个过程称为“页面去杂”。
2.2 页面去杂目前的去杂方法，大多通过删除网页中的HTML标记来实现，这可以很好的去除第二类干扰信息。
另外，由于很多导航和广告信息多以链接形式出现，因此可以去除网页中的链接。
然而这些信息除了链接外，还附加有相关的文本信息。
例如广告除了有指向某个网页的链接外，还会有一些描述信息，对于这些信息上述方法就无法去除了。
另外对于第三类干扰信息，这样的方法同样无能为力。
通过对大量网页的分析，我们发现网页的正文和干扰信息有以下两个特点。
第一，通常干扰信息和正文有着不同的文本格式，如字体大小，字体颜色，字体风格等等。
这些不同的文本格式都是通过HTML标记来实现的。
第二，通常网页正文占整个网页内容的比例（字数）较其它干扰信息所占比例大很多（少数正文内容过于短小的网页除外）。
考虑到以上两个特点，可以利用HTML标记来实现对干扰信息的去除。
我们可以解析HTML标记，找出具有相同格式，且占整个网页内容比例最大的部分，并认为这就是网页的正文。
以上方法可能会带来两个问题。
一是文章正文内的标题等内容，可能与正文有着不同的格式，因此这些内容会在去杂过程中被删除。
但这些内容较正文所占比例很小，因此可以忽略。
另一个问题是，如果正文内容较短，那么正文内容也可能被当作是干扰信息而被删除。
但考虑到过于短小的文章所具有的语义太少，大多数应用（如语料库的构建）所需的通常都具有较长的正文，语义信息丰富的文章，因此不用过多考虑正文过于短小的网页。
最后，考虑到第三类干扰信息（转载者所添加的简介，来源和评论等），以及未能完全去除的导航，广告等信息，———————————作者简介：刘四维，复旦大学通信工程系，硕士研究生，上海 200433 章轶，复旦大学通信工程系，硕士研究生，上海 200433夏勇明，复旦大学通信工程系，实验师，上海 200433钱松荣，复旦大学通信工程系，教授，上海 200433·30·通常出现在正文的头部或尾部，因此为了进一步净化页面，我们可以去除由前面的去杂过程所得到的正文的头部和尾部各一部分。
这里我们去除正文内容的前10%和后10%，只保留中间的80%，这样就可以进一步净化正文内容，同时保留了网页正文的主体内容。
综上，页面去杂主要由以下几个方面组成：1、去除网页中的链接信息。
2、找出网页中具有相同格式且占整个网页内容比例最大的部分作为网页的正文。
3、去除网页中HTML标记。
第3步和第2步通常同时进行。
4、去除第3步中所得到的正文的头部和尾部各一部分。
通过以上的页面去杂流程，就可以尽可能多的去除那些干扰信息，使后面的比较算法更加准确。
注：在下面的内容里，当我们提到网页时，都是指已经经过页面去杂后得到的网页正文。
3 网页去重算法比较网页是否相同时，不必考虑语义相关性。
因为相同的文章语义肯定相同，但语义相同的文章，在大多数情况下并不相同。
我们可以借用信息检索领域的VSM模型[5]来比较两张网页是否相同。
把网页中的每个字提取出来（由于不用考虑语义，因此不必进行分词操作），然后统计每个字在该网页中出现的次数（字频），并用这些统计数据构成一个字频向量。
然后以两张网页所对应的字频向量夹角的余弦值作为这两个网页的相似度，当该余弦值大于某个阀值时，我们就认为这两张网页相同。
由于要对网页进行两两比较，所以如果数据库里有n张网页，那么其时间复杂度就是O(n2)，因此该模型并不可取。
3.1 提取长句作为网页特征目前的大多数算法都是通过提取网页的特征，然后通过比较这些特征来判断网页是否重复。
例如前面提到，文献[2]提取网页的shingle作为特征，然后通过比较两张网页共享shingle的数量来判断两张网页是否相同。
然而该算法对shingle的选择过于随机，很容易把一些常用的单词排列当作一张网页的特征。
例如，如果取shingle的长度为3，并随机地选择shingle。
那么对于“in a word”这类大量出现在网页中的常用短语，被选中的几率就很大。
但是这类shingle 并不能很好的表征和区分网页，因此会影响去重结果的正确性。
我们应该提取网页中有区分度的部分，并利用摘要算法对其进行变换，以此作为网页的特征。
这里要注意特征长度的选取。
如果选取的特征太长，例如一个段落，那么该特征就很容易受到干扰（两个段落即使只有一个字不同，也会导致摘要结果的截然不同）。
相反，如果选取的特征太短，例如词语，那么该特征可能在多个网页中出现，导致这些特征不能很好的区分网页。
本文针对中文的特点，提取一张网页中的“长句”作为该网页的特征。
以下是我们对长句的定义。
首先以标点符号（逗号，句号，感叹号等）为分隔符，把网页拆分为多个“句子”。
这里的“句子”有别于语法上定义的用句号分隔的句子。
我们用下面的文本作为分隔的示例。
“首先，该算法对网页进行去杂处理，然后提取出文中的长句作为网页的特征。
”这段文本在语法上是一个句子，我们利用标点符号把该句拆分，可以得到以下三个“句子”。
“首先”，“该算法对网页进行去杂处理”和“然后提取出文中的长句作为网页的特征”。
注：下文中所提到的句子均指利用上述方法得到的“句子”。
我们把长句定义为句子长度不少于k个字的句子。
如果取k=8，那么上面的例子中第1个句子（2个字）就不是长句，第2和第3个句子（12和17个字）是长句。
长句能够很好的表征和区分网页，因为，一方面可以保证这些特征不太容易重复。
中文里有6700多个汉字，那么两个句子重复的概率约为1/(6700k)，当k较大时这是一个非常低的概率。
另一方面，由于句子是由标点符号隔开的，相对于一个完整的段落要短很多，被干扰的概率也较低。
一张网页，尤其是较长的网页，所能提取的长句可能会很多，为了减小存储特征所需的空间，我们仅使用所有长句中最长（字数最多）的m个句子。
对于不足m个句子的网页，则保留所有的长句。
接着我们使用MD5算法计算出这些长句的摘要，并以这些摘要作为网页的特征。
MD5算法可以把任意长度的数据作为输入，然后产生一个128比特（16字节）的摘要作为输出。
在定义长句时我们取k=8，即每个句子至少8个汉字（16个字节）。
利用MD5算法，即使超出8个汉字的长句也能用16个字节来表示，从而节省了存储空间。
MD5所产生的128比特的空间是非常大的，为了进一步减少特征所需占用的存储空间，还可以使用其它摘要算法来缩小这个空间。
例如文献[2]中使用Rabin摘要算法[4]，为每个shingle 产生一个40比特的摘要。
如上所述，一张网页的特征被定义为：其中S为该网页的长句集合，|S|表示集合S拥有元素的数量。
3.2 对于重复的定义文献[2]中，作者用一个shingle集合来表征一篇文章，并使用以下方程来定义A，B两篇文章的相似度。
|()()|(,)|()()|S A S Br A BS A S B∩=∪其中S(A)和S(B)分别表示A和B的shingle集合。
类似于上述定义，在本文中，我们把A，B两篇文章的相似度定义为：|()()||()()|F A F BSimF A F B∩=∪其中F(A)和F(B)分别表示A，B两张网页的特征集合。
Sim是一个介于0和1之间的值，如果两张网页的特征集合完全相同，那么Sim为1；相反，如果两张网页的特征集合完全不同，那么Sim为0。
Sim越大，说明两张网页共享的特征值就越多，那么这两张网页的相似度就越大。
因此我们定义，当通过两张网页的特征集合所计算出来的相似度Sim，大于某个给定的阀值时，我们就认为这两张网页是相·31·同的。
3.3 建立特征索引，去除重复网页为了降低页面去重过程的复杂度，需要对网页的特征进行索引，然后把去重过程转换为一个搜索过程。
有的算法采用二叉搜索树索引，但在最坏情况下，该树的查找和插入时间复杂度为O(n)。
本文采用红黑树[1]来建立网页特征的索引。
红黑树是一种平衡二叉搜索树，在最坏情况下，其查找和插入的时间复杂度均为O(lg n)。
红黑树的每个节点由两部分数据组成：特征值和拥有该特征值的网页编号。
