（计算机系统结构专业论文）垂直搜索引擎的研究与设计.pdf

摘要 摘要 由于通用搜索很难满足个性化和专业化的需求，垂直搜索应运而生。垂直搜 索能提供给人们更相关的信息。本文对中文垂直搜索中的几个关键技术进行论述， 并设计实现了一个简单的检索系统，包括网络爬虫、网页提取、中文分词、索引 检索等，各个部分相互关联构成一个有机的整体。 提出了基于实验学习和聚集爬虫的u r l 规则学习算法。算法的核心是u r l 规 则表达式学习，它能自动从样本网页中学习和产生规则表达式。主要包括以下几 个部分：u r l 抽取、试验学习、分类判别、规则学习；从u r l 中发掘出链接与主题 之间的相关性，以此作为判断u r l 是否抓取的依据。重新设计了词典机制和查询 算法，我们采用了双字h a s h 加逐字二分的词典机制，综合利用网络文本和搜索提 交的关键词来识别新词，并对网页信息抽取做了论述。 设计并实现了一个简单的搜索引擎，给出了系统的总体结构图，并对各个工 作流程进行了详细的描述，最后对系统的使用效果和性能进行了简单评测。 关键词：垂直搜索，网络爬虫，中文分词，结构化提取 a b s t r a c t a b s t r a c t d u et oi n d i v i d u a la n dp r o f e s s i o n a ln e e d s ，t h eg e n e r a l p u r p o s es e a r c he n g i n ec a n n o ts a t i s f yt h er e q u i r e m e n t i tr e s u l t e di nt h en a i s s a n c eo fv e r t i c a ls e a r c he n g i n e t h e v e r t i c a ls e a r c he n g i n e sc a l ld e l i v e rm o r er e l e v a n tr e s u l t st os a t i s f yu s e r s r e q u i r e m e n t w e f o c u s e do ns e v e r a lk e yt e c h n o l o g i e sa b o u tc h i n e s ev e r t i c a ls e a r c he n g i n ei nt h i st h e s i s ， a n di m p l e m e n tas i m p l es e a r c he n g i n e , i n c l u d i n gs p i d e r , w e be x t r a c t i o n ，c h i n e s ew o r d s e g m e n t a t i o n ，i n d e x e r t h ev a r i o u sp a r t sa r ei n t e r r e l a t e dw i t he a c ho t h e r w ep r o p o s ea nu b f c ( u r lr u l eb a s e df o c u s e dc r a w l e r ) a l g o r i t h mb a s e do na n e x p e r i m e n t a lc r a w l e ra n da f o c u s e dc r a w l e r t h ek e r n e lo fo u ra l g o r i t h mi s 锄u r l r e g u l a re x p r e s s i o nl e a r n e r , w h i c hi su s e dt oa u t o m a t i c a l l yl e a r na n dg e n e r a l i z et h e r e g u l a re x p r e s s i o n so f u r l so ft h es a m p l ew e b p a g e s i n c l u d i n gt h ef o l l o w i n gs e c t i o n s ： u r l f i l t e r , p i l o ts t u d y , c l a s s i f i c a t i o ni d e n t i f i c a t i o n , r u l el e a r n i n g ； w ee x c a v a t e dt h e c o r r e l a t i o nb e t w e e nt h es u b j e c ta n dl i n k si no r d e rt oj u d g ew h e t h e rt h eu r l c r a w l e d r e d e s i g n t h e d i c t i o n a r y m e c h a n i s m a n d q u e r y a l g o r i t h m s ，t h e d o u b l e c h a r a c t e r - h a s h - i n d e x i n g a n dv e r b a t i m d i c h o t o m ys e g m e n t a t i o nd i c t i o n a r y m e c h a n i s m si sp r o p o s e di nt h i st h e s i s w eu s ew e bp a g ec h a r a c t e r i s t i ca n ds u b m i t t e d k e y w o r d st or e c o g n i t i o n sn e ww o r d w ep r o p o s e sa m e t h o dt oc o n t e n te x t r a c t i o nf r o m w e b p a g e s w ed e s i g na n di m p l e m e n tas i m p l es e a r c he n g i n e t h eg l o b a ls 岫k ：t l l 代o f0 1 1 1 s y s t e ma n dr e l a t i o n so ft h ec o m p o n e n t so fs y s t e ma l ei n t r o d u c e d s o m ec o m p o n e n t sa 佗 d e t a i l e di nf u n c t i o na n di m p l e m e n t a t i o n f i n a l l yas i m p l ee v a l u a t i o na b o u ts e a r c h i n g e f f e c ta n dp e r f o r m a n c ei sg i v e n 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 ，s p i d e r , c h i n e s ew o r ds e g m e n t a t i o n , e x t r a c t i o n i n f o r m a t i o n l l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：硅到 日期：少雩年于即日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：丕刭丝导师签名：叁翌 日期：趴哆年3 - 月日 第一章引言 1 1 相关背景 第一章引言 随着互联网的普及和不断发展，现今我们的生活已经离不开网络，据市场调 查公司b d a 估计，按照网民数量计算中国已经超过美国成为世界最大的互联网市 场。 0 2 0 0 5 0 62 0 0 5 1 22 0 0 6 0 62 0 0 6 1 22 0 0 7 0 6 2 0 0 7 1 2 2 0 0 8 0 6 ( n ( w w w c n n i c c n 2 0 0 8 0 6 图1 1 我国网民增长图 中国互联网协会发布网站流量分析报告n 1 。报告对中国网民访问网站行为 作了抽样分析，结果显示，绝大部分的中国网民经常访问搜索引擎类网站和新闻 类网站。其中，有2 9 0 3 的抽样网民经常访问搜索引擎类网站，2 2 1 5 的抽样网 民经常访问新闻类网站，此二类网站形成了中国网民经常访问网站的第一阵营。 搜索引擎是网民在互联网中获取所需信息的重要工具，是互联网中的基础应用。 根据c n n i c 的报告显示目前搜索引擎的使用率为6 9 2 。即时通信、搜索引擎和电 子邮件三大互联网基础应用也位列前十，使用率均超过6 0 。报告显示用户对搜索 引擎的依赖较高，每次上网都要用到多次搜索的比例达4 4 2 ，接近一半。搜索 引擎服务能成为最受欢迎的服务是因为它解决了用户在浩瀚的互联网海量信息中 快速定位信息的瓶颈问题。 观察国外的情况，搜索引擎是美国的第二大网络应用，使用率已经达到9 1 。 3 2 2 1 1 0 0 电子科技大学硕士学位论文 根据中国互联网络信息中心( c n n i c ) 的研究，网民学历越高，搜索引擎使用率就 越高。学历在本科及以上的网民中，搜索引擎使用率已经超过9 3 。 搜索引擎整合了众多网站信息，恰恰起到了信息导航的作用。通用搜索引擎 就如同互联网第一次出现的门户网站一样，大量的信息整合导航，极快的查询， 将所有网站上的信息整理在一个平台上供网民使用，于是信息的价值第一次普遍 的被人们所认可，迅速成为互联网中最有价值的领域。互联网的低谷由此演变为 第二次高峰。大家熟知的搜索引擎g o o g l e h 引、百度3 等是搜索引擎现今的杰出代 表。 由于通用搜索引擎是针对所有的用户群，信息量大、查询不准确、深度不够 等特点使得它并不能满足人们某一特定领域、某一特定人群或某一特定需求提供 精准化信息服务。垂直搜索有如燎原星火般迅速发展起来。垂直搜索细分了用户 的需求，它将逐步帮助用户认识到“精准才是好”的理念。以前是“阅读尽可能 多的信息”，现在是“将有限信息作用于实践的效率最大化”，拥有再多的垃圾信 息也是无济于事，重要的是在用最短的时间找到最准确的对实践有帮助的信息阻。 1 1 垂直搜索概述 由于通用搜索的上述一些问题，垂直搜索如雨后春生般的兴起。垂直搜索【2 l 】 是针对某一个行业的专业搜索引擎，是搜索引擎的细分和延伸，是对网页库中的 某类专门的信息进行一次整合，定向分字段抽取出需要的数据进行处理后再以某 种形式返回给用户。 垂直搜索引擎和普通的网页搜索引擎的最大区别是对网页信息进行了结构化 信息抽取，也就是将网页的非结构化数据抽取成特定的结构化信息数据，好比网 页搜索是以网页为最小单位，基于视觉的网页块分析是以网页块为最小单位，而 垂直搜索是以结构化数据为最小单位。然后将这些数据存储到数据库，进行进一 步的加工处理，如：去重、分类等，最后分词、索引再以搜索的方式满足用户的 需求。 整个过程中，数据由非结构化数据抽取成结构化数据，经过深度加工处理后 以非结构化的方式和结构化的方式返回给用户。 垂直搜索引擎的应用方向很多，比如供求信息搜索引擎、购物搜索、房产搜 索、职位搜索、地图搜索、音乐搜索、图片搜索几乎各行各业各类信息都可 以进一步细化成各类的垂直搜索引擎。 2 第一章引言 举个例子来说明会更容易理解，比如购物搜索引擎，整体流程大致如下：抓 取网页后，对网页商品信息进行抽取，抽取出商品名称、价格、简介等，甚至可 以进一步将电脑简介细分成“品牌、型号、c p u 、内存、硬盘、显示屏、oo 然 后对信息进行清洗、去重、分类、分析比较、深度挖掘，最后通过分词索引提供 用户检索。 下面从垂直搜索的特征，关键技术分别介绍。 1 1 1 垂直搜索的特征 正因为垂直搜索面对的用户群，处理的数据对象方面与通用搜索的差别，所 以有其自身的特征，人们归纳出垂直搜索有别于通用搜索的几大特征如下： 处理一个特定数据领域或对象 垂直搜索可以按照领域划分为求职、房产、旅游、餐饮，博客等，也可以 按照对象分为机构、产品、地域，图片，文献，职位等，而且这可能是多维交 叉的。垂直搜索都是针对一个领域或者一个对象，通常就是和行业相关，比如 现实中的旅游业，汽车业，就业市场等，同时这个行业的网上信息有一定的数 量和集中，而不是少而分散，然后在领域中选定对象，展开搜索。如果不划定 领域的话，一个对象往往会散布在整个互联网中，尽管和该对象有关的信息只 是很少的一部分，但同样要像通用搜索一样爬全网，这个开销太大。 满足用户某一方面的需求 不管是哪个领域的垂直搜索都是从内容的角度看的，从需求的角度看，垂 直搜索的用户是有特定需求的。以汽车为例，主要需求有：购车，用车，修车， 转让二手车，选驾校，选店等；还比如旅游搜索要么就是旅游目的地的相关信 息，要么就是旅游地机票酒店信息，要么就是游记等；垂直搜索当然也不可能 满足用户的全部需求，应该选定某种特定的需求，比如“购车，结合行业特 色深入地做下去，充分地满足这种需求，然后再向其他需求推进。 搜集内容全面 垂直搜索受限到特定领域，就要把这个领域的信息尽可能都收集全，比如 在收集动态网页方面要求很高。如果还像通用搜索一样垂直搜索就没存在的价 值。 处理数据深入 通用搜索由于涉及的互联网上所有方面的网页，所以没办法做的深入。垂 电子科技大学硕士学位论文 直搜索可以不断地积累自己的行业背景知识，比如聘请行业的专家，然后利用 自然语言处理和数据挖掘等手段，挖掘信息之间的关联和趋势，给用户提供可 以用来指导实践，解决问题的“知识”，从而达到“深”的效果。这是垂直搜 索超越通用搜索的一个关键点。 反馈准确 在搜索收录的分析过程中，由于加上了行业特点和特性进行分析，能更准 确分析到网页的重要性。因此垂直搜索的结果也有更好的相关性。另外，由于 有领域知识的支持，用户的需求又比较集中，因此可以给出更准确的检索结果。 信息收集及时 通用搜索由于涉及到太多的信息要收集与处理，在时效性方面就很难满足 要求，但网上有些信息具有很强的时效性，过期了就没什么用了，比如当天的 火车票信息。还比如房产信息，时效性很强，不能总把所谓最相关内容的排在 最前面，因为内容是相关，但可能已经过时了。垂直搜索的搜索范围小，也为 快速抓取，及时更新创造了条件。 数据集的结构化 垂直搜索要利用信息抽取技术把网页打碎，从中提取出精细化、条目化的 信息，存放到数据库中。这种做法一方面可以大幅度地减少用户获取信息的速 度，另一方面在数据库中可以方便地进行深层的归并、统计、挖掘等，非结构 化信息的结构化是垂直搜索的关键一步。目前，各垂直搜索企业往往通过针对 各个网站的网页结构分别用人工书写模板的方式抽取信息，随着采集量的增 加，基于自然语言处理技术的自动信息抽取方法将逐渐发挥更重要的作用。此 外，有些信息在内容网站上已经以结构化方式存在的，可以直接加以整合。 1 1 2 垂直搜索的关键技术 由于垂直搜索引擎服务具有其自身的特性，因此其技术要求与通用搜索有很 多不同之处，通过和通用搜索的比较，国内最大的搜索引擎技术提供商t r s 公司 列举出了垂直搜索引擎的四大关键技术。 ( 1 ) 聚焦、实时和可管理的网页采集技术：一般互联网搜索面向全网信息，采 集的范围广、数量大，但往往由于更新周期的要求，采集的深度或说层级比较浅， 采集动态网页优先级比较低，因而被称为通用搜索，通用搜索以被动方式为主， 搜索引擎和被采集的网页没有约定的、标准的格式。而垂直搜索带有专业性或行 4 第一章引言 业性的需求和目标，所以只对局部来源的网页进行采集，采集的网页数量适中。 但其要求采集的网页全面，必须达到更深的层级，采集动态网页的优先级也相对 较高。在实际应用中，垂直搜索的网页采集技术能够按需控制采集目标和范围、 按需支持深度采集及按需支持复杂的动态网页采集，即采集技术要能达到更加聚 焦、纵深和可管控的需求，并且网页信息更新周期也更短，获取信息更及时。垂 直搜索采用被动和主动相结合的方式，通过主动方式，有效采集网页中标引的元 数据，整合上下游网页资源或者商业数据库，提供更加准确的搜索服务。 ( 2 ) 从非结构化内容到结构化数据的网页解析技术：通用搜索引擎仅能对网 页的标题和正文进行解析和提取，但不提供其时间、来源、作者及其他元数据的 解析和提取。由于垂直搜索引擎服务的特殊性，往往要求按需提供时间、来源、 作者及其他元数据解析，包括对网页中特定内容的提取。比如：在论坛搜索、生 活服务、订票服务、求职服务、风险信用、竞争情报、行业供需、产品比较等特 定垂直搜索服务中，要求对于作者、主题、地区、机构名称、产品名称以及特定 行业用语进行提取，才能进一步提供更有价值的搜索服务。 ( 3 ) 精、准、全的全文索引和联合检索技术：通用搜索引擎并不能提供精确 和完整的检索结果，只是给出预估的数量和排在前面部分的结果信息，但响应速 度是通用搜索引擎所追求的最重要因素；在文本索引方面，它也仅对部分网页中 特定位置的文本而不是精确的网页正文全文进行索引，因而其最终检索结果是不 完全的。垂直搜索由于在信息的专业性和使用价值方面有更高的要求，因此能够 支持全文检索和精确检索，并按需提供多种结果排序方式，比如按内容相关度排 序( 与通用检索的p a g e r a n k 不同) 或按时间、来源排序。另外，一些垂直搜索引擎 还要求按需支持结构化和非结构化数据联合检索，比如结合作者、内容、分类进 行组合检索等。 ( 4 ) 高度智能化的文本挖掘技术：垂直搜索与通用搜索的最大区别是它对网 页信息进行了结构化信息抽取加工，也就是将网页的非结构化数据抽取成特定的 结构化信息数据，好比网页搜索是以网页为最小单位，基于视觉的网页块分析是 以网页块为最小单位，而垂直搜索是以结构化数据为最小单位。基于结构化数据 和全文数据的结合，垂直搜索才能为用户提供更加到位、更有价值的服务。整个 结构化信息提取贯穿从网页解析到网页加工处理的过程。同时面对上述要求，垂 直搜索还能够按需提供智能化处理功能，比如自动分类、自动聚类、自动标引、 自动排重、文本挖掘等等。这部分是垂直搜索乃至信息处理的前沿技术，虽然尚 不够成熟，但有很大的发展潜力和空间，并且目前在一些海量信息处理的场合已 电子科技大学硕士学位论文 经能够起到很好的应用效果。 1 2 垂直搜索现状 垂直搜索的应用都是最近几年的事，随着通用搜索的成功并且给人们带来了 很大的便利，以娱乐方面的垂直搜索应用为开始，后面商业、生活、旅游等应用 应运而生，旅游搜索、地图搜索、社区搜索、房产搜索、比较购物搜索等新型的 垂直搜索服务模式开始发展。综合型搜索引擎会增加服务的细分性和层级性，以 加强对用户的吸引。如音乐类搜索方面，就集中了百度、搜狗等多家综合搜索引 擎。搜索已经不再只是单纯地搜索网站页面，而是越来越细化，越来越有针对性。 专业搜索服务越来越受到大家的欢迎，也是各大搜索引擎公司的重点。 垂直搜索最初很多是模仿通用搜索出来的，与通用搜索的区别主要在结构化 信息抽取上面，以结构化数据为最小单位。然后将这些数据存储到数据库，进行 进一步的加工处理，如：去重、分类等，最后分词、索引再以搜索的方式满足用户 的需求。在这个过程中垂直搜索比通用搜索更多的人工干预。 由于自然语言处理和人工智能没有取得突破性进展，与通用搜索一样，垂直 搜索仍然没有取得革命性的进步。大多数垂直搜索企业都在做更细致化的工作， 比如构造更大更专业的领域词典，半自动化的模板，及时的抓取。 垂直搜索与具体领域的结合还处在初步发展的阶段。同时搜索与社区，搜索 与门户的结合越来越紧密。垂直搜索在行业中也更多的作为一种工具。 1 3 本文所做的工作 本文的工作主要集中在研究垂直搜索引擎。介绍了搜索引擎相关的一系列技 术，并着重在研究和提出了中文分词与新词识别一体化和网页结构化提取技术， 最后利用基于上面的的方法设计和实现了一个初步的系统。本文重点在以下几个 部分： 我们针对垂直搜索的特殊性专门分析爬虫部分，提出了u r l 规则学习器的专 用网络爬虫。在具体主题的抓取的实验中取得了很好的效果。 对网页的结构化提取部分，由于垂直搜索只专注于一部分网页，这一部分网 页的网页特征又有许多共同的特征，我们首先根据特征提取出模板，然后根据模 板抽取网页并不断的学习。 6 第一章引言 中文分词模块设计了词典机制和查询算法，其中对于中文分词模块结合了网 页的特征和新词识别来更有效的处理网页内容。 最后进行总结并说明以后的方向。 7 电子科技大学硕士学位论文 第二章垂直搜索概要设计和网络爬虫技术 2 1 系统简介 统： 在介绍一系列垂直搜索引擎中涉及到的基本技术前，我们描述一个初步的系 图2 1 系统整体架构 整个系统由以下几部分组成： ( 1 ) 抓取网页信息 首先需要专用爬虫自动的去网上搜集信息，我们预先指定几个抓取的起始点， 然后由爬虫去爬取相应的网页；分析网页的相关度看是否是属于相关主题的网页， 若是就保存进原始网页库；有网页解析程序解析网页并提取其中的链接信息放入 u r l 库，这个过程中还需要判重。爬虫程序继续从u r l 库中提取链接信息继续上面 8 第二章垂直搜索概要设计和网络爬虫技术 的过程，直到u r l 库为空为止。 ( 2 ) 处理网页，建立索引库 为了方便用户快速查询，需要对网页进行预处理，网页预处理的第一步就是 为原始网页建立索引，有了索引就可以为搜索引擎提供网页快照功能；接下来针 对索引网页库进行网页切分，将每一篇网页转化为一组词的集合；最后将网页到 索引词的映射转化为索引词到网页的映射，形成倒排文件，同时将网页中包含的 不重复的索引词汇聚成索引词表。 ( 3 ) 用户检索及日志处理 用户提交关键字后，系统从索引库中快速的检索关键字得到文档集合，然后 根据相关性排序算法对文档进行排序后返回给用户。用户的检索信息记入日志文 件。 搜索引擎涉及到的技术相当广泛，包括快速和实时抓取，海量数据的存储与 处理，自然语言处理，索引的建立与动态维护，用户的及时访问，结果的排序等， 每一项都有很高的技术含量。这些技术又相互关联，有机的构成一个整体。本章 就垂直搜索中网络爬虫做介绍与分析，下一章将详细叙述中文分词与结构化提取 技术。 2 2 网络爬虫基本原理 2 2 1 网络爬虫概要 爬虫是一个自动抓取网页的程序，它为搜索引擎从互联网上爬取网页，是搜 索引擎的重要组成部分。传统爬虫从一个或若干初始网页的u r l 开始，获得初始 网页上的u r l ，在抓取网页的过程中，不断从当前页面上抽取新的u r l 放入队列， 直到满足系统的一定停止条件。垂直搜索爬虫的工作流程较为复杂，需要根据一 定的网页分析算法过滤与主题无关的链接，保留有用的链接并将其放入等待抓取 的u r l 队列。然后，它将根据一定的搜索策略从队列中选择下一步要抓取的网页 u r l ，并重复上述过程，直到达到系统的某一条件时停止。另外，所有被爬虫抓取 的网页将会被系统存贮，进行一定的分析、过滤，并建立索引，以便以后的查询 和检索，这一过程所得到的分析结果还可能对以后的抓取过程给出反馈和指导。 相对于通用网络爬虫，垂直搜索爬虫还需要解决三个主要问题： ( 1 ) 对抓取目标网页的描述；( 2 ) 对网页的分析与过滤；( 3 ) 基于u r l 的搜索 9 电子科技大学硕士学位论文 策略。 抓取目标网页的描述和定义是决定网页分析算法与u r l 搜索策略如何制订的 基础。而网页分析算法和候选u r l 排序算法是决定搜索引擎所提供的服务形式和 网页抓取行为的关键所在。这两个部分的算法又是紧密相关的。对u r l 搜索策略 在后面的章节有专门的论述，下面主要说明抓取目标和网页搜索策略。 2 2 2 抓取目标的描述 垂直搜索不像通用搜索那样抓取网上所有的页面而是选择一部分搜集，所以 要对搜索目标进行定位。垂直搜索爬虫对抓取目标的描述可分为基于目标网页特 征、基于目标数据模式和基于领域概念三种。 1 )基于目标网页特征的爬虫所抓取、存储并索引的对象一般为网站的网页。 根据种子样本获取方式可分为：预先给定的初始抓取种子样本，预先 给定的网页分类目录和与分类目录对应的种子样本，分类结构，通过 用户行为确定的抓取目标样例等。 2 )基于目标数据模式就是想人工确定一些相关的数据模式，然后在网页抓 取时进行目标判断。 3 )基于领域概念就是利用本体论的知识，采用专家建立的相关领域的本体 进行发掘，现在应用还有难度。 2 2 3 网页搜索策略 网页的抓取策略可以分为深度优先、广度优先和最佳优先三种。深度优先在 很多情况下会导致爬虫的陷入问题，目前常见的是广度优先和最佳优先方法。 广度优先搜索策略 广度优先搜索策略是指在抓取过程中，在完成当前层次的搜索后，才进行下 一层次的搜索。该算法的设计和实现相对简单。在目前为了覆盖尽可能多的网页， 一般使用广度优先搜索方法。也有很多研究将广度优先搜索策略应用于垂直搜索 爬虫中。其基本思想是认为与初始u r l 在一定链接距离内的网页具有主题相关性 的概率很大。另外一种方法是将广度优先搜索与网页过滤技术结合使用，先用广 度优先策略抓取网页，再将其中无关的网页过滤掉。这些方法的缺点在于，随着 抓取网页的增多，大量的无关网页将被下载并过滤，算法的效率将变低。 深度优先搜索策略 1 0 第二章垂直搜索概要设计和网络爬虫技术 与广度优先相对应，在搜索网页时由一个链接走到底，无法抓取时再回退。 最佳优先搜索策略 最佳优先搜索策略按照一定的网页分析算法，预测候选u r l 与目标网页的相 似度，或与主题的相关性，并选取评价最好的一个或几个u r l 进行抓取。它只访 问经过网页分析算法预测为“有用的”网页。存在的一个问题是，在爬虫抓取路 径上的很多相关网页可能被忽略，因为最佳优先策略是一种局部最优搜索算法。 因此需要将最佳优先结合具体的应用进行改进，以跳出局部最优点。 2 2 4 大型网络爬虫的问题 在介绍了上面的一些基本理论后，下面谈下在设计大型网络爬虫时要注意和 解决的一些问题。 多线程的调度 为了有效的利用网络带宽和主机资源，一般网络爬虫都实现为多线程方式， 多线程间的调度处理问题需要考虑，使其不会出现互相等待或者重复处理。可以 把页面进行水平分割，每个线程处理一段，这样每个线程之间不需要同步，各自 处理各自的就行了。但对于抓取同一个网站的网页来说最好一个线程去抓取，因 为可以更充分利用链接资源，高版本h t t p 协议可以保持连接。 重复网页的问题 通过分析工p 地址与域名的关系，总结出哪些主机名有同义关系，从而避免了网 页的重复获取n 引。 动态网页的抓取 由于动态网页访问大多需要权限，搜索引擎大多模拟游客身份进入，所以很 多信息搜索引擎没法获取。现在论坛和社区作为人们上网互动的主要场所，会丢 失很多重要的信息 网页的保存 抓下来的页面的保存问题，是保存到分布式文件系统还是保存在数据库里， 如果保存到磁盘，可以每个域名创建一个文件夹，凡是这个网站的页面都放到这 个文件夹下，只要文件名不一样，就不会出现冲突。一般频繁的写磁盘可能会引 起c p u 过高，而频繁的写数据库c p u 还好一些，其中对于海量网页的存储问题文 献 1 9 给出了详细的论述。 抓取的时间间隔 电子科技大学硕士学位论文 如果要抓的网页支持l a s r - m o d i f i e d 或e t a g 头，我们可以先发个h e a d 请求来 试探这个页面有没有变化来决定是否要重新抓取，但是好多网站并不支持。这样 我们就要自己去标注每个源页面的更新时间间隔及权重，再根据这两个值去用一 定的算法制定爬虫的更新策略。 2 3 垂直搜索中的网络爬虫技术 由于垂直搜索的特殊性，除了上面通用搜索的一些特点外还有自身的一些特 点。垂直搜索只关心那些与一个具体领域相关的网页，所以在抓取的时候需要判 断，我们主要根据u r l 进行分析判断页面的相关性。 2 。3 1 相关的工作 在爬虫选择算法上人们已经做了很多工作。早期研究人员通过对网页中超连 接分析来计算页面的重要性。例如，j u n g o oc h o 提出的p a g e r a n k 算法来评价网页。 但这种算法并没考虑到网页与网页主题之间的相关性。结果就可能漏掉很多与主 题相关的网页，有时可能只爬到很少与主题相关的页面。所以对网页的主题相关 性考虑对爬行算法很重要。d a v i s o n 用t f i d f 向量空间模型对1 0 0 0 0 0 个页面进行 分析，提出了“主题领域 的概念，也就是说二个网页有超链接指向的话这二个 网页就有高的相关性。后来人们用他的思想做了很多试验，发现一个网页与主题 相关时他所包含的超链接所指向的网页与主题相关性也很大。那么爬虫就可以利 用这一点就很容易找到同一个主题的页面。 后来m c c a l l u m 等人发现采用上述算法容易出现一种“主题孤岛啪抑现象。后 来研究人员又试着采用另二种方法来改进爬虫。例如，m e t a s e a r c h 采用的是使用 通用网络爬虫的同时结合种子u r l s ，c o o p e r a t i o nc r a w l e r s 则是找到用户的阅读 习惯然后针对性的改变算法，但这些都没有本质的提高b 5 1 。 2 3 2 基于u r l 规则的爬虫算法 基本规则：现今网上很多网页都是动态生成的，特别是与一个领域相关的实 时信息更是如此。动态生成的页面大多是通过查询后台数据库然后返回给网页模 板最后生成。所以查询参数通常包含在u r l s 中，u r l s 除了查询参数外都是同一个 模式。同一个模式生成的页面通常有时属于同一个主题。我们称为“页面模板法 1 2 第二章垂直搜索概要设计和网络爬虫技术 则”，也就是说同一个模式的网页他们的主题和u r l 很可能一样。“页面模板法则 告诉我们一个站点中属于相同主题的u r l 有很大的相关性，可以用一个表达式来 表述。例如：在一个网上书店w w w d a n g d a n g c o m 中，一本书的信息可以表述为： “h t t p ：p r o d u c t d a n g d a n g c o m p r o d u c t a s p x ? p r o d u c t _ id = 木 ，其中的“木 代 表书的编号，我们就可以从u r l 知道此页面代表一本书的信息。只要后面是属于 这种模式的都与书的主题相关。在站点中与此主题相关的页面也具有这种模式。 对于一个主题相关的页面也大多由少数几个模式产生，因此，我们只要归纳出相 关的模式，就可以判断网页与主题的相关性了。 通用法则：基于以上的基本规则，提出了专用爬虫的结构如下。包括二部份： u r l 规则表达式学习和网页检索。 u r l 规则表达式学习，主要包括以下几个部分：u r l 抽取、分类判别、试验学 习、规则表达式学习。如下图： 图2 - 2 专用爬虫系统结构 u r l 规则表达式学习的步骤如下：1 ) ：先人工指定种子站点，从种子站点中 抽取与主题相关的超链接列表；2 ) ：爬虫学习程序根据上面从种子站点抽取出的 超链接列表，对每一个主题相关的链接采用宽度优先算法爬取相关的页面，爬取 深度为n ，n 的取值与爬虫的效率和主题表达式有关；3 ) ：我们称与一个指定的具 电子科技大学硕士学位论文 体主题相关的页面为“有关页面”，反之为“无关页面 。分类判别器就对爬取到 的页面分为上面二类；4 ) ：通过上一步的分类，产生了“有关页面集 。然后u r l 规则学习算法从其中提取出u r l 规则表达式。 2 3 2 1 网页检索 这部分主要是由u r l 规则表达式和u r l 抽取器完成。包括以下几步： 1 ) ：u r l 抽取器读取上一步得到的u r l 规则表达式。 2 ) ：u r l 规则表达式中包含了二个集合，一个是“有关页面 ，另一个是“无 关页面 。然后对网页中的u r l 判断是与哪一个集合匹配，这样目标u r l 集就产生 了。 2 3 。2 2 规则表达式学习 从基本规则和上面的步骤中可以看出，u r l 规则表达式在其中扮演了很重要的 角色。u r l 规则表达式学习算法如下图所示： 二_ u r l 分类。卜j 一3 r l 列刊 7 7 l u r k 族一 图2 - 3 规则表达式学习 步骤如下： 1 ) ：分类，u r l 分类器将输入的待分类u r l 列表分为几大子类，称为 u r l 族 ； 2 ) ：聚类，u r l 聚类器将上面分类结果进行聚类，形成几个小的u r l s ； 3 ) ：规则提取，从聚类结果抽取出u r l 表达式； 具体说明上面三步前先介绍一个要用的一些相关的数据结构： u r l 结构 1 4 第二章垂直搜索概要设计和网络爬虫技术 我们把u r l 分开看成以下几部分：h o s t ，p a t ha n dq u e r y ，h o s t 表示域名， p a t h 表示路径，q u e r y 表示一些查询变量和值。如以下 u r l “h t t p ：w w w c h i n a p u b t o m m e m b e r n e w b o o k v i e w a s p ? a d d = 1 t i d = 0 2 8 3 1 7 ”： h o s t 为“w w w c h i n a p u b c o l n ， p a t h 为“m e m b e r b u y b o o k v ie w a s p ， q u e r y 为“a d d = l t i d = 0 2 8 3 1 7 。 u r l 之间的距离矩阵 设i ，j 分别表示二个u r l ，则i ，j 之间的距离可以用以下的公式来计算： d 。，( i ，j ) = ( d “。( i ，j ) + 1 ) xd ，。( i ，j ) + 1 ) xd 。珂( i ，j ) 一l( 1 ) 其中d 。( i ，j ) 代表h o s t 之间的距离，d 。伯( i ，j ) 代表p a t h 之间的距离， d 哪。( i ，j ) 代表q u e r y 之间的距离。三个距离公式的计算方法如下： 1 ) ：如果h o s t ( i ) ! = h o s t ( j ) 则d 。( i ，j ) = m ，其他情况d 。( i ，j ) = 0 。d 。， ( i ，j ) 值应该足够大使得不同的域名聚类到一类中去，输入给聚类算法的u r l 大多 是属于同一个w e b 站点，大多数情况还是能识别。d 州( i ，j ) = m 很少使用，我们 对d 。，( i ，j ) 设置为m 是根据实验得来，使用这个值对我们后期处理有帮助。 2 ) ：加入i 和j 的p a t h ( 路径) 分别有1 1 1 层和n 层，m = n 。 3 ) ：判断u r l ( i ) 是否与u r l 列表中的c 眦( j ) 想匹配，如若匹配则u r l ( i ) 加 入c 。札( j ) ，否则，在c 。札建立新的u r l 类c 眦( j + 1 ) ，然后把u r l ( i ) 加入c 。甩( 3 + 1 ) 中做为第一个成员，重复第三步。这里的u r l 与u r l 类匹配是指u r l 和u r l 类中 的u r l 的阈值小于h ，即 “- ( i ，j ) = h ( 3 ) 在聚类完后，u r l 类列表中包含一个个的u r l 类，在同一个类中二个u r l 的距 离小于等于阈值h ，所以在同一个类中u r l 的相似度更大。 4 ) ：计算u r l 类是否满足条件，如果满足聚类算法就结束，否则，值h + = l ， 从第三步重新开始，条件定义如下： 1 ) ：m = n x q 。其中m 为静 态聚合产生的聚合结果中的u r l 类的个数，n 为u r l 总数，c ，q 为介于0 和1 之 间的小数。c 称为类别归纳参数，越大则聚合出来的u r l 类越多，每个u r l 类包含 的u r l 数也就越少：q 称为数量归纳参数，越大则聚合出来的u r l 类越少，每个u r l 类包含的u r l 数也就越多。 聚类算法流程图如下： 图2 5 聚类流程 2 3 2 5 表达式抽取 在通过聚类算法对u r l 类进行分组后，接着我们就可以用来抽取最重要的表 达式了，像前面叙述的一样，我们把u r l 划分为h o s t ，p a t h ，q u e r y 三部分，h o s t 都是相同的就直接拿过来就是，对p a t h 部分，若p a t h 相同就将相同部分加到h o s t 后面，其他情况就用一个，l c 代替，对q u e r y 部分做相同的处理，最后的表达式 就是我们提取 出 的规则表达式 。比 如 ： h t t p ：w w w c h i n a p u b c o m c o m p u t e r s b r o w s e b r o w s e r e s u l t a s p ? t y p e i d = * e t h e p a g e n u m = * & o r d e r t y p e = * 。至此，我们的专用爬虫就可以用此表达式来提取网页 了。 1 7 电子科技大学硕士学位论文 2 3 2 6 实验数据 我们采用上述算法进行了实验，实验的网站列表有中关村在线提供，人工选择 一些有代表性的网站进行实验抓取；具体的网站如下： 网站名网站名 w w w z 0 1 c o m c 1 w w w p c p r o c o m c n w w w z d n e t c o m c n w w w x i y u i t c o m w w w p c h o m e n e t w w w n e t f r i e n d s c o m c n w w w f e n g n i a o c o m w w w s o li d o t o r g w w w s p n c o m c n w w w c c i d n e t c o m w w w i t c o m c r l w w w c n e t n e w s c o m c n i t e n o r t h c o m c ni t h e x u n c o m 表2 1 实验主题网站列表 网站页面总数相关页面数招回率 、嗍z 0 1 c o m c n6 5 7 85 4 30 4 5 3 w w w p c p r o c o m c n 3 5 4 23 40 2 3 4 w w w z d n e t c o m c n9 3 7 01 2 3 40 4 2 3 w w w x i y u i t c o m 1 2 0 94 30 2 3 6 w w w p c h o m e n e t 8 7 5 45 5 30 5 4 2 w w w n e t f r i e n d s c o m c n5 2 3 22 3 40 6 3 4 w w w f e n g n i a o c o m 4 1 51 20 3 9 1 w w w s o li d o t o r g5 4 4 34 4 30 5 3 3 w w w s p n c o m c n 3 6 5 72 3 40 2 6 7 w w w c c i d n e t c o m3 2 6 75 4 70 5 2 3 w w w i t c o m c r l5 3 5 28 0 90 5 5 8 w w w c n e t n e w s c o m c n6 6 4 52 3 40 3 2 5 i t e n o r t h c o m c n2 3 5 51 20 4 8 7 i t h e x u n c o m1 3 3 54 3 40 6 0 1 表2 2 实验统计数据 实验对表的网站从首页抓取页面，深度为6 层，这些数据就是我们后面实验 数据集。然后就用我们上面的算法进行实验学习。类别归纳参数c 我们设为0 3 ， 第二章垂直搜索概要设计和网络爬虫技术 数量归纳参数q 设为0 7 ，其中招回率为获得相关页面数与实际相关页面数的比率。 1 9 电子科技大学硕士学位论文 第三章一体化中文分词和结构化提取技术 3 1 网页预处理 3 1 1 统一编码 现在网页常见的编码主要有以下几种：g b k ，g b 2 3 1 2 ，b i g 一5 ，u t f 一8 ，u t f - 1 6 ， u n i c o d e 等。 为了便于后面对网页进行处理，我们对下载下来的网页都统一转换成一种格 式( g b 2 3 1 2 ) ，一般网页的编码格式都在网页头中用属性c h a r s e t 标明，这种情况 可直接用编码转换函数进行转换，如若没有c h a r s e t 属性就尝试进行编码转换， 若不成功就丢弃。 3 1 2 噪声的识别和过滤 根据网页空间的特征将噪声分为两类：可见噪声与不可见噪声。可见噪声是 用户在通过浏览器浏览的时候可以直接观察