基于MD5去重树的网络爬虫的设计与优化

来源：论文查重 时间：2019-08-11 15:22:55

摘 要 随着信息化社会的不断发展，互联网上的数据越来越多，随之也产生了各种各样的搜索引擎，网络爬虫正是为搜索引擎论文查重 提供数据基础的。 由于大多数普通的网络爬虫在数据量巨大时都会因为 ＤＮＳ 解析以及 ｕｒｌ 去重而消耗大量的时间，为了更好地改 进爬虫的效率，让爬虫在大数据处理时依然拥有良好的性能，使用哈希链表缓存 ＤＮＳ 并将 ＤＮＳ 解析的效率相对于普通不做 ＤＮＳ 优 化的爬虫提高了 ２． ５ ～ ３ 倍。 再将 ＭＤ５ 加密算法以及树相结合设计出一种基于 ＭＤ５ 的 ｕｒｌ 去重树，理论上使得 ｕｒｌ 去重的空间复杂 度相对于普通哈希表缩小 ６０ 倍，而让其查重的时间复杂度接近于 Ｏ （１）。 最终通过实验证明了该设计的数据结构较为良好。
如今信息化时代，互联网发展的速度越来越快。 互联网上 的网页数量数以万亿计［ １］ ，如何有效且快速地检索这些网站上 的信息，成为了一大难题，因此搜索引擎随之诞生了。 而网络爬 虫，也称蜘蛛程序，网络机器人是搜索引擎的心脏，它常年爬行 在各大网站上采集数据，为搜索引擎提供了数据基础。 现在的 各种网络爬虫的搜索策略［２］ 主要为：深度优先搜索策略、广度 优先搜索策略、非完全 ＰａｇｅＲａｎｋ 策略以及大站优先搜索策略。 另外，由于现在互联网上的数据量是如此之庞大，因此，如 何设计出一个高效且准确的爬虫是所有开发者的研究之重。 虽 然网络爬虫经过多年的发展已经相对成熟，但随着互联网的发 展，网络爬虫所面对的挑战不断的增加。 通常，好的网络爬虫都需要满足以下特性［３］ ：
（ １） 高性能 即要求爬虫抓取网页的速度达到一定程度。 （２） 灵活性 要求爬虫面对不同的环境具有较好的自适应 能力。 （３） 可扩展性 能够多服务器同时抓取，即进行分布式的 抓取。 （４） 健壮性 较好的容错能力。 （５） 友好性 严格遵循 ｒｏｂｏｔ 协议。 由于现在爬虫的主要瓶颈体现在高性能上，因此本文主要 对如何提高爬虫的性能而进行优化。 在文献［８］ 中着重优化了 爬虫的结构，在 ＤＮＳ 解析阶段进行优化，以及在页面采集阶段 充分利用网络资源优化多线程从而优化爬虫。 但其并没有对已经访问过的 ｕｒｌ 读取进行优化。 而在文献［６］中利用 Ｒａｂｉｎ 指纹 方法优化 ｕｒｌ 查重速度，但其将会有一定的误判，以及空间利用 率提高方面还有提高的空间。 本文主要着重 ＤＮＳ 解析以及 ｕｒｌ 去重两方面作进一步的优化来提高爬虫性能。
虽然现在的爬虫种类越来越多，但其核心原理都是一样的。 如图 １ 所示为通用爬虫框架［２］。 首先确定一系列的种子 ｕｒｌ，将 其放入待下载的 ｕｒｌ 队列中。 爬虫依次读取队列中的 ｕｒｌ 并通 过 ＤＮＳ 服务器进行解析。 然后爬虫会开始将相应的网页进行 下载，并把当前网页的 ｕｒｌ 存入已下载 ｕｒｌ 集合中。 下载后的网 页可以存在本地，也可以按照一定的要求存入本地等。 下载网 页期间，爬虫还将利用解析器获取当前网页中所包含的链接并 将其提取出来加入待下载的 ｕｒｌ 队列。 在加入之前还应该判断 该网页是否已经下载过从而避免重复下载。 如此一直循环下 去，直到待下载网页中的队列全部为空为止。
不管是何种爬虫，通常都会包含以下模块： （１） 用于保存带抓取 ｕｒｌ 的数据结构，本文定义为 ｌｉｎｋｕｒｌ； （２） 保存已抓取的 ｕｒｌ 的数据结构，防止重复抓取，本文定 义为 ｖｉｓｉｔｅｄｕｒｌ； （３） 页面请求模块； （４） 页面分析模块，用于提取页面中的信息以及链接等； （５） 页面保存模块。
首先，要想爬虫工作，必须人为地初始化一些种子 ｕｒｌ。 因 为广度优先搜索策略无论是从实现难易，还是从效果上来说都 是一种不错的选择。 所以本文将这些 ｕｒｌ 存放入 ｌｉｎｋｕｒｌ 队列 中，然后爬虫依次读取 ｕｒｌ 队列的值开始工作直到队列中为空 或者达到某一限定条件时停止工作。 除了第一次将 ｕｒｌ 加入队列之外，其余时间 ｕｒｌ 入队均需确 保其未被下载过，否则会出现重复下载的情况。
在进行 ｕｒｌ 队列初始化成功后，爬虫会读取 ｌｉｎｋｕｒｌ 的队头 值。 然后开始请求相应的网页，如果请求的页面是二进制文件 的话，爬虫会将其直接保存在本地而不做任何处理，如果是 ｈｔｍｌ 文档则会进行读取并开始页面的解析。 然后会将取出的 ｕｒｌ 存 放至已经访问的数据结构 ｖｉｓｉｔｅｄｕｒｌ，因为 ｖｉｓｔｉｅｄｕｒｌ 是为了防止 重复下载的，所以本文使用 ＨａｓｈＳｅｔ 来作为它的数据结构。 在获取阶段爬虫主要是通过 ｈｔｔｐ 协议与 Ｗｅｂ 服务器进行通信［４］， 使 用 Ｓｃｏｋｅｔ 或 ＨｔｔｐＷｅｂＲｅｑｕｅｓｔｄｅ 通 过 ＨＥＡＤ、 ＧＥＴ、 ＰＯＳＴ 等方法让爬虫对相应的服务器进行请求并得到响应。
在页面请求阶段爬虫将会得到服务器返回的信息，但此时 获取的是字节流，要想将其转换为文本形式还必须进一步的识 别网页所使用的语言。 即获取网页编码。 通常有如下两种获取 网页编码的方式： （１） 从 Ｗｅｂ 服务器中返回的 ｃｏｎｔｅｎｔ ｔｙｐｅ 头信息中提取编 码，如果是 ＧＢ２３１２ 类型的编码则要当成 ＧＢＫ 来处理； （２） 从网页的 ＜ ｍｅｔａ ＞ 标签中获取。 如果和头信息中的编 码相冲突，则以这个为准。 一般使用如下正则表达式来提取 ｃｈａｒｓｅｔ：
另外，有些网页例如 ｓｏｈｕ． ｃｏｍ 由于页面信息太大往往使用 ｇｚｉｐ 压缩格式来传输，对于此类网页需要在提取编码之前判断 是否经过 ｇｚｉｐ 压缩，如果是的话则要对其先进行解压缩。 提取到网页编码之后可以将流转换为 ｓｔｒｉｎｇ 字符串，从而 获得网页源码。 因为 ｈｔｍｌ 和 ｘｍｌ 不同，容错性很强，所以很多 不规范的网站的源码往往只有开始标记而没有结束标记，这就 为爬虫的分析造成了困难。 不过本文通过 Ｈｔｍｌ Ａｇｉｌｉｔｙ Ｐａｃｋ 或 者 ＨｔｍｌＰａｒｓｅ 等开源项目组件来像操纵 ＸＭＬ 一样的操纵 ｈｔｍｌ 文档，从而提取如下信息：
通常，爬虫获取的页面有如下保存方式： （１） 对于二进制流的文件直接保存在本地磁盘而不进行任 何处理； （２） Ｈｔｍｌ 文本文件以． ｈｔｍｌ 的形式保存在本地磁盘； （３） 将 ｔｉｔｌｅ、ｃｏｎｔｅｎｔ 等字段保存至数据库。 对于此种方法， 本文将增删改查等操作形成一个存储过程来提高爬虫的效率。 在将页面保存结束后，爬虫就完成了一次工作，然后继续读 取 ｌｉｎｋｕｒｌ 中的队头值以继续工作直到 ｌｉｎｋｕｒｌ 队列为空为止。
按照上面的设计，可以完成一个基本的网络爬虫并使其工 作。 可这远远不够，因为那样的工作效率还是太低下。 在爬虫工作的过程中，很多时候爬虫都需要进行 ＩＯ 的等 待。 为了充分利用 ＣＰＵ 以及网络带宽，需要设计一个多线程并 发爬行的爬虫，这种设计方法可以让多个线程同时运行并且让 等待中的线程阻塞，不仅利用了带宽还减少了通知占用 ＣＰＵ 的线程数量。 与此同时，由于 ｌｉｎｋｕｒｌ 和 ｖｉｓｔｉｅｄｕｒｌ 这两个队列属于 公共资源，所以在对其进行增删改查的时候必须对它们进行加 锁，防止数据的脏读。 如果有同时申请两个资源的情况下还应 该进行原子操作以防止死锁。
为了尽量利用 ＣＰＵ，不让线程处于等待、休眠阻塞等状态需 要更进一步的设计［５］。 由上面的分析我们可以知道，爬虫在进 行页面请求以及将网页存入本地或者数据库的时候都是进行 ＩＯ 操作的，所以这两部分用异步 ＩＯ 操作，这样可以不用线程阻 塞在那里等待，大量的 ＩＯ 操作会自动在硬件驱动那里排队而不 消耗 ＣＰＵ。
为了使本文设计的爬虫性能进一步的提升，需要对其进行 进一步的优化。 经研究发现当请求的页面达到一定程度时， ＤＮＳ 解析以及 ｕｒｌ 查重都会耗时比较多，下面就这两部分来进 行相应的优化。
由于爬虫通常使用的是 ＨＴＴＰ 协议来进行通信，所以爬虫 通常需要进行域名解析，然后利用解析后得到的 ＩＰ 地址来进行 页面抓取。 互联网上的同一个站点下拥有成百甚至上千的网页，而这 些网页所在的 ｉｐ 地址都是相同的，爬虫在进行 ＤＮＳ 解析的时候 会进行许多重复的工作。 所以本文考虑将已经解析过的域名缓 存至本地形成一个缓存表来减少解析的工作从而提高爬虫的 效率。
由于 ｕｒｌ 中域名的大量重复使用，为了提高因 ＤＮＳ 解析而 造成的效率降低，本文引入并且优化了 ＤＮＳ 本地缓存模块。 由 于 ＤＮＳ 缓存至本地了，所以在本地会实现大量的检索、添加、删 除修改等操作。 所以，如何为这些缓存模块设计出一个良好的 结构尤为重要。 本文设计了一个以哈希表为主表，以线性指针 指向冲突域中域名 － ｉｐ 映射单元的数据结构。 其中，域名 － ｉｐ 映射单元中还应该包括域名的权值，以便定期对冲突域中的数 据进行排序而提高查找效率。 姑且先命名为“ ＤＮＳ 快查缓存哈 希链表”。 图 ２ 是我们设计的表结构
这种数据结构不仅继承了哈希表易于查找的优势，还继承 了链表易操作的特性。 将两种数据结构融合在一起，可以实现 高效的检索域名、写入域名以及排序冲突表域名等操作。 在初始化阶段，本文将域名使用哈希函数到哈希表，利用线 性指针将域名 － ｉｐ 的映射指向至冲突域，以此解决当数据量较 大时发生碰撞的情形。 在爬虫需要进行 ＤＮＳ 解析时，先利用哈 希函数找到哈希表相应的位置，再利用线性指针依次遍历找到 域名 － ｉｐ 的映射，若找到则直接命中。 否则向 ＤＮＳ 服务器进行请求并将得到的 ＩＰ 与域名一起添加至“ ＤＮＳ 快查缓存哈希链 表”。 另外，在冲突域还应该根据域名的，下面对几个常用的操 作来进行一个效率分析。
另外，为了想进一步加快效率，我们还可进行二次哈希。 即 冲突域中再进行一次哈希映射。 但这样做会浪费存储空间，且 让我们的数据变得不够结构化。 而且在实际的测试中，我们发 现使用二次哈希函数与我们设计的“ ＤＮＳ 快查缓存哈希链表 的”相比，收获的效果微乎其微。 所以我们不再做进一步的处 理。 图 ３ 是我们使用“ ＤＮＳ 快查缓存哈希链表”解析 ＤＮＳ 和普 通解析的对比.
从图中我们可以看出刚开始的时候普通的 ＤＮＳ 解析与使 用 ＤＮＳ 快查缓存哈希链表进行解析的速度差不多甚至于普通 的还稍稍快些。 那是因为刚开始时我们设计的缓存表中内容为 空，所以在除了进行正常的 ＤＮＳ 解析之外还得进行插入查找等 操作。 但当查询的域名数量达到一定程度时，我们的缓存表中 存有大量的数据，这时候优势渐渐显现出来。 最终本文设计的 使用 ＤＮＳ 快查缓存哈希链表进行解析的速度约为普通 ＤＮＳ 解 析的 ２． ５ ～ ３ 倍。 这也证明了我们的设计是优秀的。
上面我们介绍过爬虫的一些搜索策略，但可以从中发现不 管是何种搜索策略其本质都是相同的，即通过分析一个页面得 到新的 ｕｒｌ 然后抓取新的 ｕｒｌ。 所以如果不能很好地排除已经抓取过的网页，将会使爬虫陷入一个死循环中，因此爬虫在设计的 过程中会有 ｖｉｓｉｔｅｄｕｒｌ 来存放已经抓取过的网页。 互联网上的链接多达几十亿上百亿，而其中有许多 ｕｒｌ 的 长度为上百个字符，更有甚者可以达到上千个字符。 下面让我 们来算一个数据，假设爬虫已经抓取了 ５０ 亿的网页，而每一个 ｕｒｌ 平均所占字节数为 ６４ Ｂ。 因为 １ ＧＢ ＝ ２３０ Ｂ 那么存储这些 ｕｒｌ 所需要的内存为：
看到这个数据是非常可怕的，因为这不仅意味着爬虫需要 一个 ３００ ＧＢ 的内存，更意味着爬虫每找到一个新的 ｕｒｌ 都需要 遍历这 ３００ ＧＢ 的内存。 不仅浪费硬件资源，更不能保证应有的 效率［６］。 为了提高爬虫的效率，需要一个良好的数据结构来保存这 些已访问的 ｕｒｌ。 由于在 ｌｉｎｋｕｒｌ 中用到最多的为查找和插入，而 插入操作不需要改变原来数据的结构，所以所用的时间可以忽 略不计，因此 ｕｒｌ 去重的效率瓶颈查找占了很大的比重。 另外， 在提示效率的同时，ｕｒｌ 的去重效果也是极为重要的，对于一个 好的 ｕｒｌ 去重结构应该满足以下几个方面： （ １） 查找速度：上文已说，由于 ｕｒｌ 的数量巨大，所以如何快 速的实现查找成为一大难点； （２） 去重效果：好的数据结构应该能够尽可能地消除误判 的可能性，减少碰撞的概率； （３） 空间复杂度：因为内存的资源是有限的，所以应能够合 理地利用相应的内存来达到去重的目的。 为了将这三种要求结合在一起，本文利用了 ＭＤ５ ［７］ 加密的 低碰撞率，再根据 ＭＤ５ 的特性与树相结合加上现在已有的一些 去重方法，结合各方面的优点最终确定了一种基于 ＭＤ５ 加密以 及树的存储方法。 这里本文暂且称之为“基于 ＭＤ５ 的 ｕｒｌ 去重 树”，简称为“去重树”。 如图 ４ 是我们的结构图。
去重树的深度为 ＭＤ５ 的位数即 １６ 层或者 ３２ 层，去重树的 节点值是 ０ － ９，ａ － ｆ 中的一个，所以每个节点都有 １６ 个指针指 向下一节点。 而在树全满的情况下每一层的节点为 １６ ｎ－１ 个。 去重树的基本思想以及主要实现步骤如下： （ １） 将 ｕｒｌ 进行 １６ 位的 ＭＤ５ 压缩。 ＭＤ５ 加密算法有 １６ 位 和 ３２ 位两种方式，理论上来说 １６ 位的 ＭＤ５ 加密的碰撞概率为 １ ／２６４。 因而不同的 ｕｒｌ 生成的 ＭＤ５ 密文相同的可能性非常之 小，这就保证了去重效果。 虽然 ３２ 位的去重效果更佳好，但却 比 １６ 位的多耗一倍的空间，因此我们采用 １６ 位的数据加密； （２） 将生成的密文切割为 １６ 位的数组 ａ。然后将 ａ［０］ 的值 与根节点下指向的节点值相比较，如果找到，我们称这个找到的 节点为 ｒ［ １］，并将 ｒ［ １］ 指向的下一节点与 ａ［ １］ 相比较，以此类 推下去，直到 ａ［ １５］ 比较结束位置。 如果未找到则新建一个值为当前比较字符，后续节点值为下一字符的节点。 这种搜索方 式有点像计算机中找某个文件夹的方式，首先得找到具体的盘 符如 Ｃ：然后再找到 Ｃ 盘下面的文件夹，然后找此文件夹下面的 文件夹直到找到最后一个文件位置。 如果不存在则新建相应的 文件夹。
因为树的结构与操作系统文件目录的结构一样，所以可知 去重树也可以用另一种方法即基于磁盘符号的查找方式，将密 文生成的数组转为相应的路径，如果路径存在则代表 ｌｉｎｋｕｒｌ 中 已有相应的 ｕｒｌ，如果不存在说明此 ｕｒｌ 为新的 ｕｒｌ。 虽然基于磁 盘符的查找方式效率也非常的高，但往往随着 ｕｒｌ 的不断增多， 磁盘的碎片会不断的增大，最终有可能会导致服务器的瘫痪。 所以这种方式适用于中小型的爬虫，而我们设计的是去重树则 很好地为大型爬虫服务。 下面我们就时间和空间复杂度来说明 去重树的优越性。
（ １） 空间分析 刚才我们分析了 ５０ 亿的 ｕｒｌ 平均每个 ６４ 字节将要占用 ３００ ＧＢ 的内存，而如果我们用 １６ 位的 ＭＤ５ 进行 加密后只需 ７５ ＧＢ。 再者，由于树的特殊性，不同的 ｕｒｌ 生成的 密文再前一段的部分有可能是同一节点，这就又省去了一部分 的空间。 假设去重树全部排满的情况下（实际不可能排满，但 为了计算我们暂且算作排满），所有的节点个数根据公式计算：
（２） 时间分析 因为现在的爬虫通常使用 ｈａｓｈ 表来存储 ｕｒｌ 以提高存储性能，因此我们将用普通的 ｈａｓｈ 表来对比时间 性能。 一般的，哈希表的查找时间由三部分所组成，分别是使用 哈希函数映射的时间 ｔ１，查找冲突域的时间 ｔ２，以及进行字符串 比较的时间 ｔ３ 。 其中，哈希函数的映射时间相对于总时间来说 可以忽略不计，而字符串的比较时间为冲突域的查找次数乘以 每一次的比较时间。 所以最终的时间复杂度为：
接下来分析去重树的时间复杂度，因为每个节点下最多只 能有 １６ 个子节点，所以我们在构造的时候可以类似于用 ｈａｓｈ 函数直接映射而不需要 １６ 个子节点逐一比较过来，因此基于 ＭＤ５ 的 ｕｒｌ 去重树的平均查找时间只需 １６ × ｔ１ × ｔ２。ｔ１ 表示映射 时间，ｔ２ 表示单个字符的比较时间。 由于这两个时间都可以忽 略不计，所以理论上来讲我们设计的基于 ＭＤ５ 的 ｕｒｌ 去重树的 时间复杂度为 Ｏ（１） 。 是普通 ｈａｓｈ 表查找的 ｎ ／ｍ 倍。 经过实验，对 ８ 万 ７ 千多条 ｕｒｌ 进行去重以比较几种不同去 重策略的效率，如表 １ 所示。
本文所使用的测试环境为 ＡＭＤ Ｐ３４０ ２． ２ ＧＨｚ 的内存大小 为 ４ ＧＢ。 本文经过了 ５０ 次的测试最终能得出基于 ＭＤ５ 的 ｕｒｌ 去重树的去重效率为平均 ３． ２ ｍｓ。 当然，虽然本文只测试了近 ９ 万条数据，去重时间为 ３． ２ ｍｓ，但这并不意味着测试 ９０００ 万 条数据时耗时就会变为 ３２００ ｍｓ，由于我们设计结构的特殊性， 我们的时间复杂度与 ｎ 无关，因此当 ｕｒｌ 达到上亿记录时，我们 的耗时依然会非常少。 在空间方面，我们发现 ８ 万 ７ 千多条的 ｕｒｌ 只占有了约接近 ０． ５ ＭＢ 的内存，这个结论看似与我们得出的缩小 ６０ 倍空间相 违背，但实际是因为由于测试数据较小时，经过 ＭＤ５ 加密后数 据相似性较低，并没有充分体现出树状结构空间利用率的特点， 但随着数据的不断增加，加密后相似性的提高，空间利用率会越 来越高，可见我们这种设计拥有较高的可行性。
布隆 过 滤 器 （ Ｂｌｏｏｍ ｆｉｌｔｅｒ） 由 巴 顿 布 隆 （ Ｂｕｒｔｏｎ Ｈｏｗａｒｄ Ｂｌｏｏｍ）于 １９７０ 年提出， 它实际上是一个很长的二进制向量数 据结构和一系列哈希函数的组合， 用这个二进制向量来实现检 索一个元素是否存在于一个集合中的功能。 使用布隆过滤器，它只需要哈希表的 １ ／８ 到 １ ／４ 的大小就 能解决同样的问题，所以空间利用率远高于一般的数据结构，但 会有一点误报率，但最重要的是布隆过滤器的时间复杂度接近 于 Ｏ（１），不随过滤器的增大而变大。 因此，许多大数据的过滤 都是会使用布隆过滤器，爬虫的 ｕｒｌ 去重也不例外。 上面我们提到一个好的 ｕｒｌ 去重结构应该在查找速度、去 重效果以及空间利用率着手，因此下面会将布隆过滤器与去重 树先从理论上进行逐一对比。
在时间复杂度上由于布隆过滤器的大小在程序初始化时已 经定义好，不需要随着 ｕｒｌ 的增多而添加，而去重树需要在新的 ｕｒｌ 到来时动态地增加节点，因此时间复杂度虽同为 Ｏ （ １）布隆 过滤器的效果依旧稍微好些。 在空间复杂度方面，去重树消耗约 ０． ６ ＭＢ 的内存，而布隆过 滤器消耗约 ０． ２ ＭＢ 的内存。 由于数据量较小，所以去重树并不 能很好地利用自身的优点，但当数据量逐渐增大时，我们有理由 相信去重树的空间利用率会逐步赶上布隆过滤器甚至更好。 最后我们可以得出结论，在时间复杂度方面布隆过滤器与去 重树基本一致，布隆过滤器略好。 但去重效果不如去重树。 而在 空间复杂度方面，理论上在大数据量的情况下去重树占用的内存 要小于布隆过滤器占用的内存。 但小数据量的情况下布隆过滤 器的占用的内存更少。 不过由于布隆过滤器需要预先定义其集 合的大小，因此其占用的内存不会随着 ｕｒｌ 的增多而增多，而本文 设计的去重树占用的内存可以动态改变，相比而言更加灵活，因 此本文设计的去重树相对于布隆过滤器仍有较好的可行性。
为了验证我们优化后的爬虫是否达到了我们预期的目标， 我们将优化前的和优化后的爬虫分别进行了测试以形成对比。 我们测试的环境如表 ３ 所示。
在经过 ２４ 小时的数据抓取之后，普通爬虫抓取了 ６７８ ９３２ 个网页，而我们经过优化后的爬虫抓取了 ８１５ ０４３ 个网页。 并 且通过对比图我们可以发现，普通爬虫随着时间的增加，下载 ｕｒｌ 数量的增多，其下载效率正在逐渐降低，而经过我们优化的 爬虫其下载效率和刚开始时大致相同，并未因为 ｕｒｌ 的增多而 受到影响。 由于条件限制，我们不能做到上亿数据量的对比，但 我们通过对比图也有理由相信，随着时间的不断推移普通爬虫 的速度会越来越慢甚至瘫痪，而我们设计的爬虫则不会受到此 影响，拥有较好的可行性。
结 语
本文主要对爬虫进行了不同模块相应的设计以及对 ＤＮＳ 解析以及 ｕｒｌ 去重方面进行优化。 提出了 ＤＮＳ 快查缓存哈希链 表以及基于 ＭＤ５ 的 ｕｒｌ 去重树，使得 ＤＮＳ 解析的速度相对于不 优化前提高了 ２． ５ ～ ３ 倍。 而在理论上使得 ｕｒｌ 去重方面使得空 间利用率相对于普通的队列存取方式提高 ６０ 倍，在时间复杂度 方面也提高至了 Ｏ（１） 。
但是，本文的爬虫仍有许多不足的地方，首先由于条件的约 束，本文的爬虫不能抓取几千万甚至上亿的页面进行测试，从而 并未使得 ｕｒｌ 去重树的空间利用率得到较好的证实。 而且由于 数据量不够，我们设计的结构并不能保证在大数据量的情况下 仍然保持高效，仍然是理论为主.

相关文章：基于语义的毕业论文题目相似性分析