搜索引擎去重算法的研究与实现 南京廖华

  本文关键词：搜索引擎去重算法的研究与实现，由笔耕文化传播整理发布。

搜索引擎去重算法的研究与实现

一.什么是无效信息

搜索引擎作为一项网络应用，已经成为人们查询信息的重要工具之一，它可以使人们从Intemet大量纷杂的信息中，找到与主题相关的信息，为人们查询信息提供了方便。但是由于中文自身的特点，目前的搜索引擎存在着很多的问题，它只解决了信息查询的问题，而从信息资源覆盖面、检索精度、信息的输出方式等许多方面来看，检索结果的查全率和查准率不是很高，将Web挖掘技术应用到搜索引擎领域，将会给用户提供一个高效、准确的Web检索工具。目前，Web用户主要是使用搜索引擎在互联网上检索信息，但目前的搜索引擎往往返回给用户成千上万个检索到的页面，且其中很大一部分是重复的或与用户检索要求不相关的内容。这些内容被认为是无效信息。

二.搜索引擎的分类

结合互联网信息的特点，搜索引擎形成了三个不同的类型：

1、全文检索搜索引擎：全文搜索引擎是名副其实的搜索引擎，国外具代表 性的有Google(http：／／www．google．com)、yahoo(http：／／search．yahoo．tom)、AllTheWeb(http：／／www．alltheweb．tom)等， 国内著名的有百度(http：／／www．Baidu．com)、中搜(http：／／www．zhongsou．com)。它们都是通过从互联网上提取的各个网站的信息(以网页文字为主)而建立的数据库，检索与用户查询条件匹配的相关记录，然后按一定的排列顺序将结果返回给用户，也是目前常规意义上的搜索引擎。

2、目录搜索引擎：目录索引虽然有搜索功能，但在严格意义上算不上是真正的搜索引擎，仅仅是按目录分类的网站链接列表而己。用户完全可以不用进行关键分类目录也可找到需要的信息。国外比较著名的目录索引搜索引擎有yahoo(http：／／www．yahoo．com)Open Directory Project(DMOZ)(http：／／www．dmoz．tom／)、LookSmart(http：／／www．100ksmart．com)等。国内的搜狐(http：／／www．sohu．com)、新浪(http：／／www．sina．com)、网易(http：／／www．163．com)搜索也都具有这一类功能。

3、元搜索引擎：元搜索引擎在接受用户查询请求时，同时在其它多个引擎上进行搜索，并将结果返回给用户。著名的元搜索引擎有Dogpile(http：／／www．dogpile．corn)、Vivisimo(http：／／www．vivisimo．com)等，国内元搜索引擎中具代表性的有搜星搜索引擎(http：／／www．soseen．corn／)，优客搜索(http：／／www．yok．com)。在搜索结果排列方面，有的直接按来源引擎排列搜索结果，如Dogpile，有的则按自定的规则将结果重新排列组合，如Vivisimo。

4、其他的像新浪(http：／／search．sina．corn．cn)、网易(http：／／search．163．com)、A9(http：／／www．A9．com)等搜索引擎都是调用其它全文检索搜索引擎，或者在其搜索结果的基础上做了二次开发。

三.搜索引擎的缺陷

据MORI民意调查，只有18％的用户表示总能在网上查到需要的信息，68％ 的用户对搜索引擎很失望，28％的用户表示还可以，4％的用户不知道。总之， 搜索引擎在准、全、新、快等方面还存在着严重的缺陷和问题，需要加以完善。

目前搜索引擎存在的缺陷或者说问题，可以归纳为以下几个方面：

1、从信息的完备性来看

目前搜索引擎的数据库规模和覆盖面是极其有限的。美国科学期]：lJNature 的一篇报告中指出，最大的搜索引擎也只能覆盖现在网页资源的16％，美国NEC 研究所的SreveLawrence和C1LeeCiles两位博士研究表明，现在的搜索引擎漏掉大约84％的网页信息。在这一方面存在的主要问题是：①搜索引擎之间缺乏协作和联合。各个搜索引擎都有自己一套的分类体系、标引方法、索引方法、数据库结构和检索界面，缺乏统一的规范性的控制，因此，各搜索引擎之间的数据资源的兼容性和互操作性差，缺乏资源共享的基础。同时又由于各搜索引擎之间没有分工合作，因此，各搜索引擎的数据资源交叉重复现象严重。②缺乏大型、集成、综合性的元搜索引擎，而垂直搜索引擎发展不快，许多专业性的搜索引擎对搜索目标、服务对象、主题范围及类型等定位模糊。③许多有实力的大型的搜索引擎(女IGoogle和百度等)仍在盲目追求数据库规模，提供的信息服务都很大众化，缺乏深度以及个性化，查准率不高。④忽视对tEWeb信息资源的收集。

2、从查全率和查准率来看

据权威机构统计，因特网上约有100多亿个网页，而世界上目前搜索量最大 的Google也只能搜索33亿网页，就是说再大的搜索引擎也不可能使查全率达到 100％。而且据excite统计，只有不到1％的用户会看200条以后的结果，几乎100％的用户不会查看超过1000条的结果[71。就是说对于大多数用户来说，查全率是次要的，而查准率则更具有意义。在这一方面存在的主要问题是：①对于多数检索课题而言，不是输出的检索结果过载，记录数量达到成千上万条，给用户的相关性判断带来困难：就是零输出或输出量太少，造成过分的漏检。②由于网站或网页的标引类型、标引深度、索引方法等的不规范，多数搜索引擎又不支持概念检索，因而直接影响检索词的选择、匹配和检索结果的输出格式，从而影响了查准率。③由于目前各种搜索引擎是按即定的相关度对检索结果进行排序的，而各种检索引擎对相关度参数的选择、计量和算法又各异，这就难免不与用户的检索目标相冲突，因而会人为地影响到查全率和查准率。④在检索功能方面的主要缺陷是关键词检索和主题分类检索不能有机的结合起来，多数搜索引擎不提供概念检索(即主题检索)，对自然语言理解力差，而检索式的构造难度大，更难提供多媒体检索。总之，这一切都影响着搜索引擎的检索效率和效果。

3、从信息的输出方式来看

据专家测评，目前主要的搜索引擎返回的相关结果其比率不足45％。据估计，当键入1个关键词后，在百度搜索的结果中总会有70％"-'80％的无用信息，有时是100％的无用【引。在这一方面存在的主要问题是：①关键词检索输出的结果相关度排序方式单一，不能根据用户需要来选择信息输出的排序方法。②主题分类检索输出的往往只是网站，而不能快速准确地提供网页信息。用户登录到相关网站后又往往找不到所需要的信息无功而返。③不论是关键词检索，还是主题分类检索，信息输出的结果显示格式简单，不能向用户提供相关的更好的途径和信息。④数据更新速度慢，更新周期长，对于网上已不存在的网页不能及时删除，因而出现死链较多，而且也不加以说明，浪费用户的宝贵时间。⑤网站、网页经常处于动态的变化之中，新的页面不断涌现，旧的页面不断消亡，如果不及时维护，那么索引库中就会存留着许多无用的信息，就会导致成千上万条没有经过筛选与排序的记录被输出。

4、从界面的友好性来看

有人估计，83％的网站含有商业广告，只有6％的网站含有科学和教育的内 容。科研人员和普通大众受到搜索引擎提供的同样的信息待遇，两者都面临着信 息不对121的困惑【8】。在这一方面存在的主要问题是：①可供用户选择搜索条件和搜索结果的功能不多，多数搜索引擎没有类型、范围限定。②多数搜索引擎是面向主题检索，而不是面向用户检索，不能重复利用用户检索过的成果，更不能对特定的用户进行定题跟踪服务。③对自然语言理解有限，用户必须自己构造检索式来表达检索命题。由于各搜索引擎关键词检索所采用的符号及其含义、分类检索所建立的类目体系及使用规则各不相同，因此给用户构造检索式带来了困难。④网站简介不规范，有些太简，弄不清网站所包含信息的内容和范围，有些太繁，，如雾里看花，难识庐山真面目，还有些网站简介误导用户进入它的广告世界。⑤网页的帮助系统许多等于虚设，起不到帮助的作用，有的只是常识介绍，更是缺乏透明度。总之，搜索引擎当前存在的主要问题是：①查全率低。由于数据库规模偏小，对网络信息覆盖不全，因而搜索引擎收录信息的完备性差，导致查全率低，用户检索不到理想的信息。②查准率低。由于搜索引擎对网站网页标引不规范、对自然语言理解差、对索引数据库维护不及时等因素，导致查准率低，大量无用信息或不相关信息困绕着广大用户。

四无效信息的粒度

五.除无效信息的方法及优缺点

1.关键字提取技术分析

关键词提供了文档内容的概要信息，它们被使用在很多数据挖掘的应用中。 关键字提取是一项重要的文本检索技术，在Web页检索、文档聚类、文档摘要 提取、文本挖掘等方面都有广泛的应用19,101。正确地提取关键字可以让我们在大量的文档中快速地选出所需要的文档。近年来，随着大量文档的电子化，关键字提取的需求也就越来越大。例如，当我们浏览一个网页而希望快速了解其内容时，就可以通过提取关键字来实现。目前，针对英文的关键词提取的研究已经取得的较多的研究成果，方法也比较成熟。但是中文不同于英文，中文词与词之间没有明显的界限，存在一个分词的问题，致使中文关键词提取相对于英文困难些，这就使得中文信息检索的效率在一定程度上被限制了。

1.1关键字提取算法

关键字提取算法可分为两类：基于训练集的关键字提取策略和不需要训练集 的关键字提取策略【l51。基于训练集的方法将关键字提取视为分类问题，通过将文档中出现的词语划分到关键字类或非关键字类，再从关键字类中选择若干个词语作为关键字，该类算法由Peter．D．Tumey首次提出，其技术已日趋成熟。

不需要训练集的算法，可分为以下四类：基于统计的方法，如频率统计；基 于词语图的方法，如KeyGraph；基于词语网络的方法，如中介性指标

(BCBetweennessCentrality)；基于SWN的方法；上述四种方法都是建立在词频统计基础上。基于统计的方法简单快速，能够提取高频词语，却忽略对文档具有重要意义但出现频率不高的词语，因此提取的关键字具有片面性。基于词语图的方法需要设定的参数过多，如顶点数、边数等，因而常造成边界上的取舍问题，影响算法的稳定性和精度。基于SWN的方法是以平均距离长度为关键字提取依据，而SWN理论以连通图为基础，故对非连通的文档结构图，无法衡量顶点的重要性，也无法正确地提取文档关键字。

1.2TF*IDF方法

文本的形式化表示一直是搜索引擎、自动文摘以及文本检索等信息检索领域 关注的基础性问题。空间向量模型(Space Vector Model)qb的TF木IDF文本表示是该领域里得到广泛应用并且取得较好效果的一种文本表示方法。特征词权重用以说明该特征词在描述网页文档内容时所起的作用的重要程度【16】。特征词权重计算的目的就是要准确描述网页信息，所以权重计算的好坏直接影响网页信息描述的准确性。目前，比较成熟的方法就是使用TF*IDF来计算权重。该方法主要考虑以下三个因素：

特征词频率tf(term frequency)．该特征词在此网页文档中出现的频率。

特征词倒排文档频率idf(inverse document frequency)：该特征词在网页文档 集合中分布情况的量化，常用的计算方法是l。g(％+0．01)。其中Ⅳ为网页文档集合中的文档数目；n七为出现过该特征词的网页文档数目。

归一化因子(normalization factor)：对各个分量进行标准化。

特征词权重的优缺点。

(1)从表2．1可以看出，T4和T5分别在一个且仅在一个文档中出现，虽

然出现的文档频率不高，但仍分别在各自的文档中作为最能区别文档的特征词。

(2)Tl从表2．1显示，在文档textl和text2中出现频率都是最高的，而且

出现频率相等。因此，对于区别文档来说，T1不起任何作用，但是在两个文档 中T1的权重均大于T3的权重。这样的结果暴露出TF*IDF方法的缺点。 TF*IDF方法虽然考虑特征词在文档集合中分布情况，很大程度上提高了文

档表示的准确性。然而，它并没有考虑特征词在文档中的分布比例，而且对于网 页文档的特殊性，也没有考虑特征词分布的位置。

2.网页去重算法分析

随着互联网的发展，越来越多的网页出现在互联网上。随之带来的问题是网 页内容的大量重复。去除重复网页不但可以减少相似的搜索结果，减轻用户的阅 读负担，还可以压缩搜索引擎的索引空间，提高搜索引擎的检索效率。如何快速、 准确地去除重复网页，成为搜索引擎研究领域一个亟待解决的问题。针对网络中大量数据重复的现状，当前，提出的网页查重的方法比较多，但大体分为两大类：基于分类的方法、排除相同URL方法以及基于特征码的方法。本文就目前常用的网页去重算法进行介绍，并对其效率、准确率、召回率做了细致的分析。

2.1 SCAM算法

SCAM算法是由斯坦福大学提出的用于复制检测和剽窃检测的一种算法。SCAM的方法受到了信息检索技术的启示，是一种基于词频统计的方法。SCAM方法可以检测出2篇文档之间相似处所在的位置，所使用的方法就是计算出每篇文档的词频，将文档用词频向量的方法表示出来，再计算2个词频向量之间的距离，在一定的范围之内就判断为相似的文档，由于同时还保留了该词的位置信息，所以同时也可以查找出到底文章的哪个部分是相似的。具体讲就是，SCAM首先统计文档中各个单词出现的次数，然后按照信息检索中常用的倒排索引存储法(inverted

index storage)存储文档与词频信息。最后，SCAM参照向量空间模型VSM(vector space model)提出了相关频率模型RFM(relative frequency model)，用以度量文档相似性。向量空间模型一般采用点积或者余弦公式来度量相似性，而相关频率模型其实是对余弦公式进行了改动，试图提高文件复制检测精度。

2.2.基于特征串的网页去重算法

  本文关键词：搜索引擎去重算法的研究与实现，由笔耕文化传播整理发布。