【毕业学位论文】（Word原稿）面向主题的中文搜索引擎的设计与实现-计算机系网络与分布式系统

摘 要 络的迅猛增长使得搜索引擎面临了前所未有的挑战，搜索引擎如何适应这种规模的急剧膨胀，成为一个备受关注的问题。面向主题搜索引擎可以有选择性的抓取与主题相关的网页。选取的对象是一个或一组事先预定义的主题，其特征由样本网页标志，而不是关键词。一般性的搜索引擎总是抓取尽量多的网页以满足所有可能的查询请求；而主题搜索被设计为只抓取与选定主题相关的网页。这不仅能够大大减少系统对硬件和网络资源的需求，而且还有助于提高抓取的准确率和搜索结果的更新速度。 本文首先对比通用搜索引擎与主题搜索引擎的区别，总结主题 搜索引擎的优点；然后介绍目前世界上主题搜索引擎技术的发展状况。接着，综述了面向主题中文搜索引擎的设计，详细介绍涉及该领域的三个核心技术：文档分类技术、中文处理技术和网页搜集预测技术。对于以上三种技术，我们在简述已知算法的基础上，都阐述了具体系统的实现方案。其中中文切词问题作为工作的重点，在文章中有比较详尽的介绍，包括中文处理的背景知识，中文切词软件的基本原理和中文切词词典的改进。 关键词： 用搜索引擎、 面向主题搜索引擎、文档分类算法、网页搜集预测算法、中文切词 目录 摘要 1 目录 2 第一章 引言 3 第二章 面向主题中文搜索引擎的设计综述 5 第三章 文档自动分类的主要算法和具体实现 7 档分类的主要算法 8 持向量机（ 法 8 单 法 8 法 9 法 9 档分类算法的实现 10 档的向量表示 10 征集的选取 11 算待分类文档与训练集的相似度 12 断待分类文档所属类别 12 第四章 中文信息处理问题 14 文信息处理研究背景 14 文信息的特点 14 文切词对系统的重要性 14 文切词 软件的基本原理 15 典的格式和数据结构表示 15 体切词过程 18 中文切词软件的修改 22 第五章 网页搜集预测算法设计 23 文本链的相关研究 23 页搜集预测功能的设计 24 第六章 工作总结和对未来的展望 26 致谢 参考文献 第一章 引言 近年来， 规模持续以令人惊叹的速度增长着。根据 2000 年 4 月在波士顿举行的第 5 届搜索引擎年会的会议报告 1，当时全球的网页数量已经超过了十亿。根据 索引擎的索引库中网页数量的统计，全球网页数量到2002 年 5 月已经达到 20 亿。 中国的发展速度也十分惊人。根据国互联网络信息中心 )2在 2002年 1月的统计信息表明，中国的 77100 个，能上网计算机 约有 1254 万台，比 2001 年 1 月的统计结果多出 350 万台，上网人数达到 3370 万，比 2001 年多了 1100 万。 和网络规模的迅速膨胀形成鲜明的对比，尽管各个大型的通用搜索引擎都维护着庞大的索引，但是索引的规模增长远远不及网络本身。相对整个网络，他们仅能够覆盖一小部分。以 索引擎为例，在 2001 年，他们的索引库覆盖了大约 个网页。因此，一个搜索引擎的查全率，特别是抓回的相关网页和所有相关网页的比例相对较低。此外，很多返回的网页都已经过期或者地址已经转 移。查准率较低也是通用搜索引擎的一个问题。这主要是因为用户以关键字的形式提出查询请求，搜索引擎系统再以关键字匹配返回结果。同一个关键字可能在多种不同的上下文环境中出现，其中大部分都与用户希望的请求无关。这就造成了搜索引擎返回的结果中只有一小部分是真正相关的网页。 这些通用搜索引擎的缺点主要来源于它们力图覆盖整个网络，并为所有可能的主题提供查询服务的目标。面向主题的搜索引擎克服了以上的缺点，拥有更好的查全率和查准率，因为它们将搜索网页的内容限定在一定的领域里，有效所建了搜集的范围。一个面向主题的搜索引擎用一部 分事先选定好的网页作为体现用户兴趣的样本。为了获得更多相关的网页，主题搜索引擎从一个给定的集合出发，递归的抓取集合中网页指向的所有出链接。经验表明一个超链往往连接的是两个相关度较大的网页。更准确的讲，两个链接在一起的网页比两个随机选择的网页更有可能是与同主题相关的。 主题搜索引擎的一个主要问题是以什么顺序访问网页里的链接出口才能尽量多的访问相关主题的网页，而只抓取一小部分无关页面。这是主题搜索引擎面临的一个重要挑战，因为有高度相关性的网页上也会有低相关度的链接出口。 自 1994 年搜索引擎问世，面向主题的搜索 引擎就已经被提上日程。 1999 年， 作了较完备的面向主题搜索引擎的模型。系统使用分类层次目录，由用户在感兴趣的领域作出标记，作为搜索引擎的主题。用户可以在浏览的时候标识感兴趣的网页，然后按照 种经典分类方法将该网页分入对应类别中作为样本。该搜索引擎主要由三部分组成：搜集器，分类 器和被作者称之为“蒸馏器”（ 进程。分类器判断一个超文本文档与主题的相关度；“蒸馏器”（ 在超文本链接分析的基础上，识别出具有很多高相关度出链的 目录型网页（ 搜集器则根据分类器和“蒸馏器”提供的控制信息对未访问队列进行动态配置。通过试验，他们指出在有限的领域内挖掘网上资源是可行的；如果某个网页与主题具有高相关度，可以认为它在网络中的邻居（即出链接）也是相关的。 另一种搜索引擎由 学的 开发。他们通过先搜集“更重要”的网页使搜集过程更加有效。这种“重要”性主要体现在与查询请求的相似程度，网页的入度（即链向这一页的网页数），网页的出度（即这一网页的链接出口数），网页评分（ 网页的位置特点等方面。一个网 页的网页评分（ 指向它的网页的 加权和。 研究比较了这几种衡量方法的区别。他们发现使用网页入度计数的搜集器的表现近似于深度优先搜索，倾向于优先访问一个“簇”（ 的网页，而且不同的初始网页集合的选取会对最终的结果造成比较大的影响。而使用网页评分（ 法的搜集器则似乎不受这方面的影响，并且较好的结合了深度优先和广度优先两种方法的优越性。 2001 年的研究评估了几种不同搜集策略的优劣。他们的试验为100 个主题分别建立了分类 器，以衡量搜集到的网页的相关度。 出一个好的面向主题搜索引擎应该将搜索的范围尽量保持在向量空间中与主题邻近的区域内。他们总共评估了三种不同的搜集策略： 集器 : 优先队列中的优先级是包含该出链的原网页与主题的相关度 集器 : 以网页评分（ 高低为顺序搜索，每搜集25 个网页重新计算一次评分 使用神经网络算法，考虑链接周围的上下文 他们的试验发现 现出性能最优，紧接着是 后是且他们认为 于主题搜索任务来说，过于通用化，不能体现主题性。 这些工作为我们的系统提供了良好的参考和依据。在此基础上，笔者将在下一章综述面向主题的中文搜索引擎的设计工作。 第二章 面向主题中文搜索引擎的设计综述 实现具体系统的简介 我们的系统名称为“面向课程的素材收集子系统”，将被用于“远程教育”项目的一部分，其目的是寻找一种技术，通过该技术，可以在 搜索到与给定课程相关的各类教学素材，为教师备课提供参考资料。 面向课程的素材收集子系统的设计 本系统是基于天网搜索引擎 系统的。天网由于采用了可伸缩的分布式结构、查询 引数据库和检索数据库分开等先进、有效的技术，使得系统占用资源少、信息收集速度快、用户查询响应时间快、查准率和查全率较高。 原天网系统的体系结构如图： 图表 1 天网搜索引擎系统的体系结构 其中， 收集分析子系统： 负责从网上收集主控子系统指定的网页，分析网页 的内容。从中提取关键词、摘要和超文本链，将分析的结果回送给主控子系统作进一步处理； 主控子系统：负责按照一定的规则选取待访问的 交给收集分析子系统，然后处理收集分析子系统返回的结果信息，将它们存入网页信息数据库； 索引子系统：负责处理网页信息数据库中的信息，生成查询索引库； 询页面：是天网系统和用户之间的接口，负责向查询子系统递交用户的查询请求； 查询子系统：负责处理用户的查询请求，在查询索引库中查找相关信息，将查询的结果返回给用户。 为了实现在现有天网系统的基础上实现文档自动分类和网页搜集预测，我们设计了两个处理进程 分类器和反馈进程 ；由原网页信息数据库中导出 分类结果数据库，分类结果数据库中的信息提交给索引子系统；分类器负责 实现对收集 的网页的自动分类；反馈进程根据分类结果数据库中的信息计算未访问网页的预测权值，将其反馈给主控子系统；改造现有天网系统的收集分析子系统、主控子系统、索引子系统和查询索引库，使它们能处理和储存自动分类系统返回的分类信息，在 询页面上增加分类目录，改造查询子系统，向用户提供面向分类目录的查询功能。 经过改造后的收集、控制子系统的运行流程图如下： 图表 2 收集、控制子系统运作流程图 第三章 文档自动分类的主要算法和具体实现 文档分类是将文档划分入事先确定数目的类 别中，每个文档可能被归入某个或多个类别中，也可以不属于任何类别。利用机器学习（ 术，文档自动分类的目标是实现通过学习例子自动对待分类文档指派类别。 文档自动分类技术类似于一种经验学习方法，基本思路是首先搜集一组与主题高度相关的网页作为样本，这些网页的集合就称之为“训练集”。每个训练集中的样本都由专家人工的分配了类别标签，因此具有高度的准确性。之后，根据待分类文档与样本之间的相似程度来给待分类文档指派类别标签。 持向量机（ 法 法 5是 1995年由 题时引入的一种经验学习方法。这种方法定义在向量空间中，问题的核心在于寻找一个最佳解决方案，将线性可分割空间中的点用一个决策面划分为两部分。 用结构风险最小化（ 理构造的 超平面。 将 且将其与其它方法进行性能对比。 他的试验结果表明 单 法 简单 B)算法 5是 机器学习（ 常用的一种算法。法 作了两个假设：（ 1）对于属于这个类的文档，特征项之间（即文档中词与词之间）是独立无关的；（ 2）对于不属于这个类的文档，特征项之间也是独立无关的。 这个假设使得 法比其它 法要有效的多（其它 法具有指数级的时间复杂性）。 这种方法的基本思想是给定一个类和一篇文档，利用 概率公 式：P(A|B)=P(B|A)*P(A)/P(B)，根据这个类对于每个特征项的条件概率计算它对于这篇文档的条件概率。给定一个类和一篇文档，令 ， 其 中 示文档中出现的第 i 个特征项， n 为文档中出现的特征项的总数。根据全概率公式，我们可以得到如下式子： P( + | = P( + ) * P( + ) / P( ； P( - | = P( - ) * P( - ) / P( ； 其中 P( = P(a1 P( + )表示待分类的文档所处的领域中的文档属于这个类的概率， P( - )表示不属于这个类的概率。根据两个假设，有P()=P()*P()*P(a n|+) ，P()=P()*P()*P(a n|-) 。如果 P( + | P( - | ， 则就判定这篇文档不属于这个类。 简单 法利用两条假设极大地降低了计算的复杂度，使得算法的实现成为可能，但是这两条假设缺 乏严格的理论推导作为基础，无法保证它的正确性，这也在一定程度上限制了算法的性能。 法 5的缩写，是 由一组训练集和类别集合自动学习生成一个多元回归模型。训练的数据用输入 /输出的一个向量对表示，其中输入向量是一个传统向量空间模型中的文档向量（用特征项及其权值表示），而输出向量是该文档对应的类别。通过解决一个的线性最小平方法（ 题，获得一个特征项类别的回归系数组成的矩阵： 2m r g 矩阵 A 和 B 分别代表了训练数据的输入和输出，其中 示一个特征项 文档 的权重， 值为 1 或 0， 1 表示文档 于类别 0 则不然。矩阵 描述了特征项和类别之间的关系。最后，对类别的权重进行排序，形成输入文档的候选类列表。通过给这些类别的权重设置阈值，就得到了输入文档的指派类别。 NN(法 5法的缩写，是模式识别中一种被广 为学习和研究的统计学方法。 早就被用在文档分类中，并且是几种经验学习方法中性能突出的一种。这 种算法非常简单直观：给定一个文档，系统在训练集中找到与其最相近的 k 个样本，然后利用这些样本的类别属性来决定待分类文档的类别。将待分类文档和每个邻近的文档之间的相似度作为邻近文档的类别的权重。如果 k 个最近的样本中有几个都属于同一类别，则将他们的相似度叠加；权重相加后的结果作为该类别对应于待分类文档的可能性。通过对候选类别的权重进行排序，就获得待分类文档的候选类列表。同 法一样，通过设置权重的阈值，可以得到待分类文档的最终指派类别。 法则是找 K 个最近的邻居。因此它的分类响应时间要长于 法，计算复杂度和训练集中的文档数目成正比。不过， 法简单有效，所以在大型应用中获得广泛应用。 档分类算法的实现 本系统选用的文档分类算法是 K近邻算法。原因在于 K近邻算法是目前分类性能最好的算法之一，实现非常简单有效，不会过度影响网页的收集速度。该算法涉及到如下几个方面： 文档的表示 特征词的选取 计算待分类文档与训练集的相似度 决定（判定）待分类文档所属类别 档的向量表示 待分类的文档和训练集中的文档在分 类和训练时用何种形式表示是一个很实际的问题。 1969 年， 出了向量空间模型 是文档表示的一个统计模型，该模型以特征项（ 为文档表示的基本单位。 令 D 1d ， 2d ， ，示一组已分类完毕的文档集， C 1c ， 2c ， ，类别的集合。存在一个判断矩阵（ d 11 1 1 表示文档为 0 表示该文档不属于 文档初始集 D 被分为两个不相交的子集，即 ： 训练集 1d ， ，这是一个样本网页的集合，分类器用这个集合来分析出每个类别的特征。 测试集1 ，这一集合用于检验分类器的有效性。测试集中的每个文档都要送给分类器作测试，分类器根据由训练集分析出的每个类别的特征给测试文档指派一个类别。分类器的效果好坏由有多少的测试文档的类 别与前面描述的判断矩阵中对应的该文档的类别一致来衡量。 征集的选取 信息挖掘研究中提出词不仅能够很好的描绘文档的特征，而且它在文档中出现的顺序对多数工作的影响很小。这就为文档分类提供了良好的基础。每个不同的词对应文档的一个特征项，而该词在文中出现的次数设为它的权值。为了避免不必要大的特征空间，只有出现过较多次数和非“停词”（例如“和”、“或”）才会被选择为特征项。即便是这样，特征空间的维数仍然很容易超出 1 万。为了解决这个问题，数据挖掘技术中提出了很多方法减少特征向量的维数： 文档频率法（ 信息增容法（ 相互信息法（ 2 统计法 （ 相对信息法（ 鉴于本项目具有以下特点：给定一门课程，其内涵和外延一定是明确的（否则就很难称其为一门课程），因此在讲授该门课程的老师的帮助下，我们很容易在较短（一两天）时间内获得该课程的特征词。我们最终采用手工预先提取特征词的方法。 算待分类文档与训练集的相似度 通常人们选择一种距离作为度量两个文档相似程度的标准。由于文档是通过特征词权重的一维向量来描述的，设 X， Y 是两个具有相同特 征词的特征向量且X=（ .,21,）， Y=（ .,21 ,）。用 d(X,Y)表示文档特征向量 X 与 Y 之间的距离。我们选用欧氏距离函数作为度量标准，则 X， Y 间的相似度为： d ( X, 21yx 断待分类文档所属类别 设对应每个类m 个样本，则类和训练集中样本的对应情况如下： 1c 11s 12s ，令为 D 与样本相似度。事先给定一个阈值 ，令)(m dI co 文档 D 类 具体系统选择中学数学作为课程实例， 我们首先将中学数学分为如图表 3所示的九个类别。系统的分类目录，训练集，特征项空间等均用数据库中的表来描述： 表 录课程号，课程名称，课程中子类数和子类中的样本数 表 ：记录课程号，子类号，子类名称 表 录特征词和特征词 对照表 表 录训练集中每个样本的特征词权重 表 录网页信息数据库 的网页与分类 的对应关系，分别用 号、课程号和子类号表示 表 录每个课程子类的所有特征项 图表 3 分类目录 分类目录在数据库中用表 描述各类的内部结构。具体而言，“中学数学”对应课程名称，课程号为 1，其中的子类有 9个，每个子类中有 20 个样本，即分类集合 C 1c ， 2c ， ， m=9，训练集 1d ， ， g 180，对每个 i )1( ,20)*1( 到等于 1，其余的。 第四章 中文信息处理问题 文信息处理研究背景 在面向主题的搜索引擎的具体实现中，首先明确搜集和检索的对象是中文网页，因此中文信息的处理成为系统的一个关键因素。无论是在超文本文档自动分类的过程中，还是提供检索功能的索引数据库，都要求首先对中文文档做一定的预处 理，才能继续到下一步的工作。 文信息的特点 中文信息和英文信息有一个明显的差别：英语单词之间用空格分隔；而在中文文本中，词与词之间没有天然的分隔符，中文词汇大多是由两个或两个以上的汉字组成的，并且语句是连续书写的。这就要求在对中文文本进行自动分析前，先将整句切割成小的词汇单元，即汉语切词问题。用具体例子来说明，就是如何把“我的笔记本”这样连续书写的语句正确切分为“我”、“的”、“笔记本”的词汇单元。 文切词对系统的重要性 在检索和文档分类系统中，自动切词系统的速度直接影响整个 系统的效率。在第五次信息检索会议（ 增加了对中文分类系统的评测，而参加 中文信息的检索主要有两种：基于字的检索和基于词的检索。基于单字的检索系统对所有文章建立全文索引。在检索时得到每个单字的索引，而后加以适当的逻辑运算，得到检索结果。而基于词汇的检索系统对词汇建立索引，检索词汇时一次命中。本系统采用基于词的索引，具有较快的速度和较高的准确性，在查全率和查准率之间作出一定的权衡，同时能够减少索引信息对磁盘空间的占用。但是，这种检索方式要求 切词的准确率较高。 对于文档分类系统，构成向量空间的特征项主要是词，所以分词的准确率和速度与分类系统的准确率和速度密切相关。尤其是本系统中，文档的特征项多是数学专用词汇，因此中文切词软件要能够准确的切出所有在特征项集中出现的词汇。 文切词软件的基本原理 本系统采用北京大学计算语言所与北京大学中文系在语言信息处理领域内的合作研究成果 “汉语词语切分与词性标注软件”解决中文切词的问题。天网搜索引擎系统长期以来一直使用该软件，在分词准确性和速度方面都取得了比较满意的效果。 此 切词软件 将最稳定、最常用的 4 万 6 千余条现代汉语基本词汇及其有关属性组织 作 为基本词典 。 这些词的基本地位都是由汉语语言学家逐一检验认可的， 保证了该 系统 的 通用性；在此词典的基础上充分利用汉语构词法的研究成果，可以识别出大部分的常用词。 典的格式和数据结构表示 切词软件的字典的文件表示： 1 基础字典： 基础字典索引文件： 用户字典： 字列表： 标记列表： 重叠词文件： 有能形成 叠型的单字词 词表 有能形成 叠型的双字词词表 有能形成 B重叠型的双字词词表 有能形成 叠型的双字词词表。 7 前缀词： 缀信息表 8 后缀词： 缀信息表 9 特殊词： 和一些特殊后缀组合的词语表，其中收集的特殊后缀主要包括：“家”、“师”、“生”、“长”等。 基础字典、基础字典索引文件、字列表、标记列表的关系： 各个文件的格式： 基础字典： 词汇 标记 索引文件：如图 4 所示 字列表： 字 标记列表： 标记 图表 4 基础词典、索引文件 、标记列表和字列表关系图 注：灰色字体表示行号，在文件中不存在 图表 4 以基础字典中“斑”字打头的所有词为例，说明前文所提四者之间的对应关系。称一个字和以它打头的所有词为一个“结构单元”。结构单元中的数据的意义依次为： 93 代表“斑”字在字列表（字典）中的位置。 1、 6、 1、 1 分别表示词典中“斑”字打头的由 1、 2、 3、 4 个字组成的词的数量。 5 是“斑”字的标记号，查看标记列表可知是名词。 黑色字体的 数据是两个字组成的词的列表，依次是“斑点”、“斑痕”、“斑马”、“斑秃”、“斑纹”、“斑鸠”，其中“点”对应字列表中位置 532，“斑点”对应标记 5，已知是名词。其它的依此类推。 蓝色字体的数据是三个字组成的词的列表，其表示方法同两个字。 绿色字体的是四个字组成的词的列表，其表示方法同两个字。 基础字典的数据结构 首字列表： /存放两个字组成的词的结构，包括第二个字在字列表中的位置，/和词的标记 ; ; /存放首字在字列表中的位置 /指向两个字的词的列表 /指向三个字的词的列表 /指向四个字的词的列表 /结构单元的列表 /列表中数据项的总数 ; /存放以首字打头的 2、 3、 4 个字组成的词的个数 标记列表 * /标记列表 /标记列表中的标记总数 字列表 * /字列表（字典） /字列表中的汉字总数 切词软件初始化基础 词典时，调入内存的有 别是基础字典索引文件、字列表和标记列表，而 不真正调入内存中。在查找时，三个文件在内存中的信息进行对照，获得每个结构 单元的实际信息。 用户字典的数据结构 /存放用户字典中词汇和标记的结构 ; ; * /用户字典 *=0;*/ /用户字典中词的总数 /存放用户字典中首字信息的结构 ; /首字 /以首字打头的词第一次出现的位置 /以首字打头的词的总数 /以首字打头的词的最大长度 /* * /用户字典首字列表 /用户字典中首字的总数 注意：用户字典的格式同基础词典相同，但是数据结构表示却有较大的不同。 体切词过程 本 系统的处理过程包括自动切分和初始词性标记、切分歧义字段识别、组词和标注预处理、词性标记排歧、切分和词性标注后处理等过程 。 下图为切词过程 程序流程图： 图表 5 切词过程 先初始化变量，在 程进行真正的切词工作，是最重要的函数。它主要是通过查字典得到词汇的标记，根据标记的智能组合，切分出结果。切词结果记录在 组中，分别是词汇和标记。切分后要进行一系列的处理工作。 程主要处理前缀词，后缀词和叠词。如果 的某个标记含有歧义（例如：爱好 是名词 又是动词），要对 词性标记排歧 。 并所有连续 的 词性语素）和 容词性语素）。在新版本中， 加了合并一些特殊词汇的功能。例如：“一九九八年”在字典中不会出现，但是本函数会将起合并。最后，从 获取切词结果信息，存入 。调用 过程读取 为切词结果。 图表 6 进行真正的切词工作，循环调用 到整句 切分完毕。 查找用户和基础字典，获得词汇的标记，有可能获得多种切分可能性 果查找词汇在字典中只出现过一次则直接切分原句。具体切分的函数是 其中移动 针，指示 下次切分的起始点。如果查找词汇有多种切分可能性（ ），则调用数在 确定实际切分位置，并调用 图表 7 过查找字典确定切分的诸多可能性，但是并不真正进行切分工作。它主要由两步组成，一是查找用户字典，二是查找基础字典。找用户字典是否有待查找词汇的第一个字。如果有，就返回以该字打头的词的最长串的长度；否则返回 0。以 指的字为起始点，按照 1， 2， 3 到 回的最长串长度的顺序，依次查找对应长度的词在用户字典中是否出现。如果出现则在 且使切分可能性 1。查找基础词典是同一个过程。 以上是对计算语言所“汉语词语切分与词性标注软件”切词过程的一个粗略描述。其中，只涉及数据结构，程序流程等内容，不涉及歧义性的排除。 中文切词软件的修改 有两种方法可以加入新词。一种是修改天网和切词软件的接口，允许用户字典的加入。将所有的特征词加入用户字典，由系统在初始化的时候将其载入内存。这样，切词软件首先在用户字典中查找词，然后再查基础字典。另一种则直接修改基础字典。系统初始化时将用户字典的索引文件载入内存。修改基础字典，就要重新生成了一个索 引文件作为新词典，其中加入所有特征词，然后对原程序作出少量修改，使其能够顺利读取新词典。 我们选择了第二种方法，主要是考虑到将来扩充系统后，用户字典的增长可能会导致切词速度下降。另外，鉴于本系统的特殊性，很多词汇几乎不会在与中学数学相关的网页或者用户的查询请求中出现，可以去掉。这样，我们可以灵活方便地对字典文件进行增加、删除和修改。 第五章 网络搜集预测算法设计 文本链的相关研究 在搜集阶段，如何决定下一个要访问的网页是衡量主题搜索引擎性能的关键步骤。 网页与普通文档有一个标志性差别超 文本链，通过分析超文本链上的信息，可以获得整个网络的一个资源分布图。将每个网页都视为节点，其上的超链都看成一条由该节点到指向目标节点的有向边，就能获得整个 用它能大大提高搜集的目的性。 下面介绍两种典型地通过分析超文本链接信息对候选网页进行排序的方法： 法 法 7最早在网络搜索中对超文本链结构进行了分析利用，由此构成的 索引擎在商业上取得了巨大的成功。其具体算法是：给定一个 i，用 PR(i)来表示它的权值。 PR(i)用以下方程递归定义： PR(i) = dD(i) + (1 d) PR(j)/N(j, 其中， D 是所有网页上的一个概率分布； PR(j)/N(i 页的网页 j 上求和， N(j)是从 j 页上指出的链接总数； d 是 0 和 1 之间的一个常数。 法 区别于 网页价值的问题上 提出了更精确的主张。他认为网页的价值应该依赖于搜索的具体查询请求，每个网页都应该有独立的“ （ 基于指向该网页的链接）和“ （基于由该网页指出的链接）。 集合”，集合中包括和给定查询请求相关的一小部分网页。接着，用指向该集合中元素的网页和集合中元素所指向的网页扩充集合，成为一个“基本集合”。如果 ，其中 1表示从页 则 0。 a = (. . . , 示所有 h = (. . . , 表示 所有 始时， a和 u= (1, 1, . . . , 1)。 反复执行操作 I (“ ) 和 O (“ )。操作 I将 a = AT h， 操作 O将 h = A a。 每执行一次都要进行一步标准化，使向量 a和 证了在足够多的重复操作后，向量 a和 别收敛到矩阵 主特征向量 。上文提到的标准化步骤有很多种不同方法。无论采用哪种，像 ai/特征向量 ，即该特征向量对应过渡矩阵的最大特征值。 页搜集预测功能的设计 原来的天网搜集系统具有一定的网页预测能力，它主要通过配置导向词来引导系统优先访问从与导向词相关度较大的网页链接出的 导向词就是一组关键词，它们会引导搜索器按照一定顺序 搜索整个网络，使得搜索引擎可以在最短的时间里面得到最全面的与某一个主题相关的信息。通过设置导向词以及它们对应的不同权值，所有标题、作者、正文或超连接文本中含有某一导向词的网页都会被赋予较高的权值，在搜索的时候会优先考虑。搜索器在向主控程序获得时候也是按照权值由高到低的顺序。反之，搜索器在向主控程序提交新的 它的权值的时候，主控程序会按照权值预先排序，以便下一次有序的发给搜索器。 权值的设置有两种方法，第一种是根据管理员的经验手工设置，第二种是给定一个跟主题有关的网页集合，由程序自动提取这些网 页里面共同的特征，在这些网页里面都出现的很多的关键词，它就被选作导向词，即“特征提取”。原系统综合两种方法的优缺点，采用了两种方法的结合策略： 1 手工设置好一组导向词和它们对应的权值； 2 用这组导向词到原搜索引擎中查找出对应的网页； 3 按照权值的比例选取一