第２４卷第８期 计算机技术与发展 ＣＯＭＰＵＴＥＲ ＴＥＣＨＮＯＬＯＧＹ ＡＮＤ ＤＥＶＥＬＯＰＭＥＮＴ ２０１４年８月 Ｖｏ１．２４ Ｎｏ．８ Ａｕｇ． ２０１４ 主题爬虫的设计与实现 林子皓 （南京邮电大学计算机学院，江苏南京２１０００３） 摘要：在信息化爆炸的时代，一般搜索引擎的搜索结果已经满足不了人们的需要，能获得更准确全面信息的垂直搜索引 擎越来越受到关注。其中，主题爬虫作为垂直搜索引擎的核心部分一直是搜索方向的研究热点。文中在分析主题爬虫的 结构及特征的基础上，通过引入自己的主题相关度评价方法以及ＨＩＴＳ网页排序算法，构建了一个主题爬虫。文中给出了 爬虫实现的具体步骤，以云计算为主题，进行了实验。实验结果较好地反映了主题爬虫的实用性。 关键词：主题爬虫；ＨＩＳ算法；Ｔ主题相关度 中图分类号：ＴＰ３１ 文献标识码：Ａ 文章编号：１６７３—６２９Ｘ（２０１４）０８—００９９—０４ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１６７３－６２９Ｘ．２０１４．０８．０２３ Ｄｅｓｉｇｎ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ Ｔｏｐｉｃ－ｆｏｃｕｓｅｄ Ｃｒａｗｌｅｒ ＬＩＮ Ｚｉ－ｈａｏ （Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ，Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｐｏｓｔｓ＆Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｎａｎｊｉｎｇ ２１０００３，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｔｈｅ ｅｒａ ｏｆ ｉｎｆｏｒｍａｔｉｏｎ ｅｘｐｌｏｓｉｏｎ，ｔｈｅ ｇｅｎｅｒａｌ ｃｒａｗｌｅｒ ｃａｎｎｏｔ ｍｅｅｔ ｔｈｅ ｒｅｑｕｉｒｅｍｅｎｔｓ ｏｆ ｐｅｒｓｏｎａｌｉｚｅｄ ｓｅａｒｃｈ ｉｎ ｓｐｅｃｉｉｃ ａｒｆｅａｓ， ｂｕｔ ｔｈｅ ｔｏｐｉｃ ｃｒａｗｌｅｒ ｗｈｉｃｈ ｃａｎ ｏｂｔａｉｎ ｍｏｒｅ ａｃｃｕｒａｔｅ ａｎｄ ｃｏｍｐｒｅｈｅｎｓｉｖｅ ｉｎｆｏｒｍ￣ｉｏｎ ｇｅｔｓ ｍｏｒｅ ａｔｔｅｎｔｉｏｎ．Ａｍｏｎｇ ｔｈｅｍ，ｔｈｅ ｔｏｐｉｃ ｃｒａｗｌｅｒ ａｓ ｔｈｅ ＣＯｒｅ ｐａｒｔ ｏｆ ｈｅ ｔｖｅｒｔｉｃａｌ ｓｅａｒｃｈ ｅｎｇｉｎｅ ｈａｓ ｂｅｅｎ ｔｈｅ ｒｅｓｅａｒｃｈ ｆｏｃｕｓ ｉｎ ｔｈｅ ｓｅａｒｃｈ ｄｉｅｃｔｒｉｏｎ．Ｏｎ ｈｅ ｂａｓｉｔｓ ｏｆ ａｎａｌｙｚｉｎｇ ｈｅ ｓｔｔｒｕｃｔｕｒｅ ａｎｄ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｔｈｅ ｔｏｐｉｃ ｃｒａｗｌｅｒ，ｄｅｓｉｇｎ ａ ｔｏｐｉｃ ｃｒａｗｌｅｒ ｂｙ ｉｎｔｒｏｄｕｃｉｎｇ ｉｔｓ ｏｗｎ ｍｅａｓｕｒｅｍｅｎｔ ｏｆ ｔｏｐｉｃ ｓｉｍｉｌａｒｉｔｙ ａｎｄ ｐａｇｅ ｒａｎｋｉｎｇ ａｌｇｏ－ ｒｉｔｈｍ ｏｆ ＨＩＴＳ．Ｏｆｆｅｒ ｓｐｅｃｉｉｃ ｓｔｆｅｐｓ ｏｆ ｉｍｐｌｅｍｅｎｔｉｎｇ ｔｈｅ ｃｒａｗｌｅｒ．Ａｎ ｅｘｐｅｒｉｍｅｎｔ ｗｉｈ ｔｈｅ ｔｈｅｍｅ ｏｆ ｔｃｌｏｕｄ ｃｏｍｐｕｔｉｎｇ ｈａｓ ｂｅｅｎ ｃａｒｒｉｅｄ ＯＵｔ， ｗｈｉｃｈ ｐｒｏｖｅｓ ｔｈｅ ｐｒａｃｔｉｃａｌ ａｐｐｌｉｃａｂｉｌｉｔｙ ｏｆ ｔｏｐｉｃ ｃｒａｗｌｅｒ． Ｋｅｙ ｗｏｒｄｓ：ｔｏｐｉｃ ｃｒａｗｌｅｒ；ＨＩＴＳ ａｌｇｏｒｉｈｍ；ｔｔｏｐｉｃ ｓｉｍｉｌａｒｉｔｙ Ｏ 引 言 随着信息爆炸式的发展，用户对于信息搜索的需 求越来越多。由于一般搜索引擎查询结果广而不精的 现状满足不了用户需求，查询更精确、分类更细致、数 据更全面的主题搜索引擎应运而生。主题爬虫是主题 搜索引擎的关键和基础，它是根据某一特定的主题，在 因特网上能自动抓取和主题相关网页的程序。 集中。 １主题爬虫模块设计 １．１整体结构 主题爬虫只爬取与主题相关的网页，并且根据分 析、筛选的结果继续爬取合理网页。对比普通爬 虫 Ｊ，需要在原来基础上进行扩充，特别是网页处理 部分。整体结构可以看作：初始模块进行初始爬行，主 题相关度分析模块进行相关度分析并行适当筛选页 面，排序模块对网页的重要性进行一个排序，形成一个 优先级序列。每次都从优先级高的网页开始抓取，可 以保持主题不偏移。 系统架构图如图１所示。 主题爬虫的主要目标是以特定的方式，高效地抓 取Ｗｅｂ中与主题相关的网页，尽可能过滤与主题无关 的链接，实现搜索的专、深、精。它与传统的通用爬虫 相比，减少了对资源的利用并且支持扩张性的检索处 理。对于主题爬虫而言，最重要的是如何过滤网页中 的前向链接，使得爬虫聚焦在一个特定主题的Ｗｅｂ子 收稿日期：２０１３－１０—２８ 修回日期：２０１４—０１—２６ 网络出版时间：２０１４—０５—２１ 基金项目：国家自然科学基金资助项目（６１１７０３２２） 作者简介：林子皓（１９８８一），男，硕士研究生，研究方向为智能计算技术；导非经典逻辑及应用。 师：洪龙，教授，研究员级高级工程师，研究方向为分布式系统、 网络出版地址：ｈｔｔｐ：／／ｗｗｗ．ｃｎｋｉ．ｎｅｔ／ｋｃｍｓ／ｄｅｔａｉＬ／６１．１４５０．ＴＰ．２０１４０５２４．２１５１．０６１．ｈｔｍｌ ・１００・ 计算机技术与发展 第２４卷 图１ 主题爬虫运行流程及结构示意图 主题爬虫系统运行步骤： （１）根据爬行模块提供的初始种子及主题，从 ｗｅｂ中爬取网页； （２）相关度分析模块对网页进行相关度分析； （３）由分析结果进行页面的取舍，舍去不符要求 的网页； （４）从后续等待的ＵＲＬ中继续取出处理，回到第 一步，直到等待为空； （５）最终排序部分根据自己算法对爬取网页进行 重要性排序。 １．２初始种子和关键词模块 由于主题爬虫是面向特定领域的，具有主体性，初 始种子要求是与主题相关领域内的，所以文中定位自 主选初始页面，这样能很好地保证主题爬虫从一开始 顺利进行下去。例如，所选择的主题是云计算，那么初 始种子选择的就是ＣＳＤＮ云计算首页。 在确定主题方面，通过对各个关键词赋予相对应 的权值，组成相应的关键词集，用这些词集来确定主 题。设置权值有人工设置和机器提取两种方法，人工 设置即根据以往经验来制定，机器提取就是用程序提 取主题网页集中各个网页共同的部分。在文中实现 中，为了简便，只统计了种子网页的关键词词频。手工 设置通常操作简便，并且设置值与实际情况误差不大， 不足之处是有缺漏并且准确性不高；机器提取所定权 值更接近标准值，但前提是有主题贴合且代表性和全 面性都具备的网页集，否则偏差将大大增加。实际可 以结合两种方法，综合它们优点 ：人工设置关键词赋 予权值，搜出相应网页，再用这些网页组成网页集合进 行机器提取，得到对应关键词集及权值。 １．３主题相关度模块 文中把网页的主题相关度作为筛选页面的一个重 要的衡量标准，这样做能有效地利用爬虫程序处理掉 不相关的网页，避免进行无用爬取，降低准确率。因此 必须计算网页主题相关度 Ｊ，并将相关度小于设定 阈值的网页过滤掉。普通爬虫在进行爬取时会对所有 ＵＲＬ进行处理，没有方向性，这样无疑增大了无效工 作量；而主题爬虫会紧扣主题，由主题相关度计算结果 来筛选符合网页，去除无用网页，提高准确率，这就是 两者的根本区别 。 文中将每个关键词看作是一个特征项，作为网页 的一个基本单位。通过统计算法Ｔｅｒｍ Ｆｒｅｑｕｅｎｃｙ—Ｉｎ— ｖｅｒｓｅ Ｄｏｃｕｍｅｎｔ Ｆｒｅｑｕｅｎｃｙ（ＴＦ—ＩＤＦ）计算每个特征项的 权值。设某一主题在相关页面中特征项的数目为ｎ， 若以 ，表示第．『个特征项在该页面中的权值，则这ｎ 个特征项权值可以由向量Ｄ表示： Ｄ＝（叫１，Ｗ２，…，Ｗ ） （１） 定义１：页面关键词权重频率 ＝ 第ｉ个关键词出现的次数 页面中关键词出现的最多次数。 分析待判断的页面统计出关键词出现的次数，分 别表示为ａ （ｉ＝１，２，…，ｎ），以出现次数最高的关键词 作为基准，记为ａ ，则权重频率 ＝ ，显然出现最高 次数的频率即为 ＝ ０ ＝１，这样就能通过页面关键 词权重频率反映出第ｉ个关键词在页面中的重要程 度。 其他关键词的权重频率 可以根据以上算式算 出，那么页面中每一维分向量为 Ｗ ，待判定网页的关 键词权重向量空间 表示为： Ｔ＝（ ｌＷｌ，Ｘ，２Ｗ２，…，ＸｎＷ ） （２） 文中用主题基准模型向量和待判定网页向量的夹 角余弦来衡量其主题相关度。计算公式如下： ｓｉｍ：ｃｏｓ＜ ，Ｄ＞： ： ｌ Ｚ’ｌ ｌ Ｄ ｌ Ｊ— ｗ ＋ 十…＋Ｗ：Ｊｘ１垒 ＋Ｘ２Ｗ ＋…＋磐ｉ Ｗ： （３） 当计算的余弦值大于等于系统指定的相关度阈值 时，才会认定当前处理页面为主题相关页面。假设阈 值为ｒ，若ｃｏｓ＜Ｔ，Ｄ＞≥ｒ，则认为此页面和主题相关， 保留并下载此页面；若ｃｏｓ＜Ｔ，Ｄ＞＜ｒ，则认为此页面和 主题无关，舍去此页面。ｒ所设值能决定获得页面的 多少，一般根据实际需要来。ｒ越小，筛选条件低，获 得的页面越多；ｒ越大，筛选条件越严格，获得的页面 越少。 １．４ 网页价值排序模块 网页价值排序模块是对已筛选留下的网页进行操 作，把这些网页按实际价值高低排序，顺序的先后体现 了网页的重要程度，也方便价值高的网页容易地被选 择到。除了主题相关度因素体现网页重要性以外，其 他因素也是所需要排序模块考虑的，诸如网页链接个 数、链接指向、被其他网页指向等等 。 在Ｗｅｂ页面中存在大量的超链接，超链接分析可 以指出更有价值的搜索方向，可以很好地提高检索质 量，ＨＩＴＳ算法是其中一个比较有代表性的算法。ＨＩＴＳ 第８期 林子皓：主题爬虫的设计与实现 ｔ＝１ ・１０１・ 算法是由康奈尔大学（Ｃｏｒｎｅｌｌ Ｕｎｉｖｅｒｓｉｔｙ）的ＪｏｎＫｌｅｉｎ— ｂｅｒｇ博士于１９９８年首先提出的 ，ＨＩＴＳ的英文全称 为Ｈｙｐｅｒｔｅｘｔ－ＩｎｄｕｃｅｄＴｏｐｉｃＳｅａｒｃｈ。 ｄｏ ｆｏｒ ｅａｃｈ ｉｎ Ｖ ＨＩＴＳ算法定义了两个重要概念：Ａｕｔｈｏｒｉｔｙ页面 （某一主题的权威页面）和Ｈｕｂ页面（与Ａｕｔｈｏｒｉｔｙ页面 连接在一起的页面）。 Ａｕｔｈｏｒｉｔｙ：代表了特殊领域内或与主题联系紧密 ｄ。ａｔ（ ）＝∑ｈ，－ｉ（ ） ｔ（口）＝ ａ一（ ） ａ ＝ａ，／ｌ ａ ｌＩ ｌｈ ＝ｈ，／ｌ ｈ ｌｌ ｌｔ＝ｔ＋１ 的高质量网页。它的权威度与自身提供内容信息有 关，即网页被引用的越多，其Ａｕｔｈｏｒｉｔｙ越大，网页越重 ｗｈｉｌｅ ｌ ｌａ 一ａ Ｉ ｌｌ＋１Ｉ ｈ 一ｈ 一ｌ ｌＩ＜ｓ 要。 Ｈｕｂ：代表了一种包含了很多指向高质量页面链 接的网页，即提供高质量的超链接。而链接权威度与 网页提供的超链接的质量相关，引用内容质量高的网 页越多，网页的链接权威度越高。它是一种指向权威 网页的链接集合¨ 。 重要性排序模块中的网页排序可以将主题相关度 和链接分析两个因素结合起来考虑，链接分析部分主 要运用上面篇幅所介绍的ＨＩＴＳ算法¨卜 ］。以下是 排序模块中ＨＩＴＳ算法流程： （１）通过主题爬虫获得与主题最相关的 个网页 的集合，称之为ｒｏｏｔ集。 （２）通过连接分析扩展ｒｏｏｔ集，扩展后得到的集 合称之为ｂａｓｅ集。扩展方法：对于ｒｏｏｔ集中任一网页 Ｐ，加入所有Ｐ中所包含的链接到ｒｏｏｔ集，加入最多ｄ 个指向Ｐ的连接到ｂａｓｅ集。 （３）计算ｂａｓｅ集中所有页面的权威值和中心值： 设ｎ维向量ａ， 。ａ ，ｈｉ分别表示节点ｉ的Ａｕｔｈｏｒｉｔｙ值 和Ｈｕｂ值。算法如下：初始化向量口，ｈ，ａ。＝１，ｈ。＝１， 然后进行Ｉ，０操作。 Ｉ操作：ａｔ（ ）＝∑【ｗ＂】 Ｅ ｈ，－１（鲫） ０操作： （ ）＝∑ａｔ＿ｌ（ ） （４）规范化。 ）： ＿）一 ＾／∑［ａｔ（ｑ）］ ｈ ）： 一 ＾／∑［ （ｇ）］ Ｉ操作反映了如果一个网页有很多好的Ｈｕｂ指 向，其权威值会相应增加。 Ｏ操作反映了如果一个网页指向很多好的权威 页，Ｈｕｂ值也会相应增加。 重复计算Ｉ，Ｏ操作和规范化，直至ａ（ ）和ｈ（ ） 收敛为止。 具体代码实现如下： ａ，ｈ初始化为１，ａ。＝１，ｈ。＝１ ｒｅｔｕｒｎ（ａ ，ｈｔ） ２主题爬虫具体实现 ２．１ ＵＲＬ相关 实现主题爬虫需要进行主题相关度计算，并根据 计算所得值进行页面筛选，文中定于使用４个ＵＲＬ队 列 “ ，各个队列都是同状态ＵＲＬ集合： （１）等待队列：该队列等待程序处理，并且爬虫新 爬取的网页将加入其中。 （２）异常队列：无法进行下载的链接将被加入其 中，不再进行下一步骤，并且舍弃掉。 （３）抛弃队列：下载可正常进行，但主题相关度小 于阈值的链接放进此队列，程序也将不再进行下一步 骤。 （４）完成队列：下载可正常进行，但主题相关度大 于阈值的链接放进此队列，完成下载后，将已下载过的 ＵＲＬ加入完成队列。 图２说明了ＵＲＬ队列的转化流程及ＵＲＬ所处各 个队列的关系。 图２ ＵＲＬ在队列中的流通过程 ２．２网页爬取 在爬取一个网页之前，首先要检查该网页。如果 该网页是一个网络资源，那么就没有必要访问，例如网 页是一个ｍｐ３的下载页。需要忽略的网页类型有： ｉｆ（ｓ．ｅｎｄｓＷｉｔｈ（”．ｚｉｐ”）ｌｌ ｓ．ｅｎｄｓＷｉｔｈ（”．ｇｚ”）