网页去重策略和实现

网页去重的策略和实现0 引言互联网时代的到来，极大地影响了人们的日常生活，改变着人类的生活习惯。同时，也给人们带来了极大的便利。人们越来越喜欢通过搜索引擎来查找自己想要得到的内容和信息，这是搜索引擎技术的机遇，然而也是挑战，因为人们的要求也越来越苛刻。在我们用搜索引擎搜索信息的时候，常常会遇到这样一种情况：很多内容相同或相似的网页会被搜索引擎提交给我们。这对用户来说，是很不便利的，不仅浪费了时间，也占用了大量的资源。同时，也降低了搜索引擎的服务效率。因而网页去重技术也慢慢被人们重视起来。网页去重的算法有很多种，本文重点介绍一种基于网页中文字主题要素的网页去重算法。1网页去重的理论基础1.1搜索引擎搜索引擎是指根据一定的策略、运用特定的计算机程序从互联网上搜集信息，在对信息进行组织和处理后，为用户提供检索服务，将用户检索相关的信息展示给用户的系统。搜索引擎包括全文索引、目录索引、元搜索引擎、垂直搜索引擎、集合式搜索引擎、门户搜索引擎与免费链接列表等。搜索引擎的工作原理：第一步：爬行搜索引擎是通过一种特定规律的软件跟踪网页的链接，从一个链接爬到另外一个链接，像蜘蛛在蜘蛛网上爬行一样，所以被称为“蜘蛛”也被称为“机器人”。搜索引擎蜘蛛的爬行是被输入了一定的规则的，它需要遵从一些命令或文件的内容。第二步：抓取存储搜索引擎是通过蜘蛛跟踪链接爬行到网页，并将爬行的数据存入原始页面数据库。其中的页面数据与用户浏览器得到的HTML是完全一样的。搜索引擎蜘蛛在抓取页面时，也做一定的重复内容检测，一旦遇到权重很低的网站上有大量抄袭、采集或者复制的内容，很可能就不再爬行。第三步：预处理搜索引擎将蜘蛛抓取回来的页面，进行各种步骤的预处理。除了HTML 文件外，搜索引擎通常还能抓取和索引以文字为基础的多种文件类型，如 PDF、Word、WPS、XLS、PPT、TXT 文件等。我们在搜索结果中也经常会看到这些文件类型。 但搜索引擎还不能处理图片、视频、Flash 这类非文字内容，也不能执行脚本和程序。第四步：排名用户在搜索框输入关键词后，排名程序调用索引库数据，计算排名显示给用户，排名过程与用户直接互动的。但是，由于搜索引擎的数据量庞大，虽然能达到每日都有小的更新，但是一般情况搜索引擎的排名规则都是根据日、周、月阶段性不同幅度的更新。1.2 查全率和查准率查全率是指，查询关键词时，搜索引擎返回的相关网页数与全部相关网页数的比率。假如包含某关键词的网页实际上有N个，而搜索引擎真正检索的只有M个，那么这个关键词的查全率就等于MN100%。查全率是衡量搜索引擎检索是否全面的度量指标。查全率越高，则表示搜索引擎的全面检索能力越强。查准率是衡量某一检索系统的信号噪声比的一种指标，即检出的相关文献与检出的全部文献的百分比。普遍表示为：查准率=（检索出的相关信息量/检索出的信息总量）x100%。检索系统中的匹配，分为精确匹配和模糊匹配，在文献检索时应根据需要选用。本文在利用模糊匹配方式提高查全率的同时，还利用基于中文字主题要素的网页去重方法来提高查准率。1 网页重复的原因和其他去重方法21 网页重复的原因搜索过程中产生重复的原因主要有两个，一个是由于URL本身的构造原因产生搜索结果重复。例如，虚拟主机技术可能会使得多个不同域名映射到同一个IP，当搜索系统用这些域名进行搜索时，实际上搜索到的是同一个站点，导致搜索结果重复。这一类由于URL本身导致网页重复的问题相对来说比较容易解决，例如，可以通过建立IP与域名的对应表、比较网站前几页网页代码等方式解决。网页重复的另一个重要原因是不同网站之间对相同的内容重复引用或同一站点在不同物理位置的镜像等而导致的，这对于一些热点内容和重要站点尤其如此。对于这类情况，由于大量重复网页不是直接对原有网页进行复制，而是将转载引用的内容放到自己网页的某个特定位置再提供给用户，或者在镜像时定制了网页的内容。这样，新的网页就可能在风格、布局、代码方面与原有网页有很大的差别，因而不能使用网页的形式特征来对网页消重，消重的依据只能是根据网页的内容特征。22 其他去重方法 目前, 网页去重代表性方法有3种。 1)基于聚类的方法。该方法是基于网页文本内容以6763个汉字作为向量的基, 文本中某组或某个汉字所出现的频率就构成了代表网页的向量, 通过计算向量的夹角确定是否是相同的网页。 2)排除相同URL方法。各种元搜索引擎去重主要采用此方法。它分析来自不同搜索引擎的网页URL, URL 相同, 即被认为是相同的网页, 可将其去除。 3)基于特征码的方法。这种方法利用标点符号多数出现在网页文本的特点, 以句号两边各5 个汉字作为特征码来唯一地表示网页。3 基于文字主题要素的去重方法 选择主题词就是把主题概念转换成检索语言。 选词的广度和专指度对查全率和查准率起着关键作用, 使用规范的主题要素可以达到最佳的检索效果。 本文针对同一网络资源在不同网页中的不同文字描述进行去重, 对网页内容做出客观的分析和学习以达到网页去重的目的, 规范网页中文字的主题要素, 建立时间、来自于何处(版本、格式、厂家、主要行使人、地点等)与目的之间的关系, 通过建立这些关系可以表明用户按照自己的偏好查找网页的大致内容。在进行抽取的时候, 不管是时间短语、 来自于何处短语, 还是 目的短语, 都是句子修饰的一部分, 应尽量依照标点分割的方法, 把一句话分成几块, 再把 块分解成时间、 来自于何处、目的短语, 然后依照1个名词、1个动词相隔的查询方法进行抽取, 先在发现短语的这个 块中查找, 找不到再去相邻的块查找 。对这类短语, 在抽取的过程中规定了一些抽取的规则, 保证了所有抽取的一致性。 最后是提取核心词的途径, 主要有以下2种: 一是利用词表选词, 从所使用检索工具提供的主题词表查取, 如不同领域文摘的索引指南、名字及各类中文词的索引库等; 二是初查选词, 如果在词表中没有查到, 先选择课题关键词在题名字段或关键词字段进行初查, 然后, 浏览文献记录, 在主题词或叙词字段得到规范核心词, 但一定要在主题词或叙词字段检索。抽取的方式可以分为以下几种(以下加小括号的便是可根据用户的偏好进行抽取的)。 1) 来自于何处短语+ 时间短语+ 来自于何处短语+ 目的短语原文: 中国国务院总理温家宝/where当地时间2月2日下午/ time在英国剑/where(发表演讲/purpose) , 演讲中/p阐述应对全球性金融危机中国政府三点主张/purpose。抽取后: 温家宝/where2 月2 日/ time 剑桥/where阐述应对危机三点主张/purpose提取的核心: 温家宝/n 剑桥/n阐述/v三点主张/n 2) 来自于何处短语+ 目的短语+ 名词 原文: 郑州市/where最便宜的/ purpose日本料理店/n 在/v 中原路与花里路交叉口向东50米/where 抽取后: 郑州市/where最便宜的/ purpose日本料理店/n 提取的核心: 郑州/ns 最便宜的/adj 日本/ns 料理店/n 3) 来自于何处短语+ 名词+ 来自于何处 短语+ 动词+ 名词+ 动词 原文: (北京市消防局/where) 今日/ time举行/v发布会/n通报/v央视新址北配/where发生/v火灾/n因/c 业主/where 燃放/v 烟花/n 所致/c 1 /m死/v7 /m (伤/v) 抽取后: 央视新址/where 火灾/n 因/c 业主/where燃放/v烟花n所致/c1 /m死/v7 /m(伤/v) 提取的核心: 央视/n 新址/n 火灾/n 业主/n死/v 4) 时间短语+ 来自于何处短语+ 目的短语+ 目的短语 原文: 2009年/ time瑞星杀毒软件/w here 最新更新/purpose包21。 22。 01 /n (路虎网/where) 提供/v免费下载/purpose 抽取后: 2009年/ time瑞星杀毒软件/w here最新更新/purpose免费下载/purpose 提取的核心: 2009 /n 瑞星/n 最新更新/adj 免费/adj 下载/v4 网页去重方法的实现 由于是根据网页中文字的主题要素去重, 所以抽取的内容就需要采用句子的模糊匹配来进行网页重复性的度量。 算法设计如下。 1) 把要标识的网页定义为Ui, 抽取出来的短语分别表示为T (time), W (where), P (purpose), 相对应短语抽取的句子表示为Y, 句子里面的词分别表示为n, v, a。 也就是可以把一个网页表示为U =T ( Y( ( n ) , ( v), ( a ) ) ) + W ( Y( ( n) , ( v) , ( a ) ) ) +P ( Y( ( n) , ( v) , ( a) ) ) 。 2) 计算抽取词的短语相似度M sim = n + v +a /N + V+ A, 其中n 为相似的名词的总数, v 为相似的动词的总数, a为相似的形容词的总数, N 为句子里名词的总数, V为句子里动词的总数, P 为句子里形容词的总数。3) 计算抽取短语的句子相似度Y sim = t+ w +p /T + W + P, 其中t为相似的时间短语的总数, w为相似的来自于何处短语的总数, p 为相似的目的短语的总数, T 为句子里的 时间短语的总数, W 为句子里来自于何处短语的总数, P 为句子里目的短语的总数。由于抽取的不确定性, 在计算抽取的句子的相似度的时候, 不能只考虑抽取的名词和动词, 在这里还加入了抽取的核心词的比较, 并把抽取的核心词定义为co。 4) 计算抽取的核心词的相似度C sim = co /C, 其中co为比较以后一致的核心词的数量, C 为抽取的核心词的总数。5) 利用2) 3) 4) 的结果, 计算所针对句子的精确相似度为S sim = (M sim + Ysim + C sim) /3。 通过比较相似度, 得出匹配一致的句子总数为s, 抽取出来的句子总数为S。6) 由5) 的结果可计算出网页中文字的相似因子U sim = s / min(S i, S j), 其中S i, S j 分别表示第i, j个网页里抽取出来的句子总数。 为了能够准确地比较网页内容的真实性, 在这里考虑到了语言描述的误差, 把抽取出来的短语总数定义为B, 通过比较短语相一致的短语总数为b, 然后比较抽取出来匹配的句子对应的短语相一致的总数为B sim。7) 计算短语的匹配一致性B coherence =b /B sim。8) 计算短语的可靠因子B credibility= b /B。9) 在以上步骤的基础上给出重复度的评价函数RM = (B, B coherence, B credibility, U sim), 通过预先设定的B, B coherence, B credibility, U sim 与得到的4个参数来进行比较。 在这里把B, B credibility 这2个参数作为判断网页是否重复的标准, 而通过B coherence, U sim 这2个参数来对网页进行去重, 如果大于所给定的初始的B coherence, U sim, 那么RM =1, 认为2篇新闻内容是重复的, 其中1篇可以被替代, 在替代的时候暂且选择内容少的新闻被替代;否则RM = 0, 认为2篇新闻内容是不重复的, 是不可以被替代的。5 结语本文提出的基