【毕业学位论文】（Word原稿）一种可扩展的高效链接提取模型的实现与验证-计算机网络技术

封面页 北京大学计算机科学技术系苏杭学士论文 一种可扩展的高效链接提取模型的实现与验证 教师指导意见： 链接提取是网页搜集系统中的一个重要组成部分。苏杭同学的毕业论文工作，是对这一部分的突出贡献。 论文所涉及的工作包含了对搜索引擎技术的一般认识。链接提取模块以“容错性”，“正确性”，“全面性”，“高效性”和“可扩展性”为设计目标，在充分认识到传统的链接提取方法不足的基础上，提出新的设计思路，并且实现。该模块包括信息提取，信息加工，信息分析和信息存储四个过程。并成功的运用于“天网”搜索引擎。论文内容丰富，所涉及的工作量大，且有较强的系统性，是一篇很有价值的论文。 在毕业设计工作 的过程中，苏杭同学态度端正，积极努力，精力集中，表现出很强的进取精神和踏实的工作作风，为“天网”的发展做出了贡献。 指导教师：闫宏飞 2003年 6月 18日 北京大学计算机科学技术系苏杭学士论文 一种可扩展的高效链接提取模型的实现与验证 摘要 随着 来越广泛的发展与应用，搜索引擎已经成为人们从中查找信息的重要工具；在搜索引擎的系统实现中，如何通过链接提取发现更多更广的 本文总结了设计链接提取模块所要求的“容错性”、“正确性”、“全面性”、“高效性”和“可扩展性”等五个目标，并从这些角度去分析 传统的链接提取方法的不足，并作为改进，提出了一种新的设计思路。 本文将链接提取的过程划分为信息提取，信息加工，信息分析以及信息储存四个过程来进行研究。信息的获取通过 法分析方法从文档中得到初始据；信息加工阶段通过运用 后在信息分析过程中进一步地筛选与过滤；最后将结果存储在一个双链表结构中。 基于上述方法，本文实现了一个新的链接提取模型，并将该模型运用于北京大学天网 索引擎；在获得足够的实验数据之 后，全面的比较了这种新的链接提取模式与传统方法在各项指标上的优劣。结果表明该模型有明显的优势。 关键字：搜索引擎，链接提取，统一资源地址 ( 北京大学计算机科学技术系苏杭学士论文 一种可扩展的高效链接提取模型的实现与验证 s eb is an to on to in a to RL is a in RL of a is is NF is in in is in a On a RL WW to is in 杭学士论文 一种可扩展的高效链接提取模型的实现与验证 正文目录 1 研究背景 . 6 2 系统目标 . 7 3 传统方法 . 9 4 系统实现 . 10 计模型概述 . 10 息获取 . 11 . 11 . 13 设计 . 15 息加工 . 18 符串规整 . 18 析 (. 18 相对 . 20 息分析 . 22 确性验证 (. 23 选器 (. 23 价性判断 (. 24 息储存 . 25 5 性能评测 . 26 6 实验结果 . 28 7 不足与改进 . 29 附录 A 错误链接举例 . 31 附录 B . 32 附录 C 通用的 . 33 参考文献 . 34 致谢 . 35 北京大学计算机科学技术系苏杭学士论文 一种可扩展的高效链接提取模型的实现与验证 图表目录 图 1(将要的搜索引擎工作原理示意图 ). 7 图 2(旧系统进行链接提取的原理模型 ) . 9 图 3(新的设计思想的工作原理模型 ) . 4( . 5( . 6(递归式过滤注释嵌 套的方法流程图 ) . 7(双链表存储结构示意图 ) .京大学计算机科学技术系苏杭学士论文 一种可扩展的高效链接提取模型的实现与验证 第 6页 1 研究背景 因特网 (从诞生开始就以惊人的速度蓬勃地发展着。当今，因特网上的网站数目不断的增加，网站之间的链接关系越来越复杂，所容纳的信息量也以指数爆炸 式地增长着。据统计，现在 1，每年的增长率突破三千万 1。如此巨大的信息量和增长速度使得从 了解决这一困难，搜索引擎在 20 世纪 90年代初期应运而生。 当今最流行的 索引擎，以著名的 们通过网页搜集系统从 获取网页资源，然后将其中的信息索引入库，并在用户需要时提供与他们希望查找的内容相关的网页资源列表。 搜索引擎 由网页搜集系统 ( 索引器 (链接提取模块 (个重要部分组成。其中的链接提取模块，也是本文最为关心的部分，负责从网页资源中提取新的链接信息。它的设计将直接影响整个搜索引擎的效率： 它识别网页中所包含链接的能力会影响搜索引擎的信息覆盖范围 2，因为所有网页资源的链接都是通过它分析得到的。如果分析能力有限，则会有相当一部分有用信息未被搜索引擎所函盖，从而降低了其实用性。 它对链接识别的准确性将影响搜索引擎的效率。如果它不能准确地判断网页中的链接信息，而将错误的链接传给网页搜集系统， 会使其在等待错误结果 中浪费大量宝贵的时间，从而大大降低日访问量。 它本身对链接提取的算法代价不能太高，否则会引起搜索引擎的效率瓶颈。 由此可见设计一个好的链接提取模块的重要性。本文基于上述目的提出一种新的链接提取模块的设计思想与设计原理，并将其应用于北大天网系统 (北京大学计算机系网络与分布式系统实验室开发的 索引擎 3)并通过评测证明该模块是高效的。 准确的数字为 17,638,2971 2003 这里的搜索引擎指的都是索引式 (索引擎，下同。 错误的链接往往会使网页搜集系统得到连接超时的错误或者 404错误，在等待中浪费很多时间。 北京大学计算机科学技术系苏杭学士论文 一种可扩展的高效链接提取模型的实现与验证 第 7页 2 系统目标 因特网中不同网页通过超文本链接协议 (相链接的结构构成一个有向 图，其中以每个网页为顶点，网页之间的链接关系为有向边。网页搜集系统从其中一个顶点出发在图中进行遍历，每到达一个新的顶点便会将对应网页的内容抓取下来，并通过链接提取模块找到其中包含的新链接并提供给网页搜集系统。网页搜集系统便可以沿新的有向边继续上述的遍历过程了。整个过程可以是完全自动化的 (只要提供一个起始的顶点，网页搜集系统就可以通过不断获取新链接自动地在因特网中进行遍历 )，然后索引器将搜集到的资源信息进行索引并存入数据库以备今后查询使用。 上述过程可以用下面的示意图来表示： 图 1中简要说明了搜索引擎的工 作原理及其各部分间的关系。从图中链接提取模块的输出将直接做为网页搜集系统的输入，因此，它对网页搜集工作的效率与质量起着决定性的作用；另外，它的输出结果对索引器也有着间接影响，如果网页中的许多无用链接 (如广告等 )被提取了出来，则索引器也会将这些“噪音”网页索引入库，从而降低了数据库中信息的质量。 基于上述分析，本文归纳和总结了设计链接提取模块的基本原则与目标： “容错性 (：必须保证在任何情况下不能出现诸如内存溢出，内存泄露，非法指针，死循环，或者其他没有处理的异常错误。在网页搜集系统自 动对因特网进行遍历并索引网页时，程序可能会连续运转几天甚至几个星期不停。如果某个模块在此期间出现了上述的错误，可能会导致整个作业崩溃，甚至当机的惨重后果。因此，极好的容错性是必须的，也是最基本的要求 “正确性 (：要保证提取出来的链接都是正确可用的。这并不是说在链接提取的过程中就能够判断每个链接都是可以连接到北京大学计算机科学技术系苏杭学士论文 一种可扩展的高效链接提取模型的实现与验证 第 8页 主机的，这里的“正确”指的是格式上的正确，即要能够将不满足格式要求的错误链接识别出来并过滤掉。错误的链接可能是网页制作时不经意的打字错误或是使用了无法识别的字符导致的，在附录 举了许多常见的错误链接示例。正确性的优劣将直接影响到网页搜集系统的工作效率。 “全面性 (：链接提取模块要尽可能多地将网页中所包含的各种链接信息提取出来。网页中包含链接信息的形式可能是多样的，链接信息可能出现十分明显的标志中 (如 )，还可能隐藏在其他信息里，甚至脚本中。因此，模块必须能准确发现以各种形式出现的链接信息。有些链接信息可能是搜索引擎不需要的 (比如图片链接、程序链接等 )，但模块也应该能找到它们，为今后系统需求的扩展做准备。全面性的优劣直接影响搜索引擎的信息覆盖率 2。 “高效性 (：链接提取算法的时间代价不能太高。图1中描述的搜索引擎的整体工作的大部分时间花在了网络延迟上，也就是等待网页搜集系统将网页的内容从因特网中抓取下来的时间。其他模块所消耗的系统时间都是很小的。如果由于算法设计的不好使得其时间代价过高 (比如超过 O(规模 )，则链接提取的过程就会消耗过多的系统时间，甚至超过了网络延迟的时间。这同样会降低系统对因特网的日访问量，降低效率。 “可扩展性 (：在设计的时候应该为今后的功能扩充留有余地，这主要 体现在： 可以根据系统的不同需求得到网页中不同形式的链接资源。比如，可以只提取图片链接，或者只提取 针对新产生的网络协议能够在不对源程序做大改动的前提下方便地增加对新协议链接资源的支持。 可以适应新版本 果新版本的 可以在不对源程序做大改动的前提下实现对这些新形式的识别并从中提取出链接信息。 然而，上述这些原则有时很难同时满足，比如“正确性”和“全面性”本身就存在着某种内在的矛盾。有时为了保证“正确性”就不得不放 弃某些“危险的”链接，而采取某种相对保守的标准，这样势必会丢失一些链接信息。例如 图对脚本程序中隐藏的链接信息进行提取就是一种危险的行为。在这种“正确性”与“全面性”相冲突的情况下，“正确性”应该优先得到满足。只有这样，才能使整个搜索引擎高效率无故障地高速运行。 北京大学计算机科学技术系苏杭学士论文 一种可扩展的高效链接提取模型的实现与验证 第 9页 3 传统方法 传统的链接提取方法中最具代表性的，也是北京大学天网 3原先所使用的方法，是在网页中匹配 ”关键字，然后将它们后面的链接信息提取出来。这样做的原理是，在 部分的链接 信息都包含在少数几种元素 (，比如 , , , 等，而且这些元素基本都是以 ”属性值来容纳链接信息的。 下图中简要说明了传统链接提取方法的工作流程。 根据图 2中的流程，链接提取模块会在网页中寻找所有出现的 ” ”键字，然后将其后的属性值提取出来作为链接信息进行加工。加工的工作主要包括将相对 换为对应的绝对 将不满足系统要求和有重复的链接信 息过滤掉。最后将得到的结果储存到一个单链表结构中供网页搜集系统查询。 从图中可以很明显的看出，传统方法对上一章中提到的几个目标的实现都存在很大的差距，具体表现为： “正确性”方面：如果所匹配到的诸如 ”关键字不是在是在网页的正文文字中被提及，或者在注释中出现，提取出来的就会是错误的结果。 “全面性”方面：很多链接信息并不是对少数关键字的简单匹配就能够找到的。比如 ： 。在上例中 ， ”属性值 ”义这个 元素中包含有重定向的链接信息 ， 并在 ”性值里具体给出这个 因此，传统的方法可能会漏掉大量重要的信息。 “可扩展性”方面：传统方法很难通过对关键字数量的扩充来弥补其“全面性”方面的不足。上述 的例子就很好地说明了这一点： ”性取不同的值，后面 ”性值就对应北京大学计算机科学技术系苏杭学士论文 一种可扩展的高效链接提取模型的实现与验证 第 10页 了 不 同 的 含 义 ， 只 有 ”取值为 ”， ”才包含有链接信息。所以简单对关键字进行匹配是无法适应这些复杂情况的。 从上面的分析可以看出，传统的链接提取方法存在着明显的不足，会严重影响整个搜索引擎的质量与效率。通过分析也可以看到，图 2中所阐述的传统方法的模型本身是存在严重缺陷的，根据这个模型设计出来的链接提取模块有上述的不足也就在所难免了。因此，要想消除这些问题，就需要在方法模型的层次上重新设计出一种更加合理的架构。 4 系统实现 计模型概述 为了实现一种更加合理与高效的链接 提取方法，本文将整个链接提取与链接分析的过程划分为四个阶段：信息获取，信息加工，信息分析与信息储存。 北京大学计算机科学技术系苏杭学士论文 一种可扩展的高效链接提取模型的实现与验证 第 11 页 图 3中说明了本文提出的可扩展的高效的链接提取方法的工作原理，并将全部步骤划分为上述的四个阶段。这四个阶段描述了链接提取过程中为了实现第二章提出的设计目标所必须进行的步骤。这四个阶段中，前者是后者的条件，后者是对前者的补充，它们缺一不可，并最终将所有满足条件的链接信息提取出来，将不满足条件的结果过滤掉。它们对信息加工和处理的层次不断深入，循序渐进地将提取出来的初始数据 (范化 (符合 对其进行筛选和过滤，并最终得到正确且有用的结果，从而提高了链接提取模块的质量与搜索引擎的效率。 下面分别就上述四个阶段进行剖析与说明。 息获取 为了能够更好地对 多、更准确的提取其中的有用信息，不能仅仅将网页的内容看做是简单的线性文本 (言是符合 4规范的，因此它是具有自己的文法特征 与文档结构的。一个标准的 成，在元素间可以存放文本正文 (不同的元素在文档中有着不同的功能。每个元素都是用 ”括起来的实体(其中以元素名开头，后面接若干属性 (不同元素中允许出现的属性种类也互不相同。有的属性名后面可以用 ”=”接属性值，有的属性则没有属性值 (如 无值属性 )。属性值可以用双引号括起 (在值中允许存在单引号 )，可以用单引号括起 (在值中允许存在双引号 )，也可以不被 引号括起来 (这样的属性值中不能有任何种类的引号或空白字符出现 )。下面是一个正确的示例： 中， ”a”是元素名， ” ”a”的属性名， ” ”属性值， ”文本正文， /a是与 对应的结束标签 ( 又由于 与网页相关的信息 (也包括链接信息 )都是作为属性值出现在不同元素中的 (比如 中的 ，所以可以根据 取出所有与链接信息有关的属性 (值 )。 下面是 这个表达式旨在描述提取 值 )的方法。它并不涉及 比如，有些元素必须具有结束标签，或者对元素在文档中出现位置的限制等 )，因为这些文档结构方面的规定不能提供有关链接的更多信息。 北京大学计算机科学技术系苏杭学士论文 一种可扩展的高效链接提取模型的实现与验证 第 12页 = *( ) = = “” = “” = *(“=” *( = = *( *( “” *(“” *( = 1*(终结符的定义： = “ “ | “t” | “n” | “r” “ “n” “” - “” - “” = = “A” | “B” | | “Z” = “a” | “b” | | “z” := 文档所用字符集 (所有字符的集合 利用上述文法对 页进行文法分析的工作可以安排给一个单独的模块来完成。这个模块负责网页的分析和对其中所有元素及其属性的提取，并通过向使用者提供接口的方式将这些提取出来的信息反馈给调用者。因此，可以把这个模块看做是一个封装好的 很明显，上面描述的文法是标准的正则文法 (56，因此可以通过构造的方法有穷自动机 (56对其进行分析。 字符串常量被 ”括起； *表示后面的内容重复 )；可选项用 括起。 北京大学计算机科学技术系苏杭学士论文 一种可扩展的高效链接提取模型的实现与验证 第 13页 图 4中完整描述了 值 )的流程。图中声明了三个接口，分别用于向调用者返回网页中下一个元素的元素名，其属性名与属性值。图 4中的流程图其实就相当于一个有穷自动机的简化形式，并通过它实现了对前面正则文法的解析。 下面简要的对图 4中的工作过程进行说明。图中左半部分是寻找 (一个元素的结束标志 )，则说明该元素中没有声明属性，于是直接跳转到最开始，继续查找下一个元素；否则，说明有属性声明，于是转到图 4右半部分，开始分析属性名和属性值。 如果属性名后面没有 =，则说明这个属性是无值属性 (类似属性 )；否则，对 =后面的属性值进行提取。属性值可能是被双引号 (”)或单引号 ()括起来的，也可能没有被引号括起来，于是分三种情况分别进行提取。得到属性值之后同样要判断后面是否出现元素的结束标志 ， 如果不是，则说明还有下一个属性要处理，于是重复上面的操作，直到处理完所有的属性。在整个过程中，应当加入适当的异常处理。比如，对属性值的引号不配对，元素名过长等异常情况进行捕获，以保证“容错性”要求。 而，这些信息当中的大部分都与链接信息没有关系。因此，要对 杭学士论文 一种可扩展的高效链接提取模型的实现与验证 第 14页 文法分析引擎提取的信息进行有选择地处理。为了解决这个问题，我们引入 有些像现在广 泛提到的插件 (它“插手”某个系统的处理过程，并进行额外的处理工作，从而对系统的功能进行了扩充或修正。 我们引用 它们挂接在 获提取出来的信息并进行额外的加工分析。每个 图为 每当分析引擎找到了下一个 就会将结果通过接口传递给所有的 些 后，返回分析引擎继续查找下一个元素。如此循环。 每个 定规则工作。它必须判断当前传递进来的是否是它要处理的特定元素。如果是，那么这个后从中获得有用的信息并进行加工处理。 然后，这个 统会调用下一个 也会做和上面类似的工作。 图 5中的示例中注册了 3个 个 如，图 5中，它们处理了 ,三种元素，并从这些元素的“ ”性值中析取 从前面的分析可以看出，这种 这种设计体现了很好的模块化设计思想：分析引擎被设计成一个独立封装的完整模块，每个 们通过接口彼此传递信息并相互调用。这样做使得每个模块都可以单独的进行调试与扩充而不影响其他模块，而且它们可以像搭积木一样随意地进行拼接。 对“全面性”目标的实现：通过 以将网页中所有元素所包含的信息没有疏漏地提取出来而不会漏掉任何有用的信息。 对“可扩展性”目标的实现：很好的模块化设计使得每个模块的改 进都变得很容易。而且通过挂接新的 足新的系统需求，而不用大量修改原有代码。 北京大学计算机科学技术系苏杭学士论文 一种可扩展的高效链接提取模型的实现与验证 第 15页 设计 谓的有用信息狭义地讲就是指包含 面详细讨论了这些信息在 的出现形式与提取方法。 包含 根据归纳，一个 息所在的属性名 备注 a ”性的值也应该被提取出来用以指示链接目标的字符集及其使用的语言。 素用于重新声明当前网页的基地址 ( 架目标 嵌框架目标 定 的信息不会被浏览器显示，但它提供了与当前网页相关的若干重要线索。 性的值为 ”才有效 ) 才包含链接信息。 ;字符的后面 (前面是表间隔时间的数字 )。 许多网页都只声明了这样一个 元素，使得浏览这样的网页时浏览器会自动重定向到其中包含的 应该为上表中的每种情况设计单独的 而很全面对 此外，利用前面提到的 可以提取文档中其他的重要信息 (广义上的有用信息还包括对索引器索引该网页有帮助的信息 )。这 些重要信息包括文档的标题 (重要的 网页所使用的字符集 (语言 (等。附录 对注释的处理 作为一种特殊的 释 ()中的内容是必须被忽略的，即使其中包含大量的 有可能是已经过期的无用信息。因此，北京大学计算机科学技术系苏杭学士论文 一种可扩展的高效链接提取模型的实现与验证 第 16页 必须增加一个 之所以使用 注释过滤掉而不是简单的将它忽略 (没有定义专门的理它就相当于将它忽略 )， 是由于注释在文法上的特殊性：在它的开始标志 (”)之间可以存在任意多的 字符，如果不进行特殊处理，分析引擎会将这样的 判断为注释元素的结束标志，导致分析的错误。因此必须设计一个 另一个值得注意的地方是，注释是允许嵌套的，不能只是简单地找到第一个出现的 ”就把它认为是整个注释的结束标志。 图 6中给出了递归处理的示意图。 对脚本程序的处理 与注释十分类似的还有一个元素，那就是 元素。在 与中间包含着脚本程序，脚本程序可以由不同的脚本语言书写。它的特殊性在于，在脚本程序中可能隐藏有 息，甚至有些网页完全由脚本程序生成，其中的链接信息也就都包含在脚本程序当中了。因此，为了满足“全面性”的要求，应该对脚本程序进行分析，提取出其中隐藏着的 然而，对脚本程序的分析是极其危险的行为，而且论分析程序写的多么复杂，许多隐藏在脚本中的 最为理想的分析程序通过模拟脚本的解释程序来分析脚本中的相关信息。然而分析程序与脚本的解释程序有着本质的区别。 在浏览器中，脚本存在着一个运行时环境 (我们称其为浏览器环境，这个环境为脚本的运行提供了必不可少的动态支持。比如，在动态网页 (，脚本可以以变量的形式引用 某些控件的值 (编辑框，复选框等 )，并使这些变量的值参与计算，得到动态的结果进行输出。这个“动态”的概念在整个过程中就显得尤为重要，浏览器环境为北京大学计算机科学技术系苏杭学士论文 一种可扩展的高效链接提取模型的实现与验证 第 17页 脚本引用这些控件的值提供了支持，于是脚本的解释程序可以根据用户输入的不同数据得到不同的 动态结果。 然而，分析程序无法提供上述的环境。分析程序的输入是“静态”的脚本，分析程序可以对它进行模拟并对其行为作出分析，然而，当脚本引用运行时环境(即浏览器环境 )的动态数据时，分析程序是无法得到动态结果的，因为用户的输入等动态信息是不可得的。 因此，无论分析程序设计得再复杂再完善，它处理脚本程序对动态数据的引用时就变得一筹莫展。事实证明，在脚本中包含的 如， ”+其中的据。这样的情况下，分析程序是无法得知 通过上述分析可以看出，脚本程序中的链接信息是无法被 100%地提取出来的，而且在提取的过程中存在着很大的风险。如果分析程序做得不够复杂与完善，则提取出来的链接很有可能是错误的。比如上面的例子，很有可能就将链接的内容提取成了 ”+而这种错误恰恰是天网系统中原先使用的链接提取模块所常犯的。这严重违反了“正确性”的设计目标。因此，宁愿跳过脚本程序的分析，也不应从中提取出大量的错误 链接来影响效率。 下面是一组测试，从测试结果可以看出脚本程序中上述形式的动态链接所占比例之大，以及忽略脚本程序对“全面性”原则的损失之小。 测试的数据是从天网系统的链接数据库中随机抽样选取的，测试的结果是手工统计分析的，并列在下表中： 参加统计的 脚本程序总数 其中包含的正确有用的错误的 没有价值的232 452 234( 126( 92( 表 1：网页中脚本程序所包含的 统计 表 1中所谓 “错误的 的是与前面例子中类似的通过动态数据计算求得的 没有价值的 的是一些对索引器 (有价值的者某些弹出小窗口的广告链接。 从测试结果可以看出，脚本程序中存在相当大比例的“危险”的。根据前面的证明，是无法得到这些 1中的数据还说明即使能够大量准确地提取出脚本程序中包含的正确的链接信息，这些正确的链接中还会有 28%(92/(234+92)28%)左右是无用的。 由此可以得出结论，脚本程序中所包含的链接有相当大的比例是无法提取 这些 的数目统计中没有包括那些引用外部脚本文件 (比如 的情况。 北京大学计算机科学技术系苏杭学士论文 一种可扩展的高效链接提取模型的实现与验证 第 18页 的，而且可以提取的链接中也有很大一部分是广告等无意义的链接。再根据第二章中对各个设计目标的分析，我们采用一种折中的方案，就是完全不对脚本程序进行分析处理。这样做对“全面性”原则的损失 (从上面的测试结果可以看出 )是很小的，而且保证了“正确性”。 息加工 通过 而这些信息还是格式极不规整的初始数据 (下面，通过“信息加工”的几个步骤将这些初始 数据规范化 (这些步骤包括： 相对 在进行 两个步骤之前必须先将得到的 保证在后续加工过程中的正确性。 规整的过程包括如下两个部分： 字符串的