（计算机应用技术专业论文）基于文本分类的web信息检索技术的研究.pdf

摘要 摘要 随着i n t e m e t 的迅猛发展，搜索引擎已经成为人们处理w e b 信息、获取信息资源的 必备工具。传统的搜索引擎，即通用搜索引擎不能满足人们对个性化信息检索服务日益 增长的需要。近年来，基于文本分类技术的面向专题的搜索引擎应运而生，以提供分类 更细致精确的w e b 信息检索服务。 文本自动分类是指在给定的分类体系下，根据文本的内容自动判别文本类别的过 程。近年来，文本分类技术已经逐渐与搜索引擎、信息推送、信息过滤等信息处理技术 相结合，有效地提高了信息服务的质量。文本自动分类技术能够有效地将文本信息组织 管理起来，帮助人们准确高效的定位文本信息，为用户获取所需信息提供有力的支持。 文本分类的关键技术主要包括向文本表示模型、特征项赋权、特征选取、分类器构 建等，本文对这些技术作了详细介绍和深入分析。本文在向量空间模型基础上，通过针 对常用的特征权重计算方法t f i d f 的分析，提出了一种新的权值计算方法。该权值计 算方法将特征评估函数包含到特征权值计算中，按照特征对文本分类的辨别能力调整其 在权重计算中的贡献。 网页是一种超文本文档，其中含有文本信息和许多超文本标记等结构信息。本文通 过分析h t m l 标记对特征值权重的影响，在特征赋权方面，提出了结合t f i d f 与h t m l 标记分布信息的权重计算法。实验结果表明改进的权重计算法对分类精度有所提高。 本文介绍了l u c e n e 搜索架构以及l u c e n e 各个模块的组成和使用，利用开源的 l u c e n e 引擎架构设计一个搜索测试系统。 关键词：搜索引擎；文本分类；网络爬虫：l u e e n e 大连交通大学下学硕十学位论文 a b s t r a c t w i t ht h eb l o o m i n go fi n t e r a c ti n f o r m a t i o n ，t h ei n f o r m a t i o n - p r o c e s s i n gi sb e c o m i n ga n e c e s s a r yt o o lf o rp e o p l et oh a v ea c c e s st ou s e f u li n f o r m a t i o n t r a d i t i o n a ls e a r c he n g i n ec a n t m e e tt h ed e m a n dt h a tp e o p l ei n c r e a s i n g l yn e e dt h ec h a r a c t e r i s t i ci n f o r m a t i o ns e a r c hs e r v i c e t o p i c - o r i e n t e dt e x tc a t e g o r i z a t i o ns e a r c he n g i n ee m e r g e dw i t ht h et i d eo ft h et i m e sp r o v i d i n g t h em o r ep r e c i s es e a r c hs e r v i c ei nr e c e n ty e a r s t e x ti st h em a i ni n f o r m a t i o nc a r r i e ro ni n t e m e t t e x tc a t e g o r i z a t i o ni st h ek e yt e c h n i q u e t h a tt h e t o p i c o r i e n t e ds e a r c he n g i n e t e x ta u t o - c a t e g o r i z a t i o ns y s t e mc a no r g a n i z ea n d m a n a g et h et e x ti n f o r m a t i o na v a i l a b l y ，l o c a t i n gt h ei n f o r m a t i o na c c u r a t e l ya n dr a p i d l y ， s u p p o r t i n gt h ei n f o r m a t i o ne x t r a c t i n ge f f e c t i v e l y t h ep a p e rr e s e a r c h e si nd e t a i li n t ot h et e c h n o l o g yo ft e x tc l a s s i f i c a t i o nb a s e do nv e c t o r s p a c em o d e l t e r mw e i g h t i n g ，t e r ms e l e c t i o na n dc l a s s i f i e rc o n s t r u c t i o n ，t h ek e y so ft e x t c l a s s i f i c a t i o ns y s t e m ，a r ei n t r o d u c e da n da n a l y z e di nt h ep a p e r t h ep a p e rd i s c u s s e st h e t r a d i t i o n a ls y s t e ma l g o r i t h mo ft e r mw e i g h t i n g ：t f - i d f , t h ei n t r o d u c t i o no ff a c t o ri nt e r m w e i g h t i n gi sp r e s e n t e d i nf e a t u r es e l e c t i o n ，t h ep a p e ri n d i c a t e st h er e a s o nt h a tm u t u a l i n f o r m a t i o ns h o w sl o wp r e c i s i o ni nc l a s s i f i c a t i o na n dp r o p o s e st h ei m p r o v e da l g o r i t h m an e ww e i g h ta d j u s t m e n tm e t h o dw a sp r o p o s e dt h r o u g ha n a l y s i so ft f i d f b e c a u s et h e t f i d fm e t h o dc o u l dn o td e a lw i t hw o r d sw e i g h tp r o p e r l y ；t h en e wm e t h o di n t r o d u c e s f e a t u r ee v a l u a t i o nf u n c t i o ni nt h ef e a t u r ew e i g h tc o m p u t a t i o na n da d ju s t st h ef e a t u r e s c o n t r i b u t i o n t h e a c c u r a c yo fc a t e g o r i z a t i o n w a si m p r o v e d u s i n gt h e n e wm e t h o d e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ei m p r o v e da l g o r i t h m se x p e r i m e n t so u t p e r f o r m e dt h e t r a d i t i o n a lm e t h o d si nc l a s s i f i c a t i o np r e c i s i o n t h el u c e n ep a c k a g ea n do p e n s o u r c et o o l su s e db ys e a r c he n g i n et e s ts y s t e mh a v eb e e n i n t r o d u c e d t h e nt h r e eb a s i cc o m p o n e n t s ( c r a w l e r ，i n d e x e ra n d s e a r c h e r ) a r ei m p l e m e n t e db y j a v at e c h n o l o g y k e yw o r d s ：s e a r c he n g i n e ；t e x tc a t e g o r i z a t i o n ；s p i d e r ；l u c e n e i l 绪论 绪论 一课题研究背景 网络信息资源的指数增长，使搜索系统对网络信息的覆盖率在整体上呈下降趋势。 面对不同用户的需求，就是号称功能最强大的搜索系统，也无法跟上网络信息的增长速 度。尽管当前有些比较成熟的搜索系统，但是要达到准确、快速地查找所需信息的目的 还是有很多困难，这是由于以下几方面的原因： ( 1 ) 由于自然语言的歧义性，一个关键字可以出现在多个不同的信息领域中，并有 不同的意义，基于这个关键字的检索就会将所有涉及这个关键字的页面均返回给用 户，检索精度低。一次搜索的结果可能有成千上万条，而在这过于庞大的信息群 中，有用信息只是其中的小部分，检索结果中出现大量冗余信息。 ( 2 ) 目前的搜索系统都是服务器端软件，用户需要严格按照各搜索系统所要求的格 式输入查询词，种种限制使用户不知道如何确切地表达自己的信息需求，也不知道 如何更准确地寻找所需信息。经典的信息检索界认为用户很难简单地用关键字来 忠实表达他所真正需要检索的内容，表达的困难将导致检索结果的不理想，而且如何将 结果表达成用户容易理解和使用的方式也是一个难题。 ( 3 ) w e b 信息资源的动态变化，搜索引擎无法保证对信息的及时更新；传统的搜索引 擎不能满足人们对个性化信息检索服务的日益增长的需要。网络信息的急剧膨胀， 使检索难以控制，用户需求和服务问的巨大反差产生了强大的检索障碍。 ( 4 ) 搜索引擎一般不会遗漏较重要的网站，但由于对网站的描述较为简单，不能深 入到网站的内部标引。对各个站点的标引仅是以宽度优先，而深度不足，常常导致相关 的信息被漏搜。 面对这些挑战，各种适应特定人群需要的搜索工具应运而生并引起了研究者的重 视。以何种策略访问w e b ，以提高搜索效率，成为近年来专业搜索引擎研究的主要问题 之一。专业化的搜索引擎的优势在于，针对性强，对特定范围的网络信息的覆盖率相对 较高，具有信息资源保障，有明确的检索目标定位，有效地弥补了综合性搜索引擎对专 门领域及特定主题信息覆盖率过低的问题。同时，能够把具有相同兴趣点的人们集中在 主题范围内，集中提供各种针对性的资源。 文本分类作为信息处理的重要研究方向，无疑是处理文本信息的有效途径。通过文 本分类系统，信息可以得到有效的组织管理，这样就有利于快速准确的定位信息，具体 体现为信息查洵时间、组织和过滤时间、阅读时间的减少，从而使用户快速地获取信息 成为可能。文本分类最初是应信息检索( i n f o r m a t i o nr e t r i e v a l ，简称i r ) 系统的要求出现 大连交通人学f ：学硕十学位论文 的，通过分类对文本集进行有序组织，把相似的、相关的文本组织在一起。文本分类作 为知识的组织工具，为信息检索提供了更高效的搜索策略和更准确的查询结果。其中， 高效来自于用户可以首先确定查询的可能类别，减小需进一步匹配的文本数量。有效性 在于相似的文本很可能与相同的查询相关。这样，检索的查全率和准确率都得到了提高。 文本分类技术可以被看作是所有基于内容的文本信息管理的基础，由此可以看出文本分 类技术在信息处理领域的重要性。 二本文的意义及主要工作 基于文本分类的信息检索服务能够根据用户个人独特的信息需求，在特定的专题类 别范围内，从w e b 上搜索相关的信息，并将它们整合在一起，有针对性地满足不同用 户的信息需求。 本文做了如下工作： ( 1 ) 系统介绍了搜索引擎的相关概念、发展历程；分析了搜索引擎的体系结构，总 体上描述了搜索引擎的主要组成部分：s p i d e r ，索引部分，检索部分。 ( 2 ) 介绍了文本自动分类的相关技术；通过对常用的特征权重计算方法t f i d f 的分 析，提出了一种新的权值计算方法。该权值计算方法将特征评估函数包含到特征权值计 算中，按照特征对文本分类的辨别能力调整其在权重计算中的贡献。， ( 3 ) 通过h t m l 标记对特征值权重的影响的分析，在特征赋权方面，提出了结合 t f i d f 与h t m l 标记分布信息的改进权重计算法。实验结果表明改进的权重计算法对 分类精度有所提高。 ( 4 ) 介绍了l u c e n e 的原理和特点，l u c e n e 搜索架构的各个模块。 ( 5 ) 利用l u c e n e 搜索架构构建了一个分类搜索测试系统。 2 筇一章搜索引擎概述 1 1 信息检索技术 第一章搜索引擎概述 1 1 1 信息检索的概念 信息检索( i n f o r m a t i o nr e t r i e v a l ) 是从结构化的文档集中找出与用户需求相关的信 息，与数据库系统不同，信息检索主要研究的不是结构数据的查询和事务处理问题，而 是研究大量文本文档的信息组织和检索【l j 。它处理的对象是非结构化数据，主要有文本 数据、网页、多媒体数据。典型的信息检索问题是基于用户的输入定位相关的文档，典 型的信息检索系统有联机图书馆目录系统和联机文档管理系统。 传统i r 技术研究信息的表示、存储、组织、查询。通常处理的是文本信息，用于 从一定规模的文档库中获取用户需要的信息，其核心是文本信息的索引和检索。从历史 上看，信息检索经历了手工检索、计算机检索到目前网络化、智能化检索等多个发展阶 段。 虽然信息检索的主要任务是对大量数据进行处理，但不能简单认为信息检索 ( i n f o r m a t i o nr e t r i e v a l ) 就是数据检索( d a t ar e t r i e v a l ) t 引，这两种检索方式的要求是有区别 的。数据检索要求查询结果必须精确无误，即返回与查询准确匹配的结果。可以这样假 设：只要数据库不改变，对于不同的人在不同时间提交的相同查询，其返回结果应该是 一样的。然而，信息检索就不同了，它的检索结果可以是不精确的。形成这两种不同检 索方式的主要原因是信息检索通常处理自然语言文本，自然语言的特点就是没有良好的 组织结构，而且语义上比较模糊，而数据检索处理的是具有结构化，语义明确等特点的 数据( 如关系数据库) 。 信息检索系统的目的是检索到与查询相关的所有文档，同时尽可能少地检索到无关 文档，即系统对用户提交查询后所返回的结果信息要充分满足用户的需求。然而，要实 现这样的检索目的，一是需要用户提供一系列能传递信息所含语义的词汇；二是信息检 索系统必须找到一种方法解析查询信息包含的内容，同时把文档表示成一组关键词或是 索引词条，以方便信息检索时抽取信息，并根据与用户查询的相关程度来排列这些结果 信息。 1 1 2 信息检索系统模型 根据查找相关信息的实现方式不同，常见的信息检索引擎有布尔逻辑模型、模糊逻 辑模型、向量空间模型和概率检索模型等几类1 4 1 。 火连交通人学下学硕十学侮论文 ( 1 ) 布尔逻辑模型 布尔逻辑模型是最简单的检索模型，也是其他检索模型的基础。用户根据所检索关 键字在检索结果中的逻辑关系递交查询，查询模块根据布尔逻辑的基本运算法则来给出 查询结果。布尔检索模型原理简单易理解，容易在计算机上实现并且具有检索速度快的 优点。但是最终给出的查询结果没有相关性排序，不能全面反映用户的需求，功能不如 其他的检索模型。 ( 2 ) 模糊逻辑模型 模糊逻辑模型以模糊数学作为理论基础，设置单个的检索词w 在文档d 中的隶属 度u ，u 【0 ，1 】，u 越大代表w 和文档d 的相关性越高。用户给出查询要求，查询模块 根据模糊逻辑运算给出查询的结果，并能够按照相关度排序。模糊逻辑模型能够克服布 尔逻辑模型检索结果的无序性，但是给查询词设置准确的隶属度有一定困难。 ( 3 ) 向量空间模型 根据文档之间的相似度，结合机器学习的一些算法如神经网络算法，k 一近邻算法 和贝叶斯分类算法等，可以将文档集分类划分为一些小的文档子集。在查询过程中，可 以计算出每个文档与查询的相似度，进而可以根据相似度的大小，将查询的结果进行排 序。 向量空间模型可以实现文档的自动分类和对查询结果的相似度排序，能够有效提高 检索效率；它的缺点是相似度的计算量大，当有新文档加入时，则必须重新计算词的权 值。 ( 4 ) 概率检索模型 概率检索模型是在布尔逻辑模型的基础上为解决检索中存在的一些不确定性而引 入的。概率检索模型有多种形式，常见的为第二概率检索模型，首先设定标引词的概率 值，一般是对检索作业重复若干次，每一次检索用户对检出文档进行相关性判断。再利 用这种反馈信息，根据每个词在相关文档集合和无关文档集合的分布情况来计算它们的 相关概率。 概率模型有严格的数学理论基础，采用了相关反馈原理克服不确定性推理的缺点， 它的缺点是参数估计的难度比较大，文件和查询的表达也比较困难。 1 1 3 信息检索系统的处理过程 在使用信息检索系统前，i r 系统先对收集的文档建立索引。用户通过系统的查询接 口输入查询条件；系统对查询条件进行词干抽取、词义转换等一系列步骤生成系统内部 使用的检索关键字：通过索引获取检索结果集。在检索过程中，系统对检索文档进行匹 4 第一章搜索引擎概述 配计分，检索完成后，系统根据计分值对检索结果集中文档排序，将最终结果返回给用 户完成整个检索过程。有些i r 系统还提供了用户反馈机制来提高检索相关度。 1 2 搜索引擎简介 搜索引擎技术是由信息检索( i n f o r m a t i o nr e t r i e v a l ) 技术发展而来，是i r ( i n f o r m a t i o n r e t r i e v a l ) 技术在w e b 上的扩展。 1 2 1w e b 信息资源的特点 随着i n t e m e t 的发展，网络信息资源急剧增长。与传统信息资源相比，网络信息资 源在数量、结构、内涵、类型、载体形态、分布和传播范围、控制机制、传递手段等方 面都呈现出许多新的特点【5 】： ( 1 ) 分布广、传播快、数量大、增长快 随着网络覆盖范围的不断扩大以及网络技术的发展，存在于网络上的信息资源飞速 传播并迅速增长。由于i n t e m e t 的广泛性和开放性，在因特网上发布信息极为容易而且 不受限制，只要具备上网条件便可自由地发布信息，大大加剧了因特网信息量的急剧膨 胀。 ( 2 ) 多类型、多媒体 数量巨大的网络信息资源来源于各行各业，包括不同学科、不同领域、不同地区、 不同语言的各种信息，其内容是非常丰富的，并且以文本、图像、音频、视频、数据库 等多种形式存在。 ( 3 ) 无序性、不稳定 互联网是开放性的，通过t c p i p 将不同的网络连接起来，对网络信息资源的组织 管理并无统一的标准和规范。同时信息的地址、连接及内容本身处于经常变动之中，使 得信息资源的更迭、消亡无法预测。因此，整个网上信息资源目前状态都是无序、不稳 定的。 ( 4 ) 信息质量良莠不齐 网络信息分布具有很大的自由度和随意性，缺少质量控制和管理机制，使得网络信 息繁杂、混乱，质量良莠不齐，安全存在隐患，给用户选择、利用网络资源带来了障碍。 1 2 2 搜索引擎的发展历史 1 9 9 3 年，i n t e r n e t 上出现了最早的w 曲浏览器m o s a i c ，次年n e t s c a p e 推出了 n a v i g a t o r ，浏览器的发展促使w e b 得到迅速推广，同时也推动着搜索引擎的发展【1 2 】。 1 9 9 4 年春天出现了最早的真正意义上的搜索引擎l y c o s 。当时m i c h a e lm a u l d i n 大连交通人学i ：学硕十学位论文 将j o h nl e a v i t t 的s p i d e r 程序接入到其索引程序中，实现网页的自动发现和索引。随 后，i n f o s e e k 和e x i t e l 6 也相继出现。这些搜索引擎主要出于研究目的，解决的主要问题是 “查全率 。它们般都索引少于1 0 0 万个网页，响应时间都在1 0 秒以上。我们称之为 第o 代搜索引擎。 1 9 9 6 年出现了第1 代搜索引擎。这些搜索引擎一般每天能够接受1 0 0 0 万次检索， 并且能够索引大约5 0 0 0 万网页。这一代搜索引擎的代表是a l t a v i s t a 和i n k t o m i 。它们的 实现方法大不相同。a l t a v i s t a 采用大型的多处理器计算机来支持搜索引擎的运转；而 l n k t o m i 则采用分布式方案来解决搜索引擎对计算能力的要求。 大约到了1 9 9 8 年，出现了第2 代搜索引擎。此时，搜索引擎技术得到了空前的发 展，这个时期搜索引擎发展的主要特点有： ( 1 ) 开始出现了主题搜索和地域搜索，很多小型的垂直门户站点开始使用这些技术； ( 2 ) 随着大型多处理器计算机以及分布式技术的应用，搜索引擎搜集、索引网页的 能力得到空前的提高。这个时期的搜索引擎都试图收集“整个w 曲”。“查全率”问题已 不是主要矛盾。但是随着索引网页规模的扩大，检索结果的准确性成了主要问题。检索 结果相关度评价或“查准率”问题成为研究的焦点。其典型代表为g o o g l e 和i n k t o m i 。 相关的研究又可以分为两类：一类是对超文本链的分析，在这方面s t a n f o r d 大学的g o o g l e 系统和i b m 的c l e v e r 系统做出了很大的贡献；另一类是用户信息的反馈，d i r e c t h i t 系 统采用的就是这种方法。 1 2 3 搜索引擎的分类 搜索引擎按其工作方式主要可分为三种，分别是全文搜索引擎( f u l lt e x ts e a r c h e n g i n e ) 、分类目录搜索引擎( s e a r c hi n d e x d i r e c t o r y ) 和元搜索引擎( m e t as e a r c he n g i n e ) 。 ( 1 ) 全文搜索引擎 全文搜索引擎把w e b 看作一个大规模的全文数据库，一张网页对应多个关键词， 采用关键词匹配进行信息检索。通常利用网络爬虫提取各个网站的信息( 以网页文字为 主) ，把提取到的网页存入数据库中，并进行索引及相关性分析；查询时，把查询条件 与索引记录进行匹配，然后按一定的排列顺序把结果返回给用户。这类搜索引擎的优点 是信息量大，更新及时，不需人工干预；缺点是信息准确率不高。 国外具代表性的全文搜索引擎有g o o g l e 、f a s t a l lt h ew e b 、a l t av i s t a 、i n k t o m i 、 t e o m a 、w i s e n u t 等，国内著名的有百度( b a i d u ) 。 ( 2 ) 分类目录搜索引擎 分类目录搜索引擎以人工或半自动方式搜集信息，由编辑人员编写信息摘要，并将 6 第一章搜索引擎概述 信息置于预先确定的分类框架中，用户逐层浏览目录寻找需要的信息。主要的分类目录 搜索引擎有y a h o o ，l o o ks m a r t 等1 7 l 。这类搜索引擎采用人工分类和摘要，因而准确率很 高。它有着目录结构清晰、内容准确的突出优势，尤其适用于那些希望了解某一方面信 息而不希望通过关键字进行检索的用户。但人工操作的速度慢、分类体系不规范、交叉 类内容易遗漏、更新不及时、处理的信息量也少。 ( 3 ) 元搜索引擎( m e t as e a r c he n g i n e ) 这类搜索引擎没有自己的数据库，而是把用户的查询请求同时向多个搜索引擎提 交，同时在其他多个引擎上进行搜索，将返回的结果进行去除重复、重新排序等处理后， 将结果返回给用户。这一类搜索引擎返回的结果信息量更大，更全，缺点是不能充分利 用所使用的搜索引擎的功能。著名的元搜索引擎有i n f o s p a c e 、d o g p i l e 、v i v i s i m o 等( 元 搜索引擎列表) ，在搜索结果排列方面，有的直接按来源引擎排列搜索结果，如d o g p i l e ， 有的则按自定的规则将结果重新排列组合，如v i v i s i m o 。 这三类搜索引擎中，元搜索引擎是基于第1 类和第2 类搜索引擎的。第一类搜索引 擎( 基于r o b o t 的搜索引擎) 与第二类搜索引擎( 目录式搜索引擎) 相比有如下特点： ( 1 ) 基于r o b o t 的搜索引擎自动收集、分析和处理网页，因而它索引的网页数多， 信息量大，并且能够定期重新收集网页，更新索引库的内容，向用户提供最新的w e b 网页信息。但是它只提供基于关键词的检索，用户只有确切的知道自己感兴趣的网页含 有哪些关键词时，查询的效果才比较理想。否则，返回的结果很可能和用户的实际需求 不相关。 ( 2 ) 目录式搜索引擎支持基于分类目录的查询。目录式搜索引擎对收集的网页采用 人工分类。由于这种人工方式对网页内容的理解比较准确，因此查询的准确性优于s p i d e r 式搜索引擎。当用户对某个领域感兴趣但并不熟悉这个领域的关键词时，这种查询方式 能为用户提供更好的服务。由于人工分类效率低，网页更新困难，目录式搜索引擎在索 引的网页的规模上受到了很大的限制。当g o o g l e 等s p i d e r 式搜索引擎索引的网页数量 早以突破十亿级时，y a h o o 还停留在千万级的水平。 由于目录式搜索引擎完全采用人工进行网页的搜集和分类，其网页规模和更新速度 与i n t e m e t 的网页总量和网页更新速度相差太远，其涵盖的范围无法满足用户的需要， 已经逐渐被基于r o b o t 的搜索引擎代替。同时，基于r o b o t 的搜索引擎在用户的抱怨声 中不断成长，不断改进检索质量，目前已经成为w e b 用户发现网上信息必不可少的工 具。 7 大连交通人学f ：学硕十学位论文 本章小结 在本章中，主要介绍了信息检索和搜索引擎的基本概念。搜索引擎技术随着互联网 的发展的主要历程，以及搜索引擎为满足不同用户的需要而采用不同技术。 8 第二章搜索引擎相关技术 第二章搜索引擎相关技术 2 1 搜索引擎的体系结构 搜索引擎一般由以下三个模块组成：信息采集模块( s p i d e r ) ，索引模块( i n d e x e r ) 、查 询模块( s e a r c h e r ) 。如图2 1 所示： 用 索 寻 检 _ 户 ：j i 引 索i 一 - i p 接 ：7 器器 ；用户 口 图2 1 搜索引擎体系结构 f i g 2 1t h es t r u c t u r eo fs e a r c he n g i n e 对应地，搜索引擎的主要三个模块： ( 1 ) s p i d e r ( 也常称作r o b o t ，c r a w l e r ) 从w e b 中采集网页数据； ( 2 ) i n d e x e r 索引器对s p i d e r 采集的数据进行分析生成索引： ( 3 ) s e a r c h e r 检索器接受用户查询请求，通过一定的检索算法获取查询结果，排序后 返回给用户。 搜索引擎的搜索过程简单描述如下： 首先需要获取网页信息数据，构造文本数据库，即将来需要进行检索的数据。在有 了文本数据之后，需要建立文档的索引。利用索引技术可以大大提高信息检索的速度。 当前有很多种建立文档索引的方法，然而对于大规模的数据量来讲，用得最多的还是倒 排索引技术。在建立好索引之后，就可以对其进行检索了。在检索过程中，用户首先给 出一个查询，该查询将被分析，然后利用文本处理技术进行处理。在查询操作进行之前 还町以对其进行一些预处理。最后根据用户的查询将获取一些文档，这就是检索结果。 在把检索结果反馈给用户之前，对检索结果按照一定的次序排序，以使最符合用户需要 的文档能够排在更前面。 9 人连交通人学t 学硕_ f j 学位论文 2 2s p i d e r 概述 s p i d e r 负责页面信息的采集，它的工作实现基于以下设想；既然所有网页都可能链 接到其他网站，那么从一个网站开始，扫描网页上的所有链接，就有可能检索整个互联 网。 2 2 1 网页的基本结构 为了有效地剔除网页中的噪音信息，得到有用内容，首先要了解网页的基本结构和 特点。目前普遍使用h t m l 语言作为创建w e b 页面的语言。h t m l 全名是超文本标识 语言( h y p e rt e x tm a r k u pl a n g u a g e ) 3 1 。从形式上看，h t m l 文件是标准的a s c i i 文件， 与普通文本不同的是，它加入了很多h t m l 标签，这些标签对应于h t m l 语言中的不 同元素( e l e m e n t ) ，用于组织文件的内容和指导文件的输出格式。绝大多数元素是“容器 ， 即它有起始标记和结尾标记。在起始链接签和结尾链接签中间的部分是元素体。h t m l 标签经常是嵌套关系，比如h t m l 标签的元素体部分又包含h e a d 和b o d y 标签，而h e a d 标签的元素体部分又包含t i t l e 标签。实际上，一个规范的w e b 页面的代码往往对应于 一颗树型结构，h t m l 标签为树根，各个不含任何标签的文本块成为该树形的各个叶节点。 标记有三类意义：结构、语义和样式。结构将文档组织成树型结构；语义将单个的元素 与外部的实际事物联系起来；而样式指定如何显示元素。 s p i d e r 程序通过分析网页的h t m l 代码，查找网页内所有链接到其他网页的标签， 来达到从一个网页移动到另一个网页的目的。网页中多数链接使用的是h r e f ( h y p e r t e x t r e f e r e n c e ，超文本链接) 的特殊类型的属性来完成的。 w 曲超文本链接的类型1 9 1 ： ( 1 ) 内部链接( i n t e m a ll i n k ) ： 务器中； ( 2 ) 外部链接( e x t e r n a ll i n k ) ： 站点不同； 链接所指向的网页与包含该链接网页在同一台w e b 服 链接指向的网页所在的w e b 站点与包含该链接的w e b ( 3 ) 其他链接( o t h e rl i n k ) ：指向非网页的资源链接。 2 2 2 网络爬虫s p i d e r 的结构及处理流程 构造s p i d e r 程序一般有递归和非递归两种方式。由于递归方式下，s p i d e r 程序不能 使用多线程，并且递归程序在运行时需要耗费大量的堆栈内存，当处理数以亿计的网页 时最终会很快耗尽整个内存并终止程序的运行。因此，只有在访问相当少的网页时，递 归方式的s p i d e r 才是合适的。 1 0 第二章搜索引擎相关技术 非递归方式的s p i d e r 是通过使用队列来实现的。 s p i d e r 的队n - ( 1 ) 等待队列：新发现的u r l 被加入到这个队列，等待被s p i d e r 程序处理。 ( 2 ) 处理队列：要被处理的u r l 被传送到这个队列。为了避免同一个u r l 被多次处 理，当一个u r l 被处理过后，它将被转移到完成队列或者错误队列( 如果发生错误) 。 ( 3 ) 错误队列：如果在下载网页是发生错误，该u r l 将被加入到错误队列。 ( 4 ) 完成队列：如果在处理网页是没有发生错误，该u r l 将被加入到完成队列。 图2 2u r l 状态流程图 f i g 2 2f l o wo fu r ls t a t u s 同一时间一个u r l 只能在一个队列中，图2 2 描述了u r l 状态如何从一个状态转 换到另一状态。 在图2 3 描述了在不出现错误时的s p i d e r 队列处理过程。 在等待队列中，u r l 等待被s p i d e r 进行处理，新发现的u r l 被加入到个队列中； 当s p i d e r 开始处理某个网页的u r l 时，这个u r l 就被送到运行队列中进行处理；如果 s p i d e r 在抓获某个网页时出错，那么这个网页的u r l 将被送到错误队列，错误队列中 的u r l 不能被移入到其他队列中；如果s p i d e r 成功的获取某个网页，那么这个网页的 u r l 将被送到完成队列，完成队列中的u r l 不能被移入到其他队列中。如果新发现的 链接不是指向当前正在遍历的网站的网页时，这个u r l 就被送到外部类型链接队列中， 外部链接队列中的u r l 不能被移入到其他队列中。 新发现的u r l 通过u r l 状态判断模块依次在这几个队列中查询是否该u r l 已经 存在。如果队列中不包含该u r l ，则继续判断该页面是否属于本网站：如果属于本网站， 则将其放入等待队列中，否则放入外部链接队列。在实际使用时，如果是简单的使用线 性队列结构，则需要在每次判断时都要在所有队列中对每个u r l 顺序地进行字符串比 较。随着遍历过程的不断深入，队列中的u r l 的总数不断增多，这个判断比较的过程 所消耗的时间也会不断增加。因此实际上可以采取散列表( h a s ht a b l e ) 或排序树( s o r tt r e e ) 大连交通人学i ：学硕十学位论文 这样的数据结构来存储u r l 。 2 3i n d e x e r 分析 图2 3s p i d e r 程序流程图 f i g 2 3f l o wo fs p i d e rp r o c e d u r e 索引是在搜索时使用到的一种特殊的数据结构。当文档的数量相当庞大，并且这些 文档中的信息相对稳定时，建立索引可以大大提高搜索时的效率。不过，这种索引结构 不支持快速的信息更新，即当建立完成索引后，如果文档中的信息发生了变化，也必须 对索引进行更新，才能够使用索引检索到最新的信息。 索引器的功能是理解搜索器所搜集的信息，从中抽取出索引项，用于表示文档以及 1 2 第二章搜索引擎相关技术 生成文档库的索引表。索引项有客观索引项和内容索引项两种：客观项是与文档的语意 内容无关，如u r l 、更新时间、编码、长度、链接流行度( l i n kp o p u l a r i t y ) 等；内容索引 项是用来反映文档内容的，如关键词及其权重、短语、词、字等。内容索引项可以分为 单索引项和多索引项( 也叫短语索引项) 两种。单索引项对于英文来讲是英语单词，比较 容易提取，因为单词之间有天然的分隔符( 空格) ；对于中文等连续书写的语言，必须采 用多索引项，进行词语的切分。索引器可以使用集中式索引算法或分布式索引算法。当 数据量很大时，必须实现实时索弓l ( r e a l t i m ei n d e x i n g ，否则就跟不上信息量急剧增加的 速度。索引算法对索引器的性能( 如大规模峰值查询时的响应速度) 有很大的影响。一个 搜索引擎的有效性在很大程度取决于索引的质量。 为了加快检索速度，搜索引擎要对抓取模块搜集到的信息建立索引。在建立索引时， 需要考虑一些问题，比如是建立全文索引还是部分索引，有些搜索引擎对于信息库中的 信息建立全文索引，有些只建立摘要部分索引或者每个段落前面部分的索引。还有些搜 索引擎在建立索引时，要同时考虑超文本的不同标记所表示的含义，如粗体、大字体显 示的东西往往比较重要。有些搜索引擎还在建立索引的过程中收集页面中的超链接，这 些超链接反映了收集到的信息之间的空问结构，利用这些结果信息可以提高页面相关度 判别时的准确度。还有是否过滤无用词，由于网页中存在这许多无用( 无实际意义) 单词。 这此词往往不能明确表达该网页信息，所以有些搜索引擎保存一个无用词汇表，在建立 索引时将不对这些词汇建立索引。 在使用索引进行查找时，首先对需要索引的文档进行预处理，建立关于这些文档的 索引结构。索引的技术主要有以下3 种：倒排索引，后缀数组和签名文件。其中，倒排 索引技术在当前大多数的信息检索系统中得到了广泛的应用，对于大规模文档数据，倒 排文件是经过大量实践检验的一种高效率的索引组织方式，能够很好的支持多种检索模 型，提供高性能的检索。后缀数组技术在短语查询中具有很快的速度，但是这样的数据 结构在构造和维护时都比较复杂一些。签名文档技术在2 0 世纪8 0 年代时期比较流行， 但是后来倒排索引技术逐渐超越了它。 对一个中文搜索引擎，索引创建不仅仅是一个高效的倒排算法，它还包含许多重要 的方面：索引词的选择，中文分词、编码识别与转换、网页净化、强健的页面分析等。 索引词的选择是检索系统实现的一个重要环节。搜索引擎普遍使用全文索引技术， 即网页文档中所有词都参与索引。理想的索引词应该是表达文档内容的语义单位，即语 言学里的词语，是那些专指义而实际意义无法由组合成分相加得到的最小语言单位。但 实际系统中中文文本必须通过自动分词程序的处理，分割成为独立的分词单位，再从分 词结果中选择索引词。自动分词算法有两大类，普遍采用的方式是基于词典的分词方法， 1 3 大连交通大学一i ：学硕十学位论文 这一方法效率高，但分词精度受词典规模制约；另一种是基于统计语言模型的方法，可 以发现一些新词。实际应用是两种方法的不同程度的组合。 对索引网页库信息进行预处理包括网页分析和建立倒排文件索引两个部分。中文自 动分词是网页分析的前提。文档由被称作特征项的索引词( 词或者字) 组成，网页分析是 将一个文档表示为特征项的过程。 分析网页和建立倒排文件二者是顺序进行，先分析网页，后建立倒排索引文件( 也 称为反向索引) ，如图2 4 所示。 过滤 切分倒排 网页正文信息 正向索引反向索引 图2 4 倒排索引文件建立流程 f i g 2 4t h ep r o c e s so fb u i l d i n gr e v e r s ei n d e x 分析网页过程包括提取正文信息( 指过滤网页标签，s c r i p t s ，c s s ，c o m m e n t s 等信息) 和把正文信息切分为索引词两个阶段。形成的结果是文档号到索引词的对应关系表。每 条记录中包括文档编号，索引词编号，索引词在文档中的位置信息，索引词载体信息。 得到网页正文信息，调用切词模块，获得正向索引。 创建倒排索引j 包括建立正向索引和反向索引。分析完网页后，得到以网页编号为 主键的正向索引表。反向索引的建立是一个表的重组的过程，为了加快速度，全过程需 要在内存中完成。在小数据量时，有足够的内存保证该创建过程一次完成。数据规模增 大后，可以采用分组索引，然后再归并索引的策略。该策略是，建立索引的模块根据当 时运行系统所在的计算机的内存大小，将索引分为n 组，使得每组运算所需内存都小于 系统能够提供的最大使用内存的大小。按照倒排索引的生成算法，生成n 组倒排索引。 然后将这n 组索引归并，即将相同索引词对应的数据合并到一起，就得到了以索引词为 主键的最终的倒排文件索引，即反向索引。 2 4s e a r c h e r 中的关键问题 ( 1 ) 检索结果的排序 由于搜索引擎返回结果非常多，检索结果是否按用户预期的顺序排列是评价搜索引 擎的重要指标之一。一些新的尝试，比如对用户偏好的分析技术如个性化搜索等都可以 运用在这里，对不同偏好的用户采用不同的排序策略。 ( 2 ) 检索结果的排重 1 4 第二章搜索引擎相关技术 检索结果的排重能提高结果数据的质量。检索结果的数量给排重带来资源上的开销 及速度上的影响。搜索引擎需要在其中做出权衡。 ( 3 ) 检索结果的相似性分析 主要用在类似网页功能中，需要在索引结构中提供支持。 ( 4 ) 检索的速度 主要依赖索引结构的设计。同时在体系结构上还有很多技术可以用来提升速度。如 c a c h e 、负载均衡等。 2 5 中文自动分词 中文信息的检索主要有两种：基于字的检索和基于词的检索【2 0 1 。基于单字的检索系 统建立单字索引。在检索时得到每个单字的索引，而后加以适当的逻辑运算，得到检索 结果。而基于词汇的检索系统对词汇建立索引，检索词汇时一次命中。基于词的索引， 具有较快的速度和较高的准确性，同时能够减少索引信息对磁盘空间的占用。 中文自动分词1 2 3 j 是网页分析的基础，在检索和文档分类系统中，中文自动分词系统 的速度直接影响整个系统的效率。在网页分析的过程中，中文与英文的处理方式是不同 的，这是因为中文信息与英文信息有一个明显的差别：英文单词之间有空格，而中文文 本中词与词之间没有分割符。这就要求在对中文网页进行分析之前，先要将网页中的句 子切割成一个个的词的序列，这就是中文分词。中文自动分词涉及到许多自然语言处理 技术和评价标准，在搜索引擎中，我们主要关心中文自动分词的速度和准确度。分词准 确性对搜索引擎来说十分重要，但如果分词速度太慢，即使准确性再高，对于搜索引擎 来说也是不可用的，因为搜索引擎需要处理数以亿计的网页，如果分词耗用的时间过长， 会严重影响搜索引擎内容更新的速度。因此，搜索引擎对分词的准确性和速度都提出了 很高的要求。 目前，中文自动分词比较成熟的技术是基于分词词典的机械分词方法。这种方法是 按照一定的策略将要分析的汉字串与词典中的词条进行匹配。根据匹配策略的不同，机 械分词方法又有如下几种算法：正向最大匹配算法、逆向最大匹配算法、最少分词算法 等