计算机技术与发展 第２２卷 基于遗传算法的主题爬虫 张海亮，袁道华 （四川大学计算机学院，四川成都６１００６５） 摘要：针对目前主题网络爬虫搜索策略难以在全局范围内找到最优解，通过对遗传算法的分析与研究，文中设计了一个 基于遗传算法的主题爬虫方案。引入了结合文本内容的ＰａｇｅＲａｎｋ算法；采用向量空间模型算法计算网页主题相关度；采 取网页链接结构与主题相关度来评判网页的重要性；依据网页重要性选择爬行中的遗传因子；设置适应度函数筛选与主 题相关的网页。与普通的主题爬虫比较，该策略能够获取大量主题相关度高的网页信息，能够提高获取的网页的重要性， 能够满足用户对所需主题网页的检索需求，并在一定程度上解决了上述问题。 关键词：遗传算法；爬虫；主题爬虫；主题相关度；网页重要性 中图分类号：ＴＰ３０１．６ 文献标识码：Ａ 文章编号：１６７３－６２９Ｘ（２０１２）０８一Ｏ０４８—０５ Ｆｏｃｕｓｅｄ Ｃｒａｗｌｉｎｇ Ｂａｓｅｄ ｏｎ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍｓ ＺＨＡＮＧ Ｈａｉ—ｌｉａｎｇ，ＹＵＡＮ Ｄａｏ－ｈｕａ （Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｓｉｃｈｕａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｅｎｇｄｕ ６１００６５，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｏｐｔｉｍｉｚｅｄ ｓｏｌｕｔｉｏｎ ｃａｎ＇ｔ ｂｅ ｆｏｕｎｄ ｉｎ ｔｈｅ ｇｌｏｂａｌ ｓｃｏｐｅ ｂａｓｅｄ ｏｎ ｔｈｅ ｐｒｅｓｅｎｔ ｓｅａｒｃｈｉｎｇ ｓｔｒａｔｅｇｙ ｏｆ ｆｏｃｕｓｅｄ ｃｒａｗｌｅｒ．Ａ ｆｃｕｓｏｅｄ ｃｒａｗｌｅｒ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｈｍ ｉｔｓ ｐｒｏｐｏｓｅｄ ｔｈｒｏｕｇｈ ｔｈｅ ａｎａｌｙｓｉｓ ａｎｄ ｓｔｕｄｙ ｏｆ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ．Ｔｈｉｓ ｍｅｔｈｏｄ ｉｎｔｒｏｄｕｃｅｓ ｔｅ ｂＰａｇｅＲａｎｋ ａｌｇｏｒｉｈｍ ｃｏｍｂｉｔｎｅｄ、ｖｉｔＩｌ ｔｅｘｔ ｃｏｎｔｅｎｔｓ，ｃｏｍｐｕｔｅｓ ｔｈｅ ｐａｇｅ ｔｏｐｉｃ ｓｉｍｉｌａｒｉｔｙ ｗｉｔｈ ｖｅｃｔｏｒ ｓｐａｃｅ ｍｏｄｅｌ ａｌｇｏｒｉｈｍ，ａｔｎｄ ｊｕｄｇｅｓ ｔｈｅ ｉｍｐｏｒｔａｎｃｅ ｏｆｗｅｂ ｐａｇｅ ａｃｃｏｒｄｉｎｇｔｏｗｅｂｌｉｎｋ ｓｔｒｕｃｔｕｒｅ ａｎｄｔｏｐｉｃ ｓｉｉｌｍａｒｉｔｙ。Ａｔｔｈｅ ｓａｌＹｌｅｔｉｍｅ－ｔｈｅ ｇｅｎｅｔｉｃｆａｃｔｏｒｓ ａｒｅ ｓｅｌｃｔｅｅｄ ｏｎ ｂａｓｉｓ ｏｆｔｈｅ ｉｍｐｏｒｔａｎｃｅ ｏｆｗｅｂ ｐａｇｅ．Ｔｈｅ ｓｙｓｔｅｍ ｓｅｔｓ ｆｉｔｎｅｓｓ ｆｕｎｃｔｉｏｎ ｔｏ ｓｅｌｅｃｔ ｐａｇｅｓ ｒｅｌｅｖａｎｔ ｗｉｔｈ ｔｏｐｉｃ．Ｃｏｍｐａｒｅｄ ｔｏ ｆｏｃｕｓｅｄ ｃｒａｗｌｅｒ．ｔｈｅ ｔｏｐｉｃ ｃｒａｗｌｅｒ ｂａｓｅｄ ｏｎ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｈｍｓｔ ｃｏｕｌｄ ｏｂｔａｉｎ ｔｈｅ ｗｅｂ ｐａｇｅｓ ｗｈｉｃｈ ｈａｖｅ ｓｔｒｏｎｇ ｃｏｒｒｅｌａｔｉｏｎ ｗｉｔｈ ｓｕｂｊｅｃｔｓ－ａｎｄ ｉｍｐｒｏｖｅ ｈｅ ｉｔｍｐｏｒ－ ｔａｎｃｅ ｏｆ ａｃｃｅｓｓ ｗｅｂ ｐａｇｅｓ。ａｎｄ ｓａｔｉｓｆｙ ｕｓｅｒ’Ｓ ｄｅｍａｎｄ ｆｏｒ ｓｅａｒｃｈｉｎｇ ｔｏｐｉｃ ｗｅｂｓ ｔｈｅｙ’ｒｅ ｉｎｔｅｒｅｓｔｅｄ ｉｎ．Ｓｏ ｉｎ ａ ｃｅ￣．ａｉｎ ｅｘｔｅｎｔ，ｔｈｅ ａｂｏｖｅ ｐｒｏｂｌｅｍｓ ａｒｅ ｓｏｌｖｅｄ． Ｋｅｙ ｗｏｒｄｓ：ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ；ｃｒａｗｌｅｒ；ｆｃｕｓｏｄ ｅｃｒａｗｌｅｒ；ｔｏｐｉｃ ｓｉｍｉｌａｒｉｔｙ；ｗｅｂ ｉｍｐｏｒｔａｎｃｅ ０ 引 言 随着互联息的剧增，用户越来越依赖搜索引 擎，而传统的通用搜索引擎查询的数据是海量无序的 １主题爬虫 自动地发现并下载网页称为爬取，下载网页的程 序称为网络爬虫…（Ｃｒａｗｌｅｒ或Ｓｐｉｄｅｒ程序），是搜索 引擎的重要组成部分。 主题网络爬虫 ．３ 的工作流程主要有三个步骤： 第一，从请求队列中取出ＵＲＬ地址，分析ＵＲＬ与 主题的相关性，如果该ＵＲＬ与主题相关且以前没有遇 且查询的深度不够，而用户最大的体验就是查询不到 自己想要的信息。为了克服通用搜索引擎不能快速、 准确地查找有用的信息，并满足用户的需求体验，于是 主题搜索引擎应运而生。 主题搜素引擎是信息技术在大规模文本集合上检 索与主题相关信息的实际应用。主题爬虫对于主题搜 索引擎发现和抓取文档具有首要的责任，主题爬虫设 计的优秀与否决定着主题搜索引擎的好坏。主题网络 爬虫采用分类技术来访问的网页是关于同一个主 题的。 到过，则将其放人待抓取的ＵＲＬ队列中。 第二，按照某种排序算法对上述ＵＲＬ队列进行排 序，使重要的页面置于队列前端，并重复上述过程，直 到满足系统设计的停止条件。 第三，存储与主题相关网页，进行一定的分析、过 滤，并建立索引，并对后续的抓取过程进行反馈和指 导。 收稿日期：２０１１－１２—２４；修回日期：２０１２—０３－２７ 爬虫开始的时候，需要给爬虫输送一个ＵＲＬ列 表，在实际应用中该列表是一个特定话题的多个权威 作者简介：张海亮（１９８７一），男，四川成都人，硕士，研究方向为分布 式并行处理与网络计算；袁道华，教授，硕士生导师，研究方向为分 布式并行处理与网络计算。 页面的集合，于是这个列表中的ＵＲＬ地址便是爬虫的 起始位置，爬虫从这些ＵＲＬ出发，不断地发现新的 第８期 张海亮等：基于遗传算法的主题爬虫 ・４９・ ＵＲＬ，然后再根据预先设计搜索策略爬行这些新的 ＵＲＬ，最后得到与主题相关的网页。一般的爬虫都自 己建立ＤＮＳ缓冲，目的是加快ＵＲＬ解析成ＩＰ地址的 速度 引。爬虫的运行过程如图１所示。 ５）扩展性强：能够与其他技术混合使用在主题爬 虫的设计中，如组合优化、机器学习和自适应控制。 ３基于遗传算法的搜索策略 ３．１设计思想 由于因特网上的信息是按照主题相关来分类，相 关或重要的网页相互链接，所以基于网页链接结构评 价的搜索策略 以此为基础来分析，但易出现“主题 漂移”问题；基于内容评价的搜索策略 采用向量模 图１ 主题爬虫运行过程 ２遗传算法的基本思想 遗传算法 ＧＡ（Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍｓ）是一种模拟 自然界生物进化过程的计算模型，用于解决最优化的 搜索算法。ＧＡ克服了传统算法的一些缺点，对一些 复杂的、难于数学建模的问题有着明显的优势。它体 现了适者生存、优胜劣汰的进化原则，通过复制、交叉、 变异等操作不断产生新的个体，并逐步淘汰适应度函 数值低的个体，使群体不断进化，同时以全局并行搜索 技术来搜索优化群体中最优个体，以求得到满足要求 的解。 主要步骤如下： ①处理用户提交的ＵＲＬ集，抽取关键词； ②选中输入集的所有链接，并获相应的ｗｗｗ表 示，结果集作为第一代； ③对第一代所有元素计算其适应度； ④不断复制、交叉、变异操作，并从上代进入到下 一代 引。 其中，选择、交叉和变异三个主要遗传算子构成了 遗传算法的遗传操作。 在主题爬虫中应用遗传算法可以在如下方面提高 搜索的性能 ： １）内在启发式随机搜索：指导主题爬虫的搜索方 向； ２）内在隐并行性：不容易陷入局部最优； ３）更好的全局寻优能力：提高主题爬虫的全局搜 索能力； ４）渐进式优化：利用选择、交叉和变异等操作，通 过不断遗传，选择最优集； 型算法，却忽略了网页之间的链接关系。因此通过对 以上两种策略的分析，再结合遗传算法的特性，决定采 用如下策略：基于从优质个体链接出去的ＵＲＬ可能是 优质个体和链接目标是优质个体的ＵＲＬ也可能是优 质个体的原则，选出与主题相关度高的个体（ＵＲＬ）作 为初始的种子集；交叉操作对父代个体进行基因变换， 产生新的个体，再从中选择优异个体；通过变异操作， 扩大搜索范围（ＵＲＬ集）。 ３．２ 系统结构 通过对普通主题的研究分析，基于遗传算法的主 题爬虫搜索策略在以下几方面对传统的设计进行了扩 展：在海量网页的处理过程中加入选择操作，通过对结 合文本内容的ＰａｇｅＲａｎｋ算法计算得到的网页重要性 值排序来选择与主题相关的网页，在一定程度上解决 了信息检索中出现的主题漂移问题；在每代种子挑选 过程中增加变异和交叉操作，增加相关度较低的页面 被爬行的机会并扩大相关网页的爬行范围，形成一个 能反映主题特征的种子集合，其实现流程如图２所示。 ３．３主题的选择 用户在使用搜索引擎时是通过相关主题来检索他 们想要的信息，从这个角度主题可以描述成某一事物 或某一信息的若干特征的集合。实际中，主题概念的 范围可大可小，主题范围可以非常抽象，但此时它的含 义非常模糊；它的范围也可以非常具体，而此时它的意 义却非常明确。主题选择是面向主题的Ｗｅｂ信息提 取的基础 。主题的确立可以采用手工设置关键词集 的方法，该方法易于实现，依赖于专家的经验ｕ。。。 ３．４初始种子集合的确立 初始种子集合的确立有三种常用的方法，第一是 人工指定；第二是自动生成；第三是前两种方式的混合 模式。由于爬虫是从初始种子集合中的ＵＲＬ开始，并 解析这些链接，根据网页的重要性来选择进入ＵＲＬ的 顺序，所以初始种子集合的选择将直接影响主题页面 的采集以及采集工作的效率。另外，由于主题爬虫只 搜索跟主题相关的ＵＲＬ，搜索的范围局限于万维网中 很小的一部分，所以更加要求初始种子集合是主题相 关的。鉴于上述理由，文中采用混合模式，利用元搜索 ・５Ｏ・ 计算机技术与发展 第２２卷 引擎获取，在领域专家的指导下并结合人的经验共同 ＣＯ８＜ ．１３＞ 一一进行筛选，选出与主题相关的ＵＲＬ作为初始种子集 合 。 初始化种子集合ｓ，相关度阈值ｒｏ。重要 性阈值Ｐ０，交叉概率Ｐｃ，变异概率Ｐｍ ！ Ｉ口Ｉ Ｉ ２ Ｉ （（口ｌ，口２，…，口 ），（ ｌ Ｊ， ２ ２，…， ）） ｌ（ｎｌ，０２，…，ｎ ）Ｉ Ｉ（ ｌ １，Ｘ２ｌ ２，…， 加 ）Ｉ ｌ ＋Ｘ２Ｗ ＋…＋ＸｎＷ： 获取种群Ｓ中未访问的ＵＲＬ，并放 入待处理列表ｓｌ中 （１） Ｉ飘ｏ Ｊ’Ｉ’１日 ！Ｌｗ ’ ｒＩ，千ｒＴ】ｊ 的相关度，与ｒｏ比较，删除相关 阈值ｒ０是一个常量，当ＣＯＳ＜ ， ＞≥ｒｏ时，该页 分析Ｓ１中的网页的链接信息，计 算网页的重要性，与Ｐ０比较，删 除重要性小于Ｐ０的网页链接 接作为ｓ２ 根据交叉概率执行交叉操作得到 否 Ｓ３ 根据交叉概率执行交叉操作得到 Ｓ４ 刷居适应度函数判断新产生Ｓ中每 个ＵＲＬ的适应性，选取适应性大 于适应度阈值的ｕＲＬ组成新的种 否为！ 退出 图２基于遗传算法的主题爬虫流程 ３．５主题相关度 计算主题相关度 采用向量空间模型算法。向 量模型不判断文档与查询是否相关，而是根据文档与 查询的相似度对文档进行排序。 选取文档中的词为向量空间的一个向量，由这些 词作为向量的维数表示文档。文档和关键词都被假设 是一个ｒｔ维向量空间的一部分，其中ｎ是关键词的个 数，每一维分量的大小为每个关键词的权值 ，主题用 向量则表示为： ＝（ａｌ，Ｃｔ２，…，口 ），ａ ＝ｔｌＪ ， ＝１，２，…， ｎｏ 采用绝对词频对页面进行统计分析，在实际计算 中，让频率出现最高的关键词作为基准，设其频率 ＝ １，通过频率之比，计算出其他关键词的相对频率 ｉ， 则该页面对应向量的每一维分量为 ｉ。 页面主题用向量则表示为： 卢＝（ Ｉ埘ｌ，Ｘ２ ２，…，ＸｎＷ ），ｉ＝１，２，…，ｎ 用两个向量夹角的余弦表示页面的主题相关度： 面和主题相关。 ３．６网页重要性 能否把与用户检索需求相关的高质量文档放在排 序结果最靠前的位置，是衡量搜索引擎性能的关键技 术之一，因此网页的排序显得尤为重要。考虑到网页 与主题的相关性以及网页之间的链接性，可以综合考 虑主题相关度和链接分析两个关键因素。 其中链接分析采用结合文本内容的ＰａｇｅＲａｎｋ算 法。ＰａｇｅＲａｎｋ “ 的基本思想是试图为所有网页赋予 一个量化的价值度，每个网页被量化的价值通过一种 递归的方式来定义，由所有链接到该网页的价值程度 决定。具体地，基于网页之间的链接信息，设Ｆ 是页 面ｉ的链出页面集， 是页面＿『的链人页面集。则在任 意时间点，爬虫位于页面＿『的概率Ｐ（．『）见式（２）： Ｐ（．『）＝（１一卢）＋卢 （２） 其中，０＜ ＜１，通常取值为０．８５。该算法认为 一个网页被多次引用，则它可能是很重要的；一个网页 虽然没有被多次引用，但是被重要的网页引用，则它也 可能是很重要的，这就是权威（Ａｕｔｈｏｒｉｔａｔｉｖｅ）网页，对 每个网页计算它的权威值，就可以对网页进行排序，从 而找到最重要的权威网页¨引。 为了能够将页面的权威性与主题相关性结合起 来，在网页间传递ＰＲ时考虑页面的主题相关性，相关 度大的链出页面的ＰＲ就相对大一些 。改进后的 ＰａｇｅＲａｎｋ见式（３）： Ｐ （＿『）＝（１一卢）Ｐ （＿『）＋ ∑Ｐ （ｆ）Ｐ （ －－＋ｊ）（３） 其中，ｔ为待搜索的主题，Ｐ（ｉ）可由（２）式计算出 来，Ｐ （ｉ一＿『）是当爬虫位于网页ｉ时选择链出页面 的 概率。 （Ｊ．）表示爬虫不选择出链而是直接跳转到页 面＿『的概率，它们都和主题相关度有关。设 为所有 网页的集合，Ｒ （ｋ）为页面ｋ关于主题ｔ的相关性： Ｐ （ｆ 盟： （４） ” ＥＲ （Ｊ｝）∑ｃｏｓ（ ， ） 一 ㈩ 第８期 张海亮等：基于遗传算法的主题爬虫 ・５１． 其中，ＣＯＳ＜口， ＞由式（１）可得。由式（４）与式 （５）可得，结合了主题的ＰａｇｅＲａｎｋ按照链出页面的主 题相关度来传递ＰａｇｅＲａｎｋ值。这样，同一页面的链出 页面集里和主题相关性大的就能获得此页面的父页面 较多的ＰａｇｅＲａｎｋ值。 ３．７适应度评价函数 个体适应度计算公式为：Ｆｉｔ（１ｉｎｋ ）＝ ＋ｒ』Ｉ后。 其中Ｆｉｔ（１ｉｎｋ ）代表第ｉ个ＵＲＬ的主题相关度。 代表 ｌｉｎｋ 对应父网页的主题相关度。ｒ 反映了链接提示信 息的主题相关度。ｋ是因子，取１００。 ３．８遗传操作 ３．８．１选择操作 在每一代种群中，对个体的适应度值进行排序，选 择适应度值高的个体遗传到下一代群体中，淘汰适应 度值低的个体。具体实现方法为： ①淘汰已搜索过的ＵＲＬ； ②删除重复的ＵＲＬ，并合并链接提示信息； ③计算链接对应ＵＲＬ的适应度值； ④根据适应度值，对个体的适应度值进行排序，选 取适应度值大于适应度阈值的个体，构成新集合Ｓ，然 后进行下一轮的遗传操作 。 ３．８．２交叉操作 交叉操作把两个适应度值高的个体上的基因重 组，产生两个新的个体，新的个体将进入新一轮的遗传 操作。 第一，分析集合５ｌ中所有ＵＲＬ对应的网页，解析 每个网页所包含的链接及链接提示信息，并计算每个 网页的重要性； 第二，依照网页的重要性进行降序排序； 第三，若设交叉概率为Ｐ ，则选出前ｍ×Ｐｃ个ＵＲＬ 进行交叉操作，交叉结果集为．ｓ３。 ３．８．３变异操作 变异操作通过个体基因突变的方式，产生新的个 体，从而增加相关度较低的页面被爬行的机会，扩大相 关网页的爬行范围，能够防止局部最优化。假设种子 集合有ｍ个ＵＲＬ 由选择操作可知当前网页的重要 性。按照重要性进行降序排序。设变异概率为Ｐ ，选出 前ｍ×Ｐ 个ＵＲＬ进行变异，得到集合记为｜ｓ４。令Ｓ＝ ．ｓ２＋ｓ３＋ｓ４，则将．ｓ集合中对应的ＵＲＬ作为下一代种 子。其中，交叉概率Ｐ 与变异概率Ｐ 之和为１。 ４实验设计与数据分析 软硬件环境：Ｗｉｎｄｏｗｓ ＸＰ系统，ＣＰＵ：Ｐｅｎｔｉｕｍ Ｅ６５００，内存２Ｇ，硬盘容量为５００ＧＢ，系统用Ｍｙｅｃｌｉｐｓｅ 开发，语言为Ｊａｖａ。 实验参数：线程数＝１０，起始种子＝５，ｒｏ＝０．０００２， 变异概率Ｐ ＝０．１，交叉概率Ｐｃ＝０．９，ｔ＇ｏ＝２，适应度 阈值取ｒｏ＝０．０００２。 以“奥运”和“世博”为主题，从百度及Ｇｏｏｇｌｅ上分 别搜索获取的５个跟主题相关的ＵＲＬ作为初始ＵＲＬ 集合。图３是以“奥运”为主题的基于两种算法的爬 虫爬行网页的相关性的对比图，图４是以“世博”为主 题的基于两种算法的爬虫爬行网页的相关性的对比 图，均设定搜索深度为２（设为较小值，防止搜索规模 过大）。 图３与图４表明，基于遗传算法的主题爬虫策略 与普通的爬出策略相比，爬取网页的主题相关性高；随 着爬行网页的增多，基于遗传算法的主题爬虫策略，爬 取网页的主题相关性趋于稳定，而普通的主题爬虫策 略，爬取网页的主题相关性呈下降趋势。原因在于：在 计算网页的重要性时，基于遗传算法的主题爬虫策略 综合考虑了主题相关度和链接分析两个关键因素。 图３主题为“奥运”的爬行到网页相关性对比图 鬣 晕 檗 靼 霪 图４主题为“世博”的爬行到网页相关性对比图 表１是基于两种搜索策略在不同爬行深度的情况 下对所抓取的网页的相关性进行的比较，从表１可以 看出，在爬行深度不同而其他条件相同的情况下，随着 ・５２・ 计算机技术与发展 第２２卷 深度的增加，与主题相关的网页数占总网页数的比例 参考文献： 有所下降，其原因在于：搜索的路径越深，一方面抓取 ［１］Ｓｈｏｋｏｕｈｉ Ｍ，Ｃｈｕｂａｋ Ｐ，Ｒａｅｅｓｙ Ｚ．Ｅｎｈａｎｃｉｎｇ Ｆｏｃｕｓｅｄ Ｃｒａｗ— 到的网页的适应度越低，另一方面适应度低的网页的 ｌｉｎｇ ｗｉｔｈ Ｇｅｎｅｉｔｃ Ａｌｇｏｒｉｈｔｍｓ［ｃ］／／Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ 数量却越多。从表１还可以得出另一个结论，即基于 ｏｎ Ｉｆｎｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ：Ｃｏｄｉｎｇ ａｎｄ Ｃｏｍｐｕｔｉｎｇ（ＩＴＣＣＯ５） 一遗传算法的主题爬虫爬行到与主题相关的网页占总网 Ｖｏｌｕｍｅ ＩＩ．［Ｓ．１．］．［ｓ．ｎ．］，２００５：５０３－５０８． ［２］刘金红，陆余良．主题网络爬虫研究综述［Ｊ］．计算机应用 页数比例下降的幅度比普通主题爬虫爬行到与主题相 研究，２００７，２４（ｉ０）：２６－２９． 关的网页占总网页数比例下降的幅度小。原因在于： ［３］刘汉兴，刘财兴．主题爬虫的搜索策略研究［Ｊ］．计算机工 通过设置变异算子，增加相关度较低的页面被爬行的 程与设计，２００８，２９（１２）：３１６０－３１６２． 机会，并扩大爬行与主题相关的网页的范围；在计算网 ［４］袁津生，李群，蔡岳．搜索引擎原理与实践［Ｍ］．北京： 页重要性时引进结合文本内容的ＰａｇｅＲａｎｋ算法，考虑 北京邮电大学出版社，２００８． 了网页与网页之间的链接关系。 ［５］ 赵大明，鱼滨．基于遗传算法的专业搜素引擎［Ｊ］．计算 袁Ｉ不同爬行深度下两种爬虫 机工程，２００９，３５（２１）：１９２—１９４． 抓取网页的相关性的比较 ［６］丁永生．计算智能一理论、技术与应用［Ｍ］．北京：科学出版 社，２００４． 爬行的 基于不同算 爬行到与主题相关的 ［７］刘国靖，康丽，罗长寿．基于遗传算法的主题爬虫策略 深度 法的爬虫 网页占总网页数比例 ［Ｊ］．计算机应用，２００７，２７（１２）：１７２－１７４． 普通主题爬虫 ４０．１６％ ［８］刘林，汪涛，樊孝忠．主题爬虫的解决方案［Ｊ］．华南理 Ｄｅｐｔｈ：２ 工大学学报（自然科学版），２００４，３２（Ｓ１）：１３７—１４０． 基于ＧＡ主题爬虫 ６７．６３％ ［９］王峰松．新一代智能搜索引擎一网典［Ｊ］．网络世界，１９９９， １３（２）：１２－２１． 普通主题爬虫 ３６．８８％ ［１０］方加沛，黄战．基于单类别文档分类的主题爬虫［Ｊ］．计 Ｄｅｐｔｈ：３ 算机工程与应用，２０１０，４６（１６）：６３—６６． 基于－ＧＡ主题爬虫 ６５．３２％ ［１１］关慧芬，师军，马继红．基于遗传算法的主题爬行技术研 究［Ｊ］．计算机与数字工程，２００８，３６（ｉｏ）：５０—５３． 实验中还发现，网络的状况会影响到爬虫的爬行 ［１２］袁浩，黄烟波．网页标题分析对主题爬虫的改进［Ｊ］．计 速度与结果。网络状况较好的情况，不但爬行速度快， 算机技术与发展，２００９，１９（６）：２２—２４． 而且爬行的网页的相关度高于同等情况下网络状况较 ［１３］Ａｒａｓｕ Ａ，Ｎｏｖａｋ Ｊ，Ｔｏｍｋｉｎｓ Ａ，ｅｔ ａ１．ＰａｇｅＲａｎｋ Ｃｏｍｐｕｔａｔｉｏｎ 差时爬取的网页的相关度。 ａｎｄ ｔｈｅ Ｓｔｒｕｃｔｕｒｅ ｏｆ ｔｈｅ Ｗｅｂ：Ｅｘｐｅｒｉｍｅｎｔｓ ａｎｄ Ａｌｇｏｒｉｔｈｍｓ ［Ｒ］．［ｓ．１．］：ＩＢＭ Ａｌｍａｄｅｎ Ｒｅｓｅａｒｃｈ Ｃｅｎｔｅｒ，２００１． ５结束语 ． ［１４］冯振明．Ｇｏｏｇｌｅ核 Ｌ，－ＰａｇｅＲａｎｋ算法探讨［Ｊ］．计算机技术 与发展，２００６，１６（７）：８２—８４． 分析结果表明：基于遗传算法的爬行策略能够有 ［１５］Ｒｉｃｈａｒｄｓｏｎ Ｍ，Ｄｏｍｉｎｇｏｓ Ｐ．Ｔｈｅ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｕｒｆｅｒ：Ｐｒｏｂａｂｉｌｉｓ． 效地加快抓取网页的速度、扩大搜索范围以及提高搜 ｉｔｃ Ｃｏｍｂｉｎａｔｉｏｎ ｏｆ Ｌｉｎｋ ａｎｄ Ｃｏｎｔｅｎｔ Ｉｆｎｏｒｍａｔｉｏｎ ｉｎ ＰａｇｅＲａｎｋ 索精度。但是对于如何便捷、有效地定义有实际意义 ［Ｃ］／／Ａｄｖａｎｃｅｓ ｉｎ Ｎｅｕｒａｌ Ｉｆｎｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍ．［ｓ． 的主题，如何在搜集网页信息时准确、快速地判定页面 １．］：［ｓ．ｎ．］，２００２：６７３—６８０． 与主题是否相关以及如何提高系统搜索的完全度等， ［１６］曹道友，程家兴．基于改进的选择算子和交叉算子的遗传 将是下一步要做的工作。 算法［Ｊ］．计算机技术与发展，２０１０，２ｏ（２）：４４—４７． （上接第４７页） Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｙｓｔｅｍｓ，２００５，１６（１１）：１０７８－１０９１． ［１０］张震，王晓明．对等网中Ｃｈｏｒｄ资源查找算法研究［Ｊ］． ［６］ 王新生，梁平，张云超，等．结构化Ｐ２Ｐ路由协议的改进 计算机工程与应用，２００６，４２（１１）：１４７—１５２． ［Ｊ］．计算机工程，２０１０，３６（１０）：１０５—１０７． ［１１］刘晓峰，吴亚娟，钟乐海．ｃｈｏｒｄ路由表结构的改进与优化 ［７］ 林雅榕，候整风．对哈希算法ＳＨＡ一１的分析和改进［Ｊ］．计 ［Ｊ］．计算机工程，２００７，３３（２１）：１０２—１０４． 算机技术与发展，２００６，１６（３）：１４２—１２６． ［１２］Ｋａｒｇｅｒ Ｄ，Ｌｅｈｍａｎ Ｅ，Ｌｅｉｇｈｔｏｎ Ｔ，ｅｔ ａ１．Ｃｏｎｓｉｓｔｅｎｔ Ｈａｓｈｉｎｇ ａｎｄ ［８］ 徐乾．对等网中ｃｈｏｒｄ协议及算法的研究改进［Ｄ］．哈尔 Ｒａｎｄｏｍ Ｔｒｅｅｓ：Ｄｉｓｔｉｒｂｕｔｅｄ Ｃａｃｈｉｎｇ Ｐｒｏｔｏｃｏｌｓ ｆｏｒ Ｒｅｌｉｅｖｉｎｇ Ｈｏｔ 滨：哈尔滨工业大学，２００７． Ｓｐｏｔｓ ｏｎ ｔｈｅ Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２９ｔｈ ［９］ 张浩，金海，聂江武，等．Ｄｕａｌ—ｃｈｏｒｄ：一种更加有效的 Ａｎｎｕａｌ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｔｈｅｏｒｙ ｏｆ Ｃｏｍｐｕｔｉｎｇ［Ｃ］．［Ｓ． 分布式哈希表［Ｊ］．微型计算机系统，２００６，２７（８）：１４５０— １．］：［Ｓ．ｎ．］，１９９７． １４５４．
