（计算机应用技术专业论文）风险主题搜索引擎相关技术的研究与应用.pdf

摘要 摘要 主题搜索引擎是针对某一个行业的专业搜索引擎，是搜索引擎的细分和延 伸，是对网页库中的某类专门的信息进行一次整合。其中的关键技术包括中文分 词、主题爬虫、索引、分布式存储等，本文重点研究网络资源的爬虫和索引的主 题搜索技术，具有重要的应用价值。主要工作包括： 1 提出了一种基于内容和链接分析相结合计算主题相关度的搜索策略。基 于w e b 超链接评价算法考虑了链接结构和页面之间的引用关系，但忽略了页面 与主题的相关性。基于内容评价的算法只注重文本在主题搜索中的重要性，而 忽略了w e b 结构的作用。综合的搜索策略利用基于内容的评价来提高搜索内容 与主题的相关度，同时利用基于链接结构的评价来提高主题资源搜索的覆盖率。 2 改进了s h a r k s e a r c h 算法。从u r l 队列维护和检索时问的角度出发进行 算法的改进，提高了s h a r k s e a r c h 算法的时空效率，在主题相似度计算方法上 应用了向量空间模型；在u r l 与主题的相关性判定中，综合运用了网页文本内 容和w e b 结构图的启发策略，从待访问网站的时间性能因素出发，改进了 p a g e r a n k 算法。 3 给出了基于改进倒排表的索引器设计方案，从索引文件本身的结构出发 进行改进，采用分级的倒排表索引组织结构，提高了索引创建的效率。在索引 更新部分设计了索引器的批量索引方法与增量索引方法，实现了索引文档的动 态更新。将改进后的算法与基于n u t c h 的索引技术相结合，在此基础上实现了 一个风险主题搜索引擎索引的建立与维护。 4 基于开源项目n u t c h ，设计并实现了一个风险主题搜索引擎，把自己建 立的主题搜索引擎查询结果和网站现有的搜索结果进行比较分析，证明了系统 可以为用户提供完整准确的风险主题信息查询服务。 本课题得到了“十一五”国家科技支撑计划重点项目- 综合风险防范 ( i i 婚) 关键技术研究与示范”( 2 0 0 6 b a d 2 0 8 0 2 ) 支持。 关键词：风险主题搜索，空间向量模型，p a g e r a n k 算法，倒排表，n u t c h a b s t r a c t t h er e s e a r c ha n d a p p l i c a t i o no f i n t e g r a t e dr i s ks e a r c he n g i n et e c h n o l o g y a b s t r a c t s e a r c hf o rat h e m ei sap r o f e s s i o n a ls e a r c he n g i n ef o rac e r t a i ni n d u s t r y , i st h e s u b d i v i s i o na n de x t e n s i o nf o rt h es e a r c he n g i n e ，i st h ei n t e g r a t i o nf o rc e r t a i nc a t e g o r y o fs p e c i a l i z e di n f o r m a t i o ni nt h ew e b s i t e t h ek e yt e c h n o l o g i e s ，i n c l u d i n gt h ec h i n e s e w o r ds e g m e n t a t i o n ，t h et h e m ec r a w l e r , i n d e x i n g ，d i s t r i b u t e ds t o r a g e ；t h i sp a p e r f o c u s e so nc r a w l e ra n di n d e x i n gt e c h n o l o g y t h er e s e a r c hi n c l u d e s ： 1 a na n a l y s i so fc o m b i n i n gt h ec o n t e n ta n dl i n k st oc o c u l a t er e l e v a n c eo ft h e t h e m eb a s e di sp r o p o s e d w e b b a s e dh y p e r l i n k se v a l u a t i o na l g o r i t h mc o n s i d e rt h e r e l a t i o nb e t w e e nt h el i n k ss t r u c t u r a lt h ep a g e s ，b u to v e r l o o k e dt h er e l e v a n c eo fp a g e s w i t ht h et h e m ea n dt h es e a r c hw i l ld e v i a t ef r o mt h et h e m eo f ”t h e m ed r i f t ” c o n t e n t b a s e de v a l u a t i o no ft h ea l g o r i t h mf o c u so n l yo nt e x ts e a r c ho ft h ei m p o r t a n c e o ft h es u b j e c t ，w h i l ei g n o r i n gt h er o l eo ft h ew e b ac o m p r e h e n s i v es e a r c hs t r a t e g y c a l lm a k eu s eo fc o n t e n t - b a s e dt oi m p r o v ec o n t e n t - r e l a t e dw i t ht o p i c s ，a tt h es a m e t i m et ou s et h ee v a l u a t i o no fl i n ks t r u c t u r et oe n h a n c et h ec o v e r a g eo fs e a r c h r e s o u r c e s 2 w ei m p r o v et h es h a r k - s e a r c ha l g o r i t h mf r o mu r lq u e u em a i n t e n a n c ea n d r e t r i e v a lt i m e t h i si m p r o v et h et i m ea n ds p a c ee f f i c i e n c yo ft h ea l g o r i t h m w eu s et h e v e c t o rs p a c em o d e lt oc a l c u l a t et h et h e m es i m i l a r i t y i nt h ec o u r s eo ft h er e l a t i v i t y j u d g i n gb e t w e e nt h ep a g ec o n t e n ta n dt h et o p i c ，w ea p p l i e dt h et e r m - b a s e dv e c t o r s p a c em o d e lw h i c hi sw i d e l yu s e di nt h ef i l e do f t h et e x tc l a s s i f i c a t i o n i nt h ec o u r s eo f t h er e l a t i v i t yj u d g i n gb e t w e e nt h eu r la n dt h et o p i c ，w ea p p l yas t r a t e g yw h i c hb a s e d o nt h ep a g ec o n t e n t ，t h ew e bs t r u c t u r e ，d e v e l o p e dt h eh y p e r l i n ka n a l y s i sm e t h o d p a g e r a n kf r o mt h et i m ep e r f o r m a n c eo f t h ew e bs i t e 3 t h i sp a p e rp r o v i d e st h ed e s i g no fc h a r a c t e ri n v e r t e dl i s t sb a s e dr i s kt h e m e i i a b s t r a c t i n d e xs y s t e m w ea d o p tac l a s s i f i c a t i o nt a b l eo ft h ei n v e r t e di n d e xo r g a n i z a t i o n a l s t r u c t u r et oi m p r o v et h ee f f i c i e n c yo ft h ei n d e xc r e a t i o n w ed e s i g nai n d e xo ft h eb u l k a n di n c r e m e n t a la p p r o a c ht or e a l i z et h ed y n a m i cu p d a t i n go fi n d e xd o c u m e n t w e e s t a b l i s ha n dm a i n t a i nt h ei n d e xp a r to far i s kt h e m ee n g i n ec o m b i n et h i sc o n s t r u c t i o n a l g o r i t h mw i t hn u t c h 4 t h i sp a p e rd e s i g nar e a l i z ear i s kt h e m ee n g i n eb a s e do nt h eo p e ns o u r c e p r o j e c tn u t c h w ep r o v et h a tt h es y s t e m c a np r o v i d eu s e r sw i t hc o m p r e h e n s i v e i n f o r m a t i o nf o rr i s kt h e m ei n f o r m a t i o ns e r v i c e st h r o u g hc o m p a r i n go u ro w ns e a r c h e n g i n eq u e r y r e s u l t sa n dt h ee x i s t i n gs i t es e a r c hr e s u l t s t h er e s e a r c hw o r ki ss u p p o r t e db yk e yn a t i o n a ls c i e n c ea n dt e c h n o l o g yp r o j e c t o ft h e ”ll t hf i v e - y e a r ”p l a n ，”k e yt e c h n o l o g yr e s e a r c ha n dd e m o n s t r a t i o no f i n t e g r a t e d 蹦s kg u a r d i a n s ”( n o 2 0 0 6 b a d 2 0 8 0 2 ) k e y w o r d s ：r i s kt h e m es e a r c h ，s p a c ev e c t o rm o d e l ，p a g e r a n ka l g o r i t h m ， i n v e r t e dt a b l e ，n u t c h i i i 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名： 鲎箧指导教师签名：啦 2 秽d 墨年6 只7 今日 h 参年舌月哆日 西北大学学位论文独创性声明 本人声明；所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的学位或证书而 使用过的材料。与我一同工作的厨志对本研究所傲的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名：第灰 d 瑟年毛其 勺e t 第一章绪论 1 1 引言 第一章绪论 主题搜索引擎，也被称为垂直搜索引擎或专用搜索引擎，是以构筑某一专题 或学科领域的i n t e m e t 网络信息资源库为目标，智能地在互联网上搜集符合这一专 题或学科需要的信息资源，为包括学科信息门户、专业信息机构、特定行业领域、 公司信息中心、行业专家等在内的信息用户提供整套的网络信息资源而产生的查 询工具。 信息采集模块索引模块检索模块 图1 1 主题搜索引擎系统结构图 主题搜索引擎与通用搜索引擎存在着很大的差别： 1 ) 服务目的不同 通用搜索引擎面向任何用户提供对任何信息的查询，而主题型搜索引擎则面 向专业用户，需要向他们提供其所在专业的信息检索。 2 ) 搜索方式不同 通用搜索引擎对网络进行逐页的爬行，试图遍历整个w e b 。而主题搜索引擎 则采用一定的遍历策略预测相关网页的位置，动态的调整对网页的爬行方向，使 第一章绪论 系统尽可能的在与主题相关的网页集中进行爬行，这将节约大量的网络资源。 3 ) 对硬件和网络的要求不同 通用搜索引擎需求过大，而主题型搜索引擎由于没有遍历整个w e b 节约了大 量的网络资源，而且没有自己的大型索引数据库所以硬件需求也比较低。 相对于通用搜索引擎，主题搜索引擎的实现难点有两个：第一，起始种子站 点和词库的设置。因为该引擎并不遍历整个w e b ，所以起始站点集合就显得格外 重要。词库作为评价网页是否相关的标准的关键词的集合，它的合理配置直接影 响到检索结果的准确性。这两个方面的设置是否合理共同决定了引擎能否找到所 有的相关内容。第二，既然是有选择性的抓取信息，那么这个有选择性的遍历 w e b 的算法就直接影响了这类引擎的工作效率。此外，信息的表示、信息抽取、 信息过滤和下一个搜索站点的选择策略都是系统实现的难点。 1 2 主题搜索引擎的研究现状 作为主题搜索引擎的关键部分，主题爬虫的研究包含在主题搜索引擎的研究 之中。目前，主题搜索引擎网络爬虫通常采用“最好优先”原则访i h l w e b t ，即 为快速、有效地获得更多的与主题相关的页面，每次选择“最有价值”的链接进 行访问。在国外，对主题搜索引擎的研究开始得比较早，同时计算机水平也发展 到相当高级的阶段，对主题搜索引擎问题的研究进行得很全面。下面介绍一些较 具代表性的系统。 1 e l s e v i e r 的s c i r u s 系统 s c i r u s 科学搜索引擎是一种专为搜索高度相关的科学信息而设计的搜索引 擎，获得2 0 0 1 搜索引擎观察授予的“最佳专业搜索引擎奖”。s c d u s 是目前 互联网上最全面、综合性最强的科技文献门户网站之一。它只面向包含有科学内 容的网站，如大学和作者个人主页以及e l s e v i e r 自己的数据库。 2 b e r k e l e y 的f o c u s e dp r o j e c t t 2 j 这个系统由一个印度裔的科学家s c h a r k r a b a r t i 带头研究开发，他是最早从事 这方面研究的人之一。该系统通过两个程序来指导爬行器：一个是分类 ( c l a s s i f i e 0 ，用来计算下载文档与预定主题的相关度；另一个程序是净化器 2 第一章绪论 ( d i s t i l l e r ) ，用来确定那些指向很多相关资源的页面。 3 n e c 研究院的c i t e s e e r c i t e s e e 是一个非常有名的针对计算机科学领域论文的检索系统。c i t e s e e r 的 核心是a c i ( a u t o m a t i c a l l yc i t a t i o ni n d e x ) i 3 1 ，它可以自动地对网上的电子文件 ( p o s t s c r i p t 和p d f 等格式) 进行索引并分类。 4 基于概念搜索的a s kj e v e s 搜索引擎 a s k j e v e s 将用户提问转化为系统己知的问题，在对提问进行结构和内容分析 之后，或直接给出问题的答案，或引导用户从几个可选择的问题中进行再选择。 用户只需输入简单的疑问句，如“w h a ti st h em e a n i n go f ? ”，“h o wc a nid o ? ”， “w h e r ec a nia n d ”? 等句式就能直接获得结果。 中文主题搜索引擎的关键技术有中文分词和主题爬虫等。中文分词技术是中 文搜索引擎重要的组成部分，自从8 0 年代初中文信息处理领域提出中文分词以 来，中文分词研究全面兴起，取得了一些重要的进展和一些实用性的成果。专业 网络蜘蛛技术是垂直搜索引擎的关键部分，直接决定了主题搜索引擎的质量。专 业网络蜘蛛从9 0 年代中期的文本分类工作发展而来，到9 0 年代末已经成为一个 热点的研究领域。 1 3 选题背景及研究意义 中国是世界上灾害频发、受灾面广、灾害损失严重的国家。随着国民经济的 发展、生产规模的扩大和社会财富的增长，灾害造成的损失也逐年上升。近l o 年来，我国每年自然灾害造成的经济损失都在1 0 0 0 亿元以上，常年受灾人口达 2 亿人次。为了提高全社会防御各种灾害的能力，保证我国经济社会的可持续发 展，国家将进一步加大减灾事业的投入，实施国家减灾规划。为此，国内许多风 险防范方面的研究所、高校、政府部门等纷纷建立起自己的综合风险信息网站， 推进自然灾害综合风险防范的数字化、信息化建设，但是由于综合搜索引擎自身 的局限，综合风险主题信息的获取仍然十分困难。 通过本课题的研究，建成我国首个综合风险数据搜索与网络信息服务体系， 完成综合风险信息搜索引擎的开发以及综合风险网络服务体系的构建；建立面向 第一章绪论 具体风险防范的系统分析、模型结构和相应的可视化表达模型等技术支撑体系， 形成综合风险防范模拟仿真和决策支持的技术能力。为广大的综合风险防范工作 者、科研人员、民政部门以及林农提供快速准确的自然灾害风险信息，必将大大 推动我国自然灾害风险防范信息化工程的建设。 在风险主题搜索引擎系统中，负责信息搜集与更新的模块称为爬虫，面向风 险w e b 信息的主题爬虫的研究与实现，其目的就是研制在海量的网络信息中， 能有效识别与风险相关的w e b 信息资源并进行兰取和及时更新的系统，该系统 不仅可作为风险主题搜索引擎必要的信息获取模块，也可成为其它企业级信息应 用的网络数据来源。 1 4 本文的研究内容和论文结构 主题爬虫是主题搜索引擎的基础与核，t 二, f 4 1 ，本文主要研究了主题爬虫的相关 技术，针对风险主题搜索引擎提出的相关要求，完成了爬虫模块的研究与设计； 同时在索引的建立方法上提出了相应的改进思路。 论文结构安排如下： 第一章主要介绍了本论文的研究背景、主题搜索引擎的相关概念和工作原 理，课题的相关研究内容研究背景以及发展现状，并介绍了各部分所完成的工作。 第二章主要研究了主题爬虫的基本理论；深入分析了与爬虫相关的技术以及 他们的工作流程，分析和讨论了爬虫的几种常用搜索策略。 第三章重点研究和探讨系统中所要用到的关键算法，其中包括u r l 主题相关 性算法、页面主题相关性算法等。在此基础上结合实际情况进行选择和优化，提 出一种基于链接和基于内容相结合的算法，给出了风险主题爬虫系统的设计方 案。 第四章主要阐述了基于中文全文检索索引器的功能，组织结构图：一个索引 器应该包文本预处理模块，创建索引模块以及索引维护模块。论述了中文全文检 索索引设计的主要技术问题。给出了基于单字和改进倒排表索引的中文全文检索 索引器的设计方案和实现过程。 第五章主要介绍了风险主题爬虫的原型系统以及系统的相关技术实现细节。 4 第一章绪论 给出系统的实际应用过程和测试结果，通过对部分系统所采用算法进行的实验以 及对所开发的原型系统的整体性能测试，说明本文的工作是切实有效的。 第六章总结了系统的研究和开发经验，找到了一些不足之处，并分析了下一 步研究的方向。 第二二章主题搜索的相关理论和关键技术 第二章主题搜索的相关理论和关键技术 主题爬虫是主题搜索引擎的基础与核心。传统爬虫从一个或若干初始网页的 u r l 开始，获得初始网页上的u r l ，在抓取网页的过程中，不断从当前页面上 抽取新的u r l 放入队列，直到满足系统的一定停止条件。主题爬虫的工作流程 较为复杂，它根据一定的网页分析算法过滤与主题无关的链接，保留有用的链接 并将其放人等待抓取的u r l 队列。然后，它将根据一定的搜索策略从队列中选 择下一步要抓取的网页u r l ，并重复上述过程，直到达到系统的某一条件时停 止。通过它的工作使得下载的相关网页数量最大化，不相关网页数量最小化，极 大地提高了信息检索的查准率。 图2 1 主题爬虫的工作沉程 主题爬虫的设计思想是考虑对页面过滤，不像普通爬虫对所有页面的链接进 行处理，它先对页面与受限领城的主题相关度进行分析，只有当其主题相关度符 合要求时才处理该页面中的链接，因为如果该页面和本领域比较相关，它所包含 的链接和本领域相关的几率也较大，这徉提高了爬行精度，虽然会遗漏少数页面 但综合效果是令人满意。因此主题相关度的分析是主题爬虫设计的关键，最简单 的可以基于关键词进行分析，更深入的可以上升到语义和概念层次。 相对于通用一般的网络爬虫，主题网络爬虫需要解决三个基本问题i 5 】： 1 ) 对抓取目标的描述或定义； 6 第二章主题搜索的相关理论和关键技术 2 ) 对网页或数据的分析与过滤； 3 ) 对u r l 的搜索策略。 抓取目标的描述和定义是决定网页分析算法与u r l 搜索策略如何制订的基 础。而网页分析算法和候选u i 也排序算法是决定搜索引擎所提供的服务形式和爬 虫网页抓取行为的关键所在。这两个部分的算法又是紧密相关的。 2 1 主题爬虫的结构 主题爬虫的设计是以普通爬虫为基础，对其进行功能上的扩充，现在流行的 主题爬虫包括以下三个关键组成部分： 1 ) 页面相关度评价器。该模块主要特点是引入了文本分类的思想。在系统 爬行之初，页面相关度评价器根据用户输入的关键字和初始文本信息进行学习， 训练一个页面相关度评价模型。当一个被认为是主题相关的页面爬行下来之后， 该页面就被送入页面相关度评价器计算其主题相关度值，若该值大于或等于给定 的某阀值，则该页面就被存入页面库，否则丢弃。 2 ) 超链接评价器。该模块是主题爬虫的核心模块，计算从主题相关页面解 析出来的u r l 与主题的相关度，并提供相关的爬行策略用以指导爬虫的爬行过 程。u r l 的超链接评价得分越高，爬行的优先级就越高。反之，若通过一定的 评价策略，发现某链接与主题无关，则将该u r l 及其所有隐含的子链接一并去 除，这个过程我们称之为剪枝。剪枝的行为可能将潜在的与主题相关的页面也剪 掉。因此，超链接评价器所用的评价策略的好坏直接影响着爬虫的爬行效率以及 爬行质量。 3 ) 爬行器。该模块是任何爬虫都不可或缺的通用模块。该模块负责协调超 链接评价模块和页面相关度评价模块的工作。首先，爬行器从待爬行u r l 队列 中取出超链接得分最高的u r l ，将该u r l 相应的网页爬行到本地，然后，将该 页面交由页面相关度评价器处理。在整个爬行过程中，爬行的次序和爬行策略都 有超链接评价器提供。图2 2 为系统组成图： 7 第二章主题搜索的相关理论和关键技术 图2 2 主题爬虫系统结构图 不同的主题爬虫根据所采取的具体技术不同，以上三个模块的组成结构会有 所不同，但是三个模块的功能在主流主题爬虫中都会得到实现。 2 2 相关算法研究 在主题爬虫系统中，最核心的问题就是选择利用何种策略来判定从页面分析 中得到的u r l 与主题的相关性以及爬行下来的页面与主题的相关性。目前，相 关性判别算法的研究主要可以分为三个大类：1 ) 基于链接结构分析的判别：2 ) 基 于页面语义内容的判别；3 ) 基于网页标签信息的判别。本章的以下部分将重点介 绍在主题爬虫的设计和实现过程中会用到的关键算法及其思想。 2 2 1 基于链接分析的搜索算法 基于链接结构评价的搜索策略，是通过对w e b 页面之间相互引用关系的分 析来确定链接的重要性，进而决定链接访问顺序的方法。通常认为有较多入链或 出链的页面具有较高的价值。p a g e r a n k 和h i t s 是其中具有代表性的算法。 p a g e r a n k 算法基于链接评价的搜索引擎的优秀代表是g o o g l e ，它独创的“链 接评价体系”是基于这样一种认识：一个网页的重要性取决于它被其它网页链接 8 第二章主题搜索的相关理论和关键技术 的数量，特别是一些已经被认定是“重要 的网页的链接数量。p a g e r a n k 算法 最初用于g o o g l e 搜索引擎信息检索中对查询结果的排序过程1 6 1 ，近年来被应用 于网络爬虫对链接重要性的评价。 h i t s 方法定义了两个重要概念：a u t h o r i t y 和h u b 。a u t h o r i t y 表示一个权 威页面被其它页面引用的数量，即该权威页面的入度值。网页被引用的数量越大， 则该网页的a u t h o r i t y 值越大；h u b 表示一个w e b 页面指向其它页面的数量，即 该页面的出度值。网页的出度值越大，其h u b 值越高。由于h u b 值高的页面通 常都提供了指向权威页面的链接，因而起到了隐含说明某主题页面权威性的作 用。 2 2 。2 基于内容分析的搜索算法 基于内容评价的搜索算法【7 ，引，主要是根据主题( 如关键词、主题相关文档) 与链接文本的相似度来评价链接价值的高低，并以此决定其搜索策略。链接文本 是指链接周围的说明文字和链接u r l 上的文字信息。 基于内容评价的搜索算法根据语义相似度的高低决定链接的访问顺序。这类 方法起源于文本检索中对文本相似度的评价，它的显著优点是计算量比较小。但 是，因为w e b 页面不同于传统的文本，它是一种半结构化的文档，其中包含了 许多结构信息，w e b 页面不是单独存在的，页面中的超链接在一定程度上表示了 页面之间存在着某些关系。由于基于内容评价的网络爬虫忽略了这些信息，因而 在预测超链接的价值方面存在一些缺陷，容易造成网页的误选。此外，评价的准 确性也依赖于对主题关键词集合的选择和构建【9 】。 2 3 全文检索技术 全文检索是指计算机通过索引程序扫描文档中的每一个词，对每一个词建立 一个索引，指明该词在文档中出现的次数和位置。当用户进行查询时，检索程序 就根据事先建立的索引进行查找，并将查找的结果反馈给用户的检索方式。 全文检索的方法主要分为按字检索和按词检索2 种。按字检索是指对于文档 中的每一个字都建立索引，检索时将词分解为字的组合。 9 第二章主题搜索的相关理论和关键技术 全文检索系统是按照全文检索理论建立起来的用于提供全文检索服务的软 件系统。一般来说，全文检索需要具备建立索引和提供查询的基本功能，此外现 代的全文检索系统还需要具有用户接口、面向w w w 的开发接口、二次应用开发 接口等等【蚓。下面是一个全文检索系统的整体构造图： ： 鬻 涎塑 。f ：藿询引蘩。习。隐采螽珏弹弓i 蜜i ；检索命令习 ；：_ 翊蠹 话施一。栅。锄蕊矽 程。i 匿索雩i 弓l 擎( 索弓l 器j 。习 爱序，i i 搋i。一m 女绸 l 全文索引构造模型 从上可以看出，全文检索系统中最为关键的部分是全文检索引擎，各种 应用都需要建立在这个检索引擎之上。在检索引擎中可以看出索引引擎占据 了核位置，他是整个检索效率的重要决定因素，一个全文检索应用的优异程 度，上由全文检索引擎来决定。 2 他相关技术 2 1 向量空间模型 模型( v e c t o rs p a em o d l ，v s m ) 1 1 , 1 2 , 1 3 1 是关于文档表示的一个统计 模。空间模型基于这样一个关键假设：文章中词条出现的顺序是无关紧要的， 他们文档的类别所起的作用是相互独立的，因此可以把文档看作一系列无序 词条合【111。该模型以特征项作为文档表示的坐标，以向量的形式把文档表示 为多间中的一个点，特征项可以选择字、词、和词组等(根据实验结果，普 第二章主题搜索的相关理论和关键技术 遍认为选取词作为特征项要优于字和词组) ，表示向量中的各个分量。目前有许 多计算关键词权重的方法，s a l t o n 等在文献中给出了如下的计算公式【1 4 1 ： 对于关键词t ，其在文档i 中的权重定义为： w e i g h t ( t ，f ) = ，l g ( n n t )公式( 2 1 ) 其中，屯为关键词t 在文档i 中出现的频率，n 为信息库中文档的数目；n t 为整个文档信息库中包含词条t 的文档的个数；t i 为文档i 中所有关键词的个数。 从公式( 2 1 ) 可以得到，一个关键词在文档中出现的次数越多，其权重就越大； 一个关键词在整个信息库中出现的频率越少，其在出现的文档中的权重也越大。 经过公式( 2 1 ) 处理，一个文本可以表示为：d = d ( t l ，w l ；t 2 ，w 2 ；t n , w n ) 的形式， 即关键词t k 的权重为w k 。 在向量空间模型中，为了简化分析，减小计算量，通常忽略关键词在文本中 出现的先后次序，从而一个文本可以表示成经过关键词权重处理后的向量空间中 的一个向量。在获得了文档向量和主题向量后，就可以计算出文档向量与主题向 量之间的相似度，即主题相关度，主题相关度是通过向量间的内积计算得出： 行 s i m ( d ) = 水瓦 k = l 或者用向量夹角余弦表示： s i m ( d ) = c o s 0 = 公式( 2 2 ) 公式( 2 3 ) 其中，d 为关键词向量，t 为主题向量。向量空间模型可以很好地运用到主 题判别中，使得对关键词中的权重赋值成为可能。 2 4 2j a v a 多线程技术 通常情况下，一个程序的执行时间最多是花在等待上。例如等待i o 操作中 的某些资源变得可用才启动下一个任务，或者等待某个操作超时才做相应的处 乙 水 d 珂汹 第二章主题搜索的相关理论和关键技术 理。在爬虫程序访问w e b 时，它向w e b 服务器发出请求然后进入等待状态，直 到服务器响应请求并返回数据后，程序才能继续运行。采用多线程编程技术，可 让等待时间大大减少。多线程的特点在于一旦某个线程受阻( 出现等待情况) 时， 多线程程序就会随时选择另一个可执行的线程运行，使得c p u 资源能够得到充 分的利用。多线程的爬虫可以让每一个线程访问一个u r l ，在一个线程出现等 待的时候，其他线程还能够运行，故能成倍地加快信息采集的速度。 并行运算是合理有效地利用网络和机器资源的必要手段。多线程搜索是当前 搜索引擎用于提高采集效率普遍采用的方法。多线程技术应用的关键是保证各个 线程的独立运行和独立线程与系统的通信。 j a v a 语言的一个重要特征就是支持多线程的程序设计，它允许一个应用程序 拥有多个同时执行的线程。在风险主题爬虫的设计中，我们利用了j a v a 的这一 重要特性，实现了多线程搜索。 在j a v a 中，可以有两种方式实现多线程，一种是扩展t h r e a d 类，另一种时 实现r u n n a b l e 接口。 扩展t h r e a d 类，该类封装了线程的行为，以及创建和运行线程所需的一切 东西。要创建一个线程，只须创建一个从t h r e a d 类导出的新类，覆盖t h r e a d 的 r u n 函数来完成想要的工作。用户并不直接调用r u n 函数，而是调用t h r e a d 的s t a r t 函数，该函数对线程进行特殊的初始化，然后调用r u n 。这种方法c r a w l e r 类的 定义如下： p u b l i cc l a s sc r a w l e re x t e n d st h r e a d ； 第二种方法是实现r u n n a b l e 接口。r u n n a b l e 接口只有一个函数r u n ，此函数 必须由实现了此接口的类实现。一个类实现了r u n n a b l e 接口，并不意味着它具 有任何天生的线程处理能力，这与那些从t h r e a d 继承的类是不同的。所以为了 从一个r u n n a b l e 对象产生线程，必须单独创建一个线程，并为其传递r u n n a b l e 对象，然后调用那个线程的s t a r t 函数。这种方法比较简洁，不会增加类层次， 而且还可以通过将主程序类变成一个线程，将线程类与主程序类合并到一起。 1 2 第二章主题搜索的相关理论和关键技术 2 5 本章小结 本章主要研究了爬虫的基本理论，阐述了主题爬虫的原理和结构。深入分析 和讨论了主题爬虫的核心问题主题相关度计算的两类算法。简要介绍了信息索 引技术和爬虫设计中的其他相关技术。 1 3 第三章风险主题爬虫的设计 第三章风险主题爬虫的设计 3 1 风险主题搜索策略 风险主题搜索策略是指在w e b 信息搜索过程中尽量优先搜索与风险主题相 关的信息以及最终搜索信息的风险主题相关性。在第二章中我们讨论了目前常用 的主题搜索爬行策略：基于内容评价的搜索策略和基于w e b 链接结构的搜索策 略。基于内容评价的搜索策略以f i s h 及s h a r k 为代表，其优点是具有较好的理论 基础且计算简单。但由于这类方法忽略了链接结构信息，因而在预测链接价值的 准确性方面存在一些不足。基于w e b 链接结构的搜索策略以p a g e r a n k 和h i t s 为代表，通过分析w e b 页面之间的相互引用关系来确定网页的重要性，进而决 定链接访问顺序。该方法虽然考虑了链接结构和页面之间的引用关系，但忽略了 页面与主题的相关性，在某些情况下，h i t s 会出现搜索偏离主题的“主题漂移” 问题；而p a g e r a n k 算法只适合于发现权威网页，不适合于发现主题资源。在本 章中将详细讨论相关算法以及对算法的修改设计与实现，并将其运用到风险主题 搜索引擎的设计当中。 3 1 1 搜索策略详细分析与对比 基于内容评价的搜索策略，主要是根据主题( 如关键词、主题相关文档) 与 链接文本的相似度来评价链接价值的高低，并以此决定其搜索策略。不同类型的 信息各自构成不同的策略和算法。主要的策略有以下几种【1 5 1 6 ，1 7 ，1 8 1 ： 1 ) b e s tf i r s ts e a r c h 此算法的基本思想是：给定一个待爬行的u r l 队列，从中挑选优先级最高的 u r l 进行爬行。爬行主题一般由关键字组合表示，u r l 权值由其网页内容与关 键字的相关度来确定。相关度大的网页，它的优先级就高，以此来确定u r l 队 列的爬行次序。如果u r l 队列缓冲区满，就将优先级最低的网页节点移除。 1 4 第三章风险主题爬虫的设计 s i m ( u ，v ) = 厶厶 公式( 3 1 ) k s u n v 其中，u 表示主题，v 表示所抓取的网页，如表示词k 在u 中出现的频次， 表示词k 在v 中出现的频次。b e s t f i r s ts e a r c h 算法的伪代码如下： b e s t f i r s t s e a r c h ( s t a r t i n gu r l s ，t o p i c ) e n q u e u e ( u r l _ q u e u e ，s t a r t i n g _ u r l s ) ；将起始站点u r l 全部压栈 i n tn u m v i s i t e d = 0 ； w h i l e ( n u m v i s i t e d m a x _ b u f f e r ) d e q u e u e _ b o t o m _ l i n k s ( u r l _ q u e u e ) ； ) r e o r d e r _ q u e u e ( u r l _ q u e u e ) ； e n do fw h i l e ( u r lq u e u e ) 该算法维护两个队y 1 u r l _ q u e u e 和c r a w l e d _ q u e u e ，分别用来存放待爬行u r l 和己爬行u r l 。程序运行时，先将初始u r l 放入u r l _ q u e u e 中，通过公式( 3 1 ) 计算出优先级最高的u r l 进行爬行，并将该u r l 放入c r a w l e d _ q u e u e 。将爬行 下来的网页通过锚文本和( 或) 链接信息计算相似度，并根据该相似度值将从该页 第三章风险主题爬虫的设计 面中解析出来的相应链接插入u r l - q u e u e 。循环该操作，直到系统访问的网页数 超过最大页面数或者u r lq u e u e 中无u r l 。 这种算法的优点是计算量较小，对宽泛主题比较有用。但在关键字很多的情 况下，由于锚文本和链接信息不能很好地反映页面主题，导致效果不佳。也容易 使算法过早陷入w e b 搜索空间中局部最优子空间的陷阱，从而导致整体回报率 不高f 1 9 】。 2 ) f i s hs e a r c h f i s hs e a r c h 算法于1 9 9 3 年由荷兰t u e 大学的d e b r a 教授提出，并整合到了 当时流行的m o s a i c 浏览器上，是实时搜索中比较有名的算法【2 0 l 。 该算法的关键是根据用户的种子站点和查询的关键词或短语，将包含查询串 的页面看作与主题相关，计算该页面与主题的相关度，动态地维护待爬行u r l 的优先级队列u r l 。这个队列分为前端，中部和尾部三部分，另外还需_queue 要几个参数：d e p t h ，w i d t h 和p o t e n t i a l _ s c o r e ，分别用于记载被搜索网页的层深、 每页最多分析的链接数目( 在此，称其为孩子数) 和u r l 的相关度。这个算法的 基本思想是：它以一个u r l 为起始搜索网页，在搜索这个u r l 的基础上动态的 建立一个列表，这个列表中包含有待搜索的u r l 。这个列表中的u r l ( 吕p 孩子链 接) 具有优先级的区分，优先级高的u r l 将排在列表中的前端，将会比排在列表 后面的u r l 提前被搜索。在每一步开始时，取出列表中的第一个u r l 进行分析。 如果该网页可以访问，则经过分析对它的p o t e n t i a ls c o r e 赋值，并改变其相应的 d e p t h 和w i d t h 值，然后再重新进行下一个u r l 的检索。 f i s hs e a r c h 算法的具体描述如下： ( 1 ) 从最初的u r l 列表中选择u r l ，并取得与之对应的网页文件，将这个文 件与用户的查询内容对比，检查二者的相关性。 ( 2 ) 给每个u r l 赋相应的d e p t h 值。如果这个文件是相关的，那么这个文件 中所出现的u r l 的p o t e n t i a ls c o r e 将被赋值为1 ，并获得一个最初设定的d e p t h 值。如果这个文件不相关，那么将这个文件中出现的u r l 的p o t e n t i a l赋值scote 为0 5 或0 两种值，获得的d e p t h 值将减少，具体赋值情况如( 3 ) 0 0 维护方法所述。 o ) 将此文件中的u r l 按下面的方法加入到u r l 列表中f 2 l 】。 如果这个文件相关，则把这个文件前a w i d t h 个孩子( a 是预定义的大于1 1 6 第三章风险主题爬虫的设计 的常量) j i a 至4 4u r l _ q u e u e 的前端。 如果这个文件不相关，则把这个文件前w i d t h 个孩子的u r l 加入到 u r l _ q u e u e 队列中紧挨着相关网页的孩子节点后砸。 剩下的孩子u r l 加入到u r l _ q u e u e 的尾部( 也就是说只有在时间允许的 情况下才有可能被爬行) 。 ( 4 ) 在获取文件的时候，对w e b 服务器的传输速度进行监测，如果速率很低， 则将文件中的u r l 的d e p t h 设为0 。 ( 5 ) 在经过一段特定的时间之后，或u r l _ q u e u e 己为空时，停止运行。 算法伪代码如下【1 5 1 ： f i s hs e a r c h ( s t a r t i n j p r l s ，t o p i c ，w i d t h ，d