（计算机应用技术专业论文）垂直搜索引擎若干关键技术的研究.pdf

浙江大学硕士学位论文 摘要 摘要 随着i n t e m e t 的飞速发展，w 曲的信息量越来越大，通用搜索引擎将面临信 息采集、存储等方面更大的挑战。此外，由于通用搜索引擎面向所有的用户，力 争在返回结果上做到面面俱到，包罗万象的结果显然不能满足用户精确搜索的需 求。因此，面向专业领域的搜索引擎即垂直搜索引擎应运而生。 与通用搜索引擎不唰，垂直搜索引擎的网络蜘蛛只采集w 曲中的部分信息。 通过对网页的主题相关度进行预测和判断，专业网络蜘蛛在爬行( c r a w l i n g ) 时 避开了大量主题无关的区域。由于只采集主题相关的网页，垂直搜索引擎在套询 的准确率和效率上都有显著的提高。目前，垂直搜索引擎的中文分词和主题预测 有待进一步提高精度，网络蜘蛛的搜索策略也有待进一步改进以提高搜索引擎的 覆盖率和效率。 本文提出了基于主题的自适应的分词技术，使用候选词典和专业词库来指导 分词和歧义消除，能有效地提高专业领域中分词的查全率和查准率。 本文还提出了基于父网页的主题相关度预测算法( c p a p ) 、基于链入网页的 主题相关度预测算法( c p a h ) 和t p r 主题预测算法。c p a p 利用了锚文本和父 网页的主题相关度等信息进行预测；c p a h 在预测主题相关度时综合考虑了链接 的数量和质量；t p r 算法则将网页的主题相关性和权威性相结合，从而有效地防 止了“主题漂流”现象。 为了解决普通隧道技术随着探索半径的增大，主题无关网页呈指数级增加的 问题，本文提出了稀疏隧道技术，稀疏隧道技术使专业网络蜘蛛在整个w 曲中拉 网式地探索未知网页，从而实现“疏而不漏”地挖掘新的w 曲c o i r n u n i t y 。 最后是系统的设计与实现，在上述理论分析的基础上提出了系统的设计思 想，并介绍了系统的体系结构和具体实现技术。 关键词垂直搜索引擎，中文分词，网络蜘蛛，隧道技术，主题相关度预测 浙江大学硕上学位论文a b s 打a c t a b s t r a c t t h er a p i d 芦o w c ho ft h ei m e m e tp o s e su n p r e c e d e m e ds c a l i n gc h a l l e n g e sf o r g e n e r a 】- p l l i p o s es e a r c he n g i n e s i na d d i t i o n ，g e n e r a l p u r p o s es e a r c he n g i n e sp r o v i d e s e r v i c ef o ra l lu s e r s ，s ot h er e s m t s 丘o mt h e ma r et o oe x h a u s t i v e ，t h o u s a n d so f i r r c l a t i v er e s u l t so b v i o u s l yd on o tm e e tp i - e c i s es e a r c hn e e d s t h e r e f o r e ，v e n i c a l s e a r c he n g i n ew h i c hp r o v i d e ss e i 、，i c ei na s i n g i ef i e l de m e r g e d r a t h e rt h a nc o l l e c t i n ga n di n d e x i n ga l la c c e s s i b l ew 色bd o c u m e n t st ob ea b l et o a n s w e ra l lp o s s i b 】eq u e r i e s ，af o c u s e dc r a w l e ra n a l y z e si t sc r a w lb o u n d a r yt of i n dt h e 1 i i l l 【sm a ta r e1 i k e l yt ob em o s tr e l e v a n tf o rt h ec m w l ，a n da v o i d si r r e l e v 跚t r e g i o n so f m ew 曲a so n l yr e l a t e dp a g e sa r ec r a w j e d ，a c c u r a c ya i l de m c i e n c yo fv e r t i c a ls e a r c h e n g i n e s h a v e i m p r o v e dr e i n a r k a b l y c u r i n t ly ， a c c u m c y o fc h j n e s ew o r d s e g m e m a t i o na i l dc o r r e l a t i o np r e d i c t i o na r es t i l lt ob ei m p r o v e d ，s e a r c hs 订a t c g yo f f o c u s e dc r a w l e rh a sy e tt ob e 盘r t h e ri m p r o v e dt oe n h a r i c es e a r c he n g i n ec o v e r a g ea i l d e m c i e n c y i nc h i n e s ew o r ds e g m e n t a t i o n ，t h i s p a p e rp r e s e n t sn e wa l g o r i t h r nn a m e d a d a p t i v ec h i n e s ew o r ds e 鲫e n t a t i o nb a s e do nt h e m ew h i c hu s ec a n d i d a t e d i c t i o n a r y a i l d p r o f e s s i o n a ld i c t i o n a r y t o g u i d es e g m e n t a t i o n a n d 锄b i g u “y e l i m i n a t i o n i tp r o v e dt ob ee i 琵c t i v ei nr a i s i n gp r e c i s i o no fm ep r o f e s s i o n a lw o r d s e g m e m a t i o n i nc o r r e l a t i o np r e d i c t j o na l g o r i t h i n ，t h 陀em o d e l sa r ep r e s e n t e di nt h i sp a g e r ： c o l a t i o np r e d i c t i o na l g o r i t h mb a s e do nf a t h e r ( c p a p ) ，c o r r e l a t i o np r e d i c t i o n a l g o m h mb a s e do nh y p e r l i n k ( c p a h ) a n dt p rc o r r e l a t i o np r e d i c t i o na 1 9 0 矗t h m t h ea i l c h o rt e x ta n dc o r r e l a t i o no ff a t h e rp a g e sa r ei n v o l v e di nt l l ec p a pm o d e l ； c p a hm o d e lc a l c u l a t e sc o m l a t i o nb yt h e q u a n t i _ ) r a 1 1 dq u a l i t yo fp a g e s ；t p r a l g o r i t l l mc o m b i n e st h ec o r r e f a 虹o na n da u t h o r i t yo fp a g e s ，t 壬l e 碑b yi te f 奄c t i v e l y p r e v e n t t 1 1 e m e “r ”p h e n o m e n o n i nt 1 1 ew 曲s e a r c hs t r a t e g y ，t i l i sp a p e rp r e s e n t sas p a r s et i l 衄e l i n gt e c 1 1 1 0 l o g y i t e f r e c t i v e l y a d d r e s s e dt 1 1 e e x p o n e n t i a li n c r e a s i n gp m b l e mw i t ho r i g i n a lt u n n e l i n g t e c l l l l o l o g y s p a r s et u n n e l i n gt e c l l n o l o g ye x p l o r et l l ee n t i r cw 曲印a r s e l y ，m e r e b yi t g r e a t i yi m p m v e dm ep r o b a b i l i t yo fd i s c o v e r i n gn e w 、e bc o m m u n j t i e s f i n a l l yt l l ed e s i g na n dt l l er e a l i z a t i o no ft h es y s t e ma r ei m r o d u c e d ，i n c l u d i n gt 1 1 e s y s t e ms l 娜c t u r ea f l dm e t h o d k e y w o r d s v e r t i c a ls e a r c he n g i n e ，c h i n e s ew 0 r ds e g r n e n t “o n ，f o c u s e dc r a w l e r t l l n n e l i n 岛c o r r e l a t i o np r c d i c t i o n 浙江大学硕士学位论文第l 章绪论 第1 章绪论 1 1 背景 随着i n t e m e t 的飞速发展，w 曲的信息量越来越大，人们往往需要借助搜索 引擎来帮助他们寻找特定领域的资料，然而现有的搜索引擎如g 0 0 酉e 、百度等， 都不是专门为搜索特定领域资料而设计的，这些搜索引擎面向所有的用户，力争 在返回结果上做到面面俱到。因此，真正需要的资料往往淹没在大量的无用的信 息中，在这种情况之下，面向特定专业的搜索引擎，即垂直搜索引擎应运而生。 垂直搜索引擎也叫专业搜索引擎，是相对通用搜索引擎的覆盖率过低、查询不准 确、更新不及时等缺点提出来的新的搜索引擎服务模式，它通过针对某一特定领 域、某一特定人群或某一特定需求而提供有一定价值的信息和相关服务，其特点 是“专、精、深”，且具有行业色彩。 目前因特网上的可索引到的网页数量已超过1 l o 亿页【1 】，还有相当大的一部 分网页无法被搜索引擎索引到，即使是世界上最大的搜索引擎g o o g l e 也只能索引 到整个w 曲的3 0 4 0 ，更新这些索引的时间从几周到几个月不等。这种挑战不 是来自互联网本身，而是来自一个简单的哲学道理：我们没有办法让台机器存 储整个互联网的信息，垂直搜索引擎是在这样的背景下提出来的一种顺应历史潮 流的解决方案。 本文在这种背景下，结合近年来比较热门的f o c u s e dc r a w l i n g 【2 】的研究成果， 对垂直搜索引擎中的中文分词和精确爬行( c r a w i i n 曲技术提出了新的思路和解决 方法，结合这种新思路所实现的垂直搜索引擎较普通的垂直搜索引擎在精度和效 率上都有较大的改进。 1 2 通用搜索引擎 1 2 1 搜索引擎的发展历史 在互联网发展初期，网站相对较少，信息查找比较容易。然而伴随互联网爆 炸性的发展，普通网络用户想找到所需的资料简直如同大海捞针，这时为满足大 众信息检索需求的专业搜索网站便应运而生了。 现代意义上的搜索引擎的祖先，是1 9 9 0 年由蒙特利尔大学学生a i 弛e m t a g e 发明的a r c h i e 。虽然当时w j r i dw i d ew 曲还未出现，但网络中文件传输还是相当 频繁的，而且由于大量的文件散布在各个分散的f 1 p 主机中，查询起来非常不便， 因此a l 锄e m t a g e 想到了开发一个可以以文件名查找文件的系统，于是便有了 a i c h i e 。 浙江大学硕上学位论文 第l 章绪论 a r c l l i e 工作原理与现在的搜索引擎已经很接近，它依靠脚本程序自动搜索网 上的文件，然后对有关信息进行索引，供使用者以一定的表达式查询。由于a r c l l i e 深受用户欢迎，受其启发，美国内华达s y s t e mc o m p 嘶n gs e r v i c e s 大学于1 9 9 3 年 开发了另一个与之非常相似的搜索工具，不过此时的搜索工具除了索引文件外， 已能检索网页。 最早现代意义上的搜索引擎出现于1 9 9 4 年7 月。当时m i c h a e l m a m d i n 将j o h n l e a v i 仕的蜘蛛程序接入到其索引程序中，创建了大家现在熟知的l 水o s 。同年4 月，斯坦福( s t a i 渤r d ) 大学的两名博士生，d a v i df i l o 和美籍华人杨致远( g e n 呷 y 粕g ) 共同创办了超级目录索引y 曲0 0 ，并成功地使搜索引擎的概念深入人心。 从此搜索引擎进入了高速发展时期。 1 2 2 搜索引擎的分类 搜索引擎按其工作方式主要可分为三种，分别是日录式搜索引擎、基于网络 蜘蛛全文搜索引擎和元搜索引擎。 1 ) 目录式搜索引擎目录式搜索引擎的典型代表是y a h o o ，它们主要依靠人 工维护网站索引。基于目录的搜索引擎通过人工浏览各站点的信息，按照一定的 分类规则或分类体系，对网站进行分类。一般来说，它们具有结构清晰、错误较 少，比较符合人们的阅读习惯的优点，而缺点是工作人员多、整理周期长，速度 慢、人工干预成分多，不能适应w 如资源的规模发展，另外如果查找的信息没有 对应的分类项，则无法进行搜索。 2 ) 基于网络蜘蛛的全文搜索引擎网络蜘蛛是指可以在w 曲上漫游并按照 一定规则自动从w 曲下载网页的计算机程序，对应的同义词有机器人f r o b o t l 、爬 行器( c m l e r ) ，漫游者( w a n d e f e r ) 等。本论文统一采用“网络蜘蛛”来代表该类计算 机程序。基于网络蜘蛛的搜索引擎的全部工作基本上由程序自动完成，人工参与 成分很少。它通过网络蜘蛛在网上自动爬行，将搜索到的网页自动地加入到本地 索引数据库中，用户可以很快从索引数据库查到更新后的信息。它的优势在于自 动化程度高、维护费用低，更强调技术上的创新和提高，也更适合于开展研究工 作，因而成为当前研究的热点。常用的基于网络蜘蛛的搜索引擎有剐t a v i s t a ， i n f o s e c k ， g o o 酉e 等。 3 ) 元搜索引擎元搜索引擎是一种通过调用其它独立搜索引擎而完成搜索 服务的搜索引擎，是用户同时使用多个独立搜索引擎进行网络搜索的中介。用户 只需递交一次检索请求，由元搜索引擎负责转换处理后提交给多个预先选定的独 立搜索引擎，并将所有查询结果集中起来以整体统一的格式呈现到用户面前。元 搜索引擎通过综合利用多个搜索引擎的搜索服务，可以在一定程度上弥补单个搜 索引擎的不足，但是元搜索引擎的出现，并不能使搜索引擎技术得到气的飞跃， 2 浙江大学硕士学位论文第l 章绪论 它们仅仅只是提供了搜索结果的重新组织。典型的元搜索引擎有m e t a c r a w i e r ， b ”e s e a r c h 等。 1 2 3 搜索引擎组成及工作原理 目前流行的搜索引擎关注广大用户的搜索需求，不对人群需求进行划分，因 而也被称之为通用搜索引擎，下面介绍通用搜索引擎的组成和一般性原理。 搜索引擎系统一般由网络蜘蛛、分词器、索引器、查询器几部分组成【2 l ，2 8 】。 网络蜘蛛负责网页信息的抓取工作，一般情况下分词器和索引器一起使用，它们 负责将抓取的网页内容进行分词处理并自动进行标引，建立索引数据库。查询器 根据用户查询条件检索索引数据库并对检索结果进行排序和集合运算，如并集、 交集运算，再提取网页简单摘要信息反馈给查询用户。 以g d o 四e 为例，搜索引擎从功能上可分为三大部分：w 曲页搜索、标引入 库和用户查询。 1 ) w 曲页搜索w 曲页搜索部分主要负责网页的抓取，由u r l 服务器、网 络蜘蛛、存储器、分析器和u r l 解析器组成，网络蜘蛛是该部分的核心。 2 ) 标引入库标引入库主要负责对网页内容进行分析，对文档进行索引并 存储到数据库里，由标引器和分类器组成。 3 ) 用户查询用户查询主要负责分析用户输入的检索表达式，匹配相关文 档，把检索结果返回给用户，由查询器和p a g e r a n k 值评定器组成，其中网页等 级的计算是该部分的核心。 g o o 西e 搜索引擎的体系结构如图1 1 所示： 浙江大学硕士学位论文第l 章绪论 标 引 入 库 用 户 查 询 国 驰回 | g 隔南搀 l 吲 耳人 入 多圆 l 立越 r n l 一 一一一j 图1 1 通用搜索引擎体系结构 搜索引擎的主要工作流程是：首先从网络蜘蛛开始，按深度优先或广度优先 算法，抓取u r l 服务器上所指定的网页，将抓取的网页存入文档数据库。一般 在存入文档数据库之前进行一定的压缩处理，并将当前页上的所含超链接存入到 u r l 服务器中。 在进行抓取的同时，分词器和索引器将已经抓取的网页文档进行分词处理， 并按词在网页中出现的位置和频率计算权值，然后将分词结果存入索引数据库。 用户提交查询时，查询器首先对用户输入的信息进行分词处理，并检索出所 有包含检索词的记录，通过计算网页权重和级别对查询结果进行排序，最后从文 档数据库中提取各网页的摘要信息反馈给查询用户。 1 2 4 现有的通用搜索引擎的局限性 通用搜索引擎的出现很大程度上解决了人们在互联网上查找信息的困难，但 在使用中也面临着如下问题： 1 ) 覆盖率低基于w 曲的自身特点，大量的数据分布在数以亿计页面的互 联网上，检索起来困难重重。单个搜索引擎的覆盖率一般都低于3 0 ，很难索引 所有的w 曲资源。 2 ) 时效性差互联网信息呈指数增长，大量信息的存活期却在缩短，这导 致搜索引擎的时效性很难保证，返回结果中存在大量无效或过时的链接。 4 w e r 页搜索 浙江大学硕士学位论文第1 章绪论 3 ) 易导致迷航经典的信息检索界认为用户很难简单地用关键字来忠实表 达他所真正需要检索的内容，甚至根本就不知道要找什么东西，即所谓“迷航”。 表达的困难将导致检索结果的不理想，而且如何将结果表达成用户容易理解和使 用的方式也是一个难题。 4 ) 结果不准确一次搜索的结果可能有成千上万条，而在这过于庞大的信 息中，有用信息只是其中的小部分，可谓“冰山一角”，并且常常发生收到和下载 的信息难以消化的情况，即所谓的“认知过载”。 5 ) 过于死板现有的搜索引擎多采用关键词的机械式匹配。没有对用户的 输入进行语义理解，这种方式的固有缺点是参与匹配的只有字符的外在表现形 式，而非它们所表达的概念。因此，经常出现答非所问、检索不全的结果。 1 2 5 搜索引擎的发展趋势 正在发展的第三代搜索引擎以智能化、个性化和专业化为目标，力争为用户 提供更快更准的查询结果。下面介绍第三代搜索引擎技术的研究热点。 1 ) 多媒体搜索引擎随着宽带技术的发展，未来的互联网是多媒体数据的 时代。音频、视频和图像将取代文本成为互联网上主要的信息载体。一开发基于内 容检索的多媒体搜索引擎是一个新的发展方向。 2 ) 个性化搜索引擎个性化搜索能够满足用户的个体信息需求，通过长期 观察用户的搜索行为，从中识别用户的信息需求偏好，并且能够根据用户对搜索 结果的评价，自觉调整搜索策略，使得对于同一检索请求，不同用户能够得到最 贴近自己需要的信息。个性化搜索引擎的核心是根据用户信息以及通过跟踪分析 用户的搜索行为来提高搜索引擎查准率。 3 )智能化搜索引擎传统的搜索引擎对要检索的信息采用机械式匹配来 实现，缺乏知识处理能力和理解能力，智能化搜索引擎把信息检索从目前基于关 键词的层面提高到基于知识( 或概念) 的层面。智能搜索引擎对知识有一定的理 解与处理能力，能够实现智能分词技术、同义词技术、概念搜索、短语识别以及 机器翻译技术等。它允许用户采用自然语言进行信息检索，为他们提供更方便、 更确切的搜索服务。 4 ) 垂直搜索引擎目前，大多数搜索引擎在满足搜索全面性要求的同时难 以兼顾专业性的需求。垂直搜索引擎面向特定领域，专注于自己的特长，保证了 对该领域信息的完全收录与及时更新。与通用搜索引擎不同，垂直搜索的目标是 尽可能多的搜集与该主题相关的网页。专业网络蜘蛛抓取到的网页如果与预定义 主题相关，就做进一步的处理；如果不相关，则抛弃该网页。这样处理的结果是， 系统最终只索引了w 曲上所有网页的一部分，也就是与预定义主题相关的网页。 这样处理的好处是可以节省大量的存储空间和具有较高的更新频率。在较短的时 浙江大学硕士学位论文第l 章绪论 间内就可以把主题领域内的网页全部更新一遍，这样能够跟上w e b 上网页变化。 而且对用户而言，如果她对该主题感兴趣，那么系统在该领域的信息是最详尽的。 垂直搜索引擎也是本文的研究重点。 1 3 垂直搜索引擎 垂直搜索引擎，即专业或主题搜索引擎，就是专为查询某一领域或主题的信 息而产生的查询工具，它专门收录某一主题的信息，对解决该领域内的实际查询 问题要比通用搜索引擎有效得多。如果用户想获得某一专业的信息，就可使用垂 直搜索引擎。 1 3 1 垂直搜索引擎的优势 通用搜索引擎的弊端在网络信息的急剧膨胀下突显起来，搜索越来越难以控 制，用户需求和市场服务间的巨大反差产生了强大的“搜索噪音”，人们呼唤更有 针对性的搜索引擎，垂直搜索引擎应运而生。 垂直搜索引擎的网络蜘蛛只抓取特定主题的信息，按预先己经定义好的专题 有选择地收集网页。由于所收集的学科领域小，信息量相对较少，更新及时，因 而有效地解决了通用搜索引擎的弊端。 由于垂直搜索引擎只涉及一个或几个领域，词汇和用语“一词( 一语) 多意”的 可能性降低，而且可以利用专业词表进行规范和控制，大大提高查全率和查准率。 这种高度目标化、专业化的搜索引擎的优势在于针对性强，对特定范围的网 络信息的覆盖率相对较高，有明确的检索目标定位，有效地弥补了综合性搜索引 擎对专门领域及特定主题信息覆盖率过低的问题。 1 3 2 专业网络蜘蛛 页面抓取是搜索引擎工作流程中的第一步，通常是由网络蜘蛛完成的。当前 的网络蜘蛛主要有两点不足： 1 ) w e b 页面覆盖率不够高 2 ) w c b 页面更新不及时 专业网络蜘蛛( f o c u dc m w l e r ) 是垂直搜索引擎的重要组成部分，它在搜 索i n t 唧e t 时会对u r l 进行主题识别，判断是否符合特定领域的网站，从而大大 缩小抓取范围。 通用网络蜘蛛的目标是要发现和下载尽可能多的网页，以使搜索引擎能回答 更多的用户查询，因此在网络蜘蛛技术上采用了宽度优先或深度优优先的搜索策 略，使网络蜘蛛有更广的覆盖面。 然而，专业网络的目标是在尽可能少地遍历w 曲的前提下，却尽可能多地发 6 浙江大学硕上学位论文 第l 章绪论 现与主题相关的网页。因而，专业网络蜘蛛往往采用b e s tf i r 矿策略，即更高主 题相关度的网页优先下载。为了实现“b e s t f i r s r 策略，需要将待下载的u i 也根据 主题相关度进行排序，因此，需要预测待下载u r l 的主题相关度，即在不下载 网页的前提下，通过已知的信息来预测u r l 所指向的网页与主题的相关度，本 文第三章提出的主题相关度预测算法具有较高的准确率。 1 3 3 研究现状 目前在国内外，有关新一代搜索引擎的研究正在成为一个热点，下面介绍一 下具有代表性的系统。 1 ) s c i r u s 是面向科技文献的一个垂直搜索引擎，它的信息源主要包括网页 和期刊两部分。它首先对网络中所搜索到的结果进行过滤，然后只列出包含有科 学信息的成分，方便了科研人员的使用。 2 ) b e r k e l e y 的f o c u s e dp r o j e c t 系统通过两个程序来指导爬行器，一个是 分类器，用来计算下载文档与预定主题的相关度，另一个程序是净化器，用来确 定那些指向很多相关资源的页面。 3 ) 基于概念搜索的a s kj e e v e s 搜索引擎，它将用户提问转化为系统已知的 问题，在对提问进行结构和内容分析之后，或直接给出问题的答案，或引导用户 从几个可选择的问题中进行再选择。用户只需输入简单的疑问句，如“w l l a t i s t h e m e 她i n g o f ? ”，“h o w c a i l i d o ? “w h e r e c 觚i f m d ? ”等句式就能直接 获得结果。 垂直搜索引擎的关键技术有中文分词和网络蜘蛛等。中文分词技术是中文搜 索引擎重要的组成部分，自从8 0 年代初中文信息处理领域提出中文分词以来， 中文分词研究全面兴起，取得了一些重要的进展和一些实用性的成果。 目前分词的方法主要可分成三大类：机械分词方法、基于统计的分词方法和 基于理解的分词方法。机械分词方法需要分词词典的支持，具有效率高，算法简 单的特点；基于统计的分词方法根据词的频度来判断成词的概率，这种方法能有 效地识别新词，但效率往往没有机械分词方法高；基于理解的分词方法通过让计 算机模拟人对句子的理解，达到识别词的效果，由于语言知识和语言规则过于复 杂，因而这种方法尚处于研究的阶段。 专业网络蜘蛛技术( f o c u dcr a _ w l e r ) 是垂直搜索引擎的关键部分，直接决 定了垂直搜索引擎的质量。专业网络蜘蛛从9 0 年代中期的文本分类工作发展而 来，到9 0 年代末已经成为一个热点的研究领域。 专业网络蜘蛛技术的研究成果有：c h a k r a b a n ie ta 1 实现了一个免定制和存储 管理的专业爬行器【3 】；i 尬i e 和m c c a l l 啪【4 】将巩固学习( r e i n f o r c 锄e n t l e a m i n g ) 【5 】引入网络蜘蛛的学习过程，通过训练发掘出链接文本中“隐含”的结构 7 浙江大学硕上学位论文第1 章绪论 信息来指导爬行器工作；d i l i g e m i 【6 】提出了基于语境图的搜索策略，它通过构建 典型页面的w j b 语境图”来估计离目标页面的距离；为避免p a g e 黜i i l l 【算法的“主 题漂移”问题，斯坦福大学计算机科学系胁e fh a v e l i 啪l a 提出了主题敏感t o p i c l l s i t i v ep a g e r a n k 算法 1 0 】等等。 1 4 本文的工作和组织 在中文分词技术方面，本文提出了基于主题的自适应分词技术，使用候选词 典和关键词库来指导分词和歧义消除过程，为了合理地控制候选词典的规模和质 量，提出了a 西n g 技术，使得一部分关键词由于过于衰老而退出候选词典。将基 于主题的分词方法和基于统计的方法相结合具有较高的查全率和查准率。 在专业网络蜘蛛技术方面，提出了基于父网页的主题相关度预测、基于链入 网页的主题相关度预测和t p r 算法。基于父网页的主题相关度预测利用了锚文本 和父网页的主题相关度等信息进行预测；基于链入网页的主题相关度预测算法则 综合考虑了链接进入网页的数量和质量；t p r 算法将网页的主题相关性和权威性 相结合，从而有效地防止“主题漂流”现象。 此外，为了克服基于“隧道技术”的网络蜘蛛效率低下的问题，本文改进了 “隧道技术”的算法，改进后的隧道技术能在整个w 曲中拉网式地探索未知网页， 从而发现新w 曲c o m m u n 埘的概率大大得到提高。 下面是本文的章节结构： 第一章绪论 介绍了本文的研究背景及搜索引擎的历史、分类、工作原理和发展趋势。对 比了通用搜索引擎和垂直搜索引擎的优缺点，介绍了垂直搜索引擎，总括全篇的 研究目标和各章内容。 第二章相关技术的研究现状 本章首先介绍三大类的中文分词方法：机械分词、基于统计的分词和基于规 则的分词方法，然后介绍用于主题相关度判别的计算模型：布尔模型和向量空间 模型，最后介绍两种较为出名的基于链接的分析技术p a g e r a n k 和h i t s 算法。 第三章中文分词和主题预测关键算法 本章主要介绍了本文提出的几个主要算法：基于主题的自适应的分词方法、 基于父网页主题预测方法、基于链入网页的主题预测方法和1 1 p r 主题预测算法。 第四章基于稀疏隧道技术的f o c u s e dc r a w l e r 本章首先介绍f o c l l s e dc r a w l e r 技术，为了解决f o c u 卵dc r a w l e f 的缺点，引 进了隧道( t u m e l i n 曲技术，最后介绍本文提出的稀疏隧道技术。 第五章系统设计与实现 介绍了系统的设计原型，以及系统的相关技术实现细节。 浙江大学硕士学位论文第l 章绪论 第六章总结与展望 总结全文，提出了一些不足之处，并对下一步的研究和应用做出展望。 最后是参考文献及致谢。 9 浙江大学硕士学位论文第2 章相关技术的研究现状 第2 章相关技术的研究现状 本章主要对中文分词技术、专业网络蜘蛛技术和链接分析技术的研究现状做 一个概述，并对其中一些实现细节做探讨。 2 1 中文分词技术 汉语以字为基本的书写单位，而作为能够独立活动的有意义的最小语言成分 的却是词。中文信息处理中一个重要的基础课题就是词的切分，也称中文分词， 与拉丁语系的语言以空格作为词界不同，在汉语中词与词之间没有明显的区分标 记【7 】，因而中文分词的意义显得格外重要。众所周知，词在中文信息处理的诸多 环节起着重要的作用，当然也包括了搜索引擎。 现有的分词算法可分为三大类：基于字符串匹配的分词方法、基于统计的分 词方法和基于理解的分词方法。机械分词方法需要分词词典的支持，具有效率高， 算法简单的特点，但难以排除机械切分产生的歧义，准确率较差【8 】；基于统计的 分词方法根据词的频度来判断成词的概率，这种方法能有效地识别新词，时空开 销大，效率有限；基于理解的分词方法通过让计算机模拟人对句子的理解，达到 识别词的效果，由于语言知识和语言规则过于复杂，因而这种方法尚处于研究的 阶段。 2 1 1 基于字符串匹配的分词方法 基于字符串匹配的分词方法，又叫做机械分词方法，它是按照一定的策略将 待切分的汉字串与分词词库中的词条进行匹配，若在词库中找到相应的词条，则 匹配成功。目前实用的分词系统基本上都是以基于字符串匹配的分词方法为主， 辅之以少量的词法、语法和语义信息。 按照扫描的方向不同，基于字符串匹配的分词方法可分为正向匹配分词方法 和逆向匹配分词方法；按照优先匹配的长度不同，又可分为最大匹配分词方法和 最小匹配分词方法。总的来说，机械分词方法中共有三种基本的分词方法，分别 是最大正向匹配法、最大逆向匹配法和逐词遍历法。除了这三种基本的方法外， 还可以在分词的过程中使用一些其它技巧，形成新的分词方法，主要有双向扫描 法、设立切分标志法、最佳匹配法和二次扫描法等等。 最大正向匹配法( m a x i m u mm a t c h i n gm e t h o d ) 。 该算法通常称为m m 法，其基本思想为：设m a x 为词典中的词条长度的最 大值，s 仃为待切分的句子或字串。如图2 1 所示，首先，令l e i l g t h 等于m a 】( ， m m 法每次从s 仃中取出长度为l e n g t h 的一个子串，把该子串与词典中的词条进 行匹配。若成功，则该子串为词。指针后移l e n g m 个汉字后继续匹配下一个词。 1 0 浙江大学硕士学位论文第2 章相关技术的研究现状 若不成功，则把该字串最后一个字去掉，再与词典中的词条进行匹配。如此匹配 下去，直至匹配成功或该子串只剩一个字为止( 表示该字可以当作词，可在该字后 面开始切分) 。 图2 1m m 算法流程 m m 分词算法优点是算法简单，不需要任何的词法、句法和语义知识，没有 很复杂的数据结构。唯一的要求就是必须有一个很强大的分词词典，缺点是不能 很好地解决歧义问题，不能认识新词。有统计表明，单纯使用该方法的匹配错误 率为1 1 6 9 ，这种精度还远远不能满足实际的需要。实际使用的分词系统，都是 把机械分词作为一种初分手段，还需通过利用其它的语言信息来进一步提高切分 的准确率。 逆向最大匹配法( r e v e r s em a ) 【i m u mm a t c h i n gm e t h o d ) 该算法通常称为r m m 算法，它的基本原理与m m 算法一样，不同的是分 词的扫描方向，r m m 算法从词尾开始切分。根据统计分析，r m m 分词算法比 m m 算法有更高的切分准确率，切分错误率为1 ，2 4 5 。 逐词遍历法 逐词遍历分词方法是将词典中的词条由长到短递减的顺序，逐个在待处理的 字串或句子中搜索，直到切分出所有的词为止。不论分词词典多大，都得把整个 分词词典匹配一遍。故这种方法的时间复杂度比较高，分词的速度慢、效率不高。 双向扫描法 双向扫描法的基本原理是分别用m m 法和r m m 法进行初步的切分，并将 浙江大学硕士学位论文第2 章相关技术的研究现状 m m 法切分的结果与r m m 法切分的结果进行比较，如果两种结果一致，则判定 切分正确；如果两种结果不一致，则采用人工干预的方式，或者记频度的算法， 或者结合上下文相关信息选取一种切分。该算法能发现所有的交集型歧义字段， 但对于正、逆向的扫描结果一致但实际切分不正确的字串仍然不能正确处理。 设立切分标志法 该方法首先在待切分字符串中识别出一些带有明显特征的词，并以这些词作 为断点，可将原字符串切分为较小的串再进行机械分词，从而减少匹配的错误率。 最佳匹配法 最佳匹配法的原理：在词典中按词的出现频率大小排列词条，高频率的词排 在前，低频率的词排在后，从而缩短分词词典的检索时间，达到最佳效果，加快 分词速度。 二次扫描法 有统计表明，汉语中词的平均长度为1 8 3 。因此，每次从待切分的字符串中 取两个字符比取最大长度的子串进行匹配的方法相比，前者的效率更高。 该方法的基本做法是：首先从待切分的字符串中取两个汉字记为s 仃，检查分 词词典中是否有这样一个词，它前两个汉字和s 仃相同，若有的话，则取待切分 的字符串中的前三个汉字记为s t r ，重新在分词词典中查找前三个字相同的词条， 如果匹配成功则继续上述过程，直到进行了n 个汉字为止( 设n 为词典中最长词所 含汉字的个数) ，则切分出一个n 字词；如果匹配不成功则完成了一次扫描；把 s t r 中最后一个汉字去掉，使用m m 方法或i t m m 方法进行第二次切分。 二次扫描法只是改变了m m 分词法从词条的最大长度开始匹配的做法，而是 从长度为2 的词条开始匹配，这样可以大量地减少匹配失败的次数，从而提高了 分词的效率。 2 1 2 基于统计的分词方法 基于统计的分词方法的基本原理：从形式上看，词是稳定的字的组合，因此 在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与 字相邻共现的频率或概率能够较好地反应成词的可信度。 当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词。这种方 法只需对语料中的字组合的频度进行统计，不需要切分词典，因而又叫做无词典 分词法。但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是 词的常用字组，例如“这一”、：艺一”、“有的”、“我的”、“许多的”等，并且对常用 词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分 词词典( 常用词词典) 进行串匹配分词，同时使用统计方法识别一些新的词，即 将串频统计和串匹配结合起来，既发挥机械分词切分速度快、效率高的特点，又 1 2 浙江大学硕士学位论文第2 章相关技术的研究现状 利用了基于统计分词方法结合上下文识别生词、自动消除歧义的优点。 计算汉字间紧密程度的统计模型主要有：互信息、t 测试两种。 互信息 定义1 ：对一包含汉字x 和y 的字符，x 和y 之间的互信息定义为 j ( x ，】，) = 1 0 9 ：高晶 ( 2 1 ) 式中：j 仪】卜汉字x 和y 的互信息； p 伍】卜汉字x 和y 联合出现的概率； p 圆一汉字x 出现概率； 尸一汉字y 出现概率。 互信息体现了汉字之间结合关系的紧密程度，当紧密程度高于某一个阈值 时，便可认为此字组可能构成了一个词。在公式( 2 1 ) 中，p 岱，的表示汉字串x y 联合出现的概率，p ( ) ( ) 为x 出现的概率，p ( y ) 为y 出现的概率，可以通过以下公 式计算得出： 尸( 置r ) ：塑，戌柳：堕型，尸( 】，) ：盟( 2 2 ) ，l ” 公式( 2 2 ) 中，汉字串x 、y 和x y 出现的次数分别计为n c 趵、n ( y ) 、n ( x y ) ， 汉字串总长度为n 。 s p r o a t 等最早将互信息用于定量估计两个汉字问的结合力：两汉字问互信息 越大，两个汉字结合的紧密程度越高；互信息越小，结合的紧密程度越低。并给 出了两个相邻汉字断连与否( 即是否能够构成词，连则能构成词，断则不能构成词) 的判别规则：互信息超过某一阈值，则连；否则断。 t 测试原理 定义2 ：对有序汉字串x y z ，汉字y 相对于x 及z 的t 测试定义为 “2 丽筹舞 ， 艿2 ( p ( z y ) ) + 艿2 ( p ( y x ) ) 。 式中：p 似j _ _ y 关于x 的条件概率； 尸白纠z 关于y 的条件概率； j 2 ( 尸( z y ) ) _ z 关于y 方差； 万2 ( 户o ，砌y 关于x 方差。 浙江大学硕士学位论文第2 章相关技术的研究现状 从t 测试的定义，可知： ( 1 ) t 测试 o 时，字y 有与后继字符z 相连的趋势，值越大，相连趋势越强； ( 2 ) t 测试= o 时，不反映任何趋势； ( 3 ) t 测试 o 时，字y 有与前趋字符x 相连的趋势，值越小，相连趋势越强。 2 1 3 基于理解的分词方法 基于理解的分词方法是通过计算机模拟人对句子的理解，达到识别词的效 果。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信 息来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控 部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义 信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需 要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种 语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试 验阶段。 2 2 主题判别的研究现状 垂直搜索引擎与通用搜索引擎最大的区别在于垂直搜索引擎是面向某个领 域的，因而垂直搜索引擎的网络蜘蛛只采集与主题相关的网页，与主题无关的网 页将被丢弃，我们将此类网络蜘蛛称为专业网络蜘蛛( f 0 c u s e dc r a w l e r ) 。 专业网络蜘蛛将网页下载到本地后，需要使用基于内容的主题判别方法计算 该网页的主题相关度值，主题相关度低于某一阀值的网页被丢弃。主题相关度的 计算方法有布尔模型和空间向量模型。 2 2 1 布尔模型 在主题判别时，布尔模型是最容易实现的。在布尔模型中，一个文档通过一 个关键词集合来表示。同时，某个主题也以关键词集合的形式来表示。在判断文 档与某主题的相关度的过程中，相当于是计算两个关键词集合的交集。对基于布 尔模型的主题判别模型来说，交集中含有的元素越多，则认为与主题的相关度就 越高。可以用文档d 与主题关键词集合t 之间交集元素的个数占集合t 的比例来 代表文档d 的主题相关度s i m ( d ) ，公式表示如下： 删耻喘铲 ( 2 4 ) 布尔模型的主要缺陷在于每个关键的权重都是一样的，它不支持设定关键词 1 4 浙江大学硕士学位论文 第2 章相关技术的研究现状 的相对重要性，但是其优点也较为明显，它易于实现，计算代价较小。 2 2 2 向量空间模型 该模型由s a l t o n 等人在1 9 6 8 年提出 1 3 】，该模型中的主题主关键词和文档关 键词均通过向量来表示。文档向量是一个n 元组，其中，每一个坐标值代表了相 应关键词的权重。权重越大，对应的关键词对于该文档就越重要。主题关键词向 量和文档向量类似，主题关键词向量中的权重表示对应关键词相对于该主题而言 的重要性。 对于关键词权重的设定，通常是基于词在文档中的出现频率，目前有许多计 算关键词权重的方法，s a i t o n 等在文献中给出了如下的计算公式【1 3 】： 对于关键词t ，其在文档i 中的权重定义为： 耽堙厅f ( r ，f ) = 办l g ( 一r ) 其中，五为关键词t 在文档i 中出现的频率，n 为信息库中文档的数目；胁为 整个文档信息库中包含词条t 的文档的个数； 为文档i 中所有关键词的个数。 从公式( 2 5 ) 可以得到，一个关键词在文档中出现的次数越多，其权重就越大； 一个关键词在整个信息库中出现的频率越少，其在出现的文档中的权重也越大。 经过公式