随着近年来互联网技术和规模的空前发展，Internet已经成为获取信息的主要渠道之一。截至2007年7月的调查中，共统计约1亿2千5百多万个网站［1］。搜索引擎因其方便快捷的检索功能，成为当今网络用户进行信息检索的主要工具，而其中信息检索的质量及其工作效率将直接影响到搜索引擎的整体性能。根据中国互联网络信息中心2005年7月发布的统计报告显示，用户在回答“检索信息时遇到的最大问题”这一提问时，选择“重复信息太多”选项的占44.6%，排名第1位［2］。面对海量的数据，用户不愿意看到一堆内容相同或近似的数据，如何更为快速、准确地帮助用户获取所需要的信息，是网络信息服务面临的新课题。
我们常把句法、结构完全相同的文档视为重复文档。但本文所指的近似网页是指正文内容基本相同的网页，而不论其句法、结构是否完全一致。
重复文档的去除采用传统的剽窃检测技术很容易完成，但对于内容近似的文档检测就不那么容易了。本文提出的近似网页去重算法DDW（Detecting near-Duplicate WebPages），兼顾考虑网页的语法和语义信息，提取特征向量进行文档的表示；并充分利用检索系统和分类信息进行近似网页检测和排查。
一.网页在重复方面的特点,归纳如下:
(1)重复率高。网页的重复主要来自转载。网页转载非常容易。由于用户兴趣的驱动,网络信息流通中人们通过复制方式进行信息共享,经典的文章,以及新闻网页,很容易引起人们的关注,有时转载竟高达几十次之多。
(2)存在噪声。转载时一般都“原样照搬”,保持文本内容和结构的一致,并尊重版权,在开头加入了引文信息。可是引文会导致复制的文本与原文不完全一致,本文把这种造成转载文章与原文不同的情况称为网页噪声。还有一些其他情况引入噪声,如一般各个网站网页的生成环境和版面的风格不同,转载的文本有时需要还HTML语言和XML语言内部格式的转换,造成内部格式的不完全一致。另外,插入的广告图片也是噪声的主要来源。
(3)局部性明显。主要表现在转载内容的局部性和转载时间的局部性。前者是指转载的内容主要偏向于人们关注的热点且权威网页,其他网页转载的相对较少。后者是指转载的时间比较集中,大都在一两天内进行转载,十天以后再转载则很少。
这里所指的重复网页指因转载形成的重复网页,对原网页再编辑或截取部分内容造成的网页视为不同网页,因为此时信息量发生了变化。重复网页的文本经过提取并去除噪声后,在内容和结构方面能够保持高度一致,本文正是利用了这个特点实现网页去重。
二、现有去重方法简介
当前,提出的网页去重的方法还比较少,主要沿用信息发布系统中相同或相似文档的探测或去重时应用的方法,代表性方法主要有:基于聚类的方法,排除相同URL方法、基于特征码的方法,下面做一下简要分析。
(1)聚类的方法:该方法是基于网页文本内容,以6763个汉字作为向量的基,文本的汉字字频就构成了代表网页的向量。通过计算向量的夹角决定是否是相同网页。特点:方法简单,易于实现。不足:对大规模网页,聚类的类别数目庞大,难以确定,聚类复杂度O(n2),计算时间长;只计算字频,没有利用文本的结构信息;实时性差,对于新网页需要重新聚类决定是否重复。因此,实际应用中难以适用。
(2)排除相同URL方法:各种元搜索引擎去重的主要方法。它分析来自不同搜索引擎的网页URL,相同的URL认为是相同的网页,给予去除。特点:方法简单,易于实现,可去除一部分相同网页。不足:未利用网页的文本内容结构信息,不能对转载造成的重复网页去重。
(3)基于特征码的方法:这种方法利用标点符号多数出现在网页文本中的特点,以句号两边各五个汉字作为特征码来唯一的标识网页。因为特征码的精确匹配可以与先进的检索系统联系起来,去重效率较高,不失为一种好方法。然而,该方法也存在不足:特征码的精确匹配不能抵抗网页转载时产生的噪声;没有利用网页文本结构信息,会发生长度不同,甚至悬殊的文本会看成相同网页;作为产生特征码的标志的句号有时不会在网页文本中出现,或只出现在文章末尾,有时在版权信息和超链接中出现,这些都会导致特征码的产生错误。
三、基于特征串的去重算法设计
(1)网页的文本提取
观察网页的版面结构,位于版面中间是网页的文本信息,文本提取就是要把这部分提取出来并尽可能去掉噪声。在文本区上方通常是广告条、导航条、网站标志等信息,左右两侧是网页的超链接,下方是文本的相关超链接,底部一般是网站版权声明。
高质量的网页去重算法必须是基于网页文本内容的,因此在网页去重前必须提取出网页的文本,提取出的文本质量直接决定着去重的效果。提取文本的难点主要在于去除网页噪声,虽然利用模板滤除一些噪声,但通用的模板很少。而要滤除随机产生的噪声则更困难。本文采用两遍扫描来提取网页文本。第一遍扫描,利用HTML语言或XML语言的标记提出文本的标题,过滤掉无关的标记和超链接,并进行一些必要转换。在过滤时保留必要的占位符和文本的结构信息和一些半结构化信息。第二遍扫描,利用文本的结构信息、标点、和一些必要的模板提出网页的文本内容,保留段落信息。至此,已把网页文本提出。
(2)特征串的抽取
为保留文本特征串的内容、结构信息,采用如下设计思想:采用“自然语句分隔标志”(简称为分隔标志)将文本切成若干“句子”,从“句子”中抽取若干字符或汉字作特征码,然后按照“句子”在文本中的顺序把特征码连接起来构成特征串。由于把文本看作字符流且不需保留语义信息,所以分隔标志可以是任何符号,但为保持“句子”划分的均匀性,通常采用高频字符,如“。”、“?”和“的”等。这样得到的特征串只保留了文本内容(特征码内容)和结构(“句子”的顺序)信息。在抽取特征码时可依据具体需要设定抽取的字符或汉字个数,本文在“句子”的两端分别抽取相等的字符或汉字作为特征码。举例:图1给出本文部分摘要的特征串,其中分隔标志取“。”和“,”并在“句子”的首尾各抽取一个字符或汉字
(3)重复度评价函数的设计
(4)效率的优化
确定系统评价函数后,可通过两两匹配进行网页去重,但O(n2)的计算复杂度对大规模网页不适用。这里利用文本进行散列处理。
-
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术，将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外，均为转载,整理或搜集自网络.欢迎任何形式的转载，转载请注明出处.
转载请注明：文章转载自:[169IT-IT技术资讯]
本文标题:中文网页快速去重算法研究
