（计算机应用技术专业论文）事件垂直搜索引擎的研究与实现.pdf

中山大学硕士毕业论文 事件垂直搜索引擎的研究与实现 事件垂直搜索引擎的研究与实现 计算机应用技术 刘锦标 王常吉副教授 摘要 在信息膨胀的w 曲2 o 狂潮之下，g o o 百e 、b a i d u 等针对所有用户以及所有 主题的通用搜索引擎越来越力不从心，原因如下：通用搜索引擎只根据用户输入 的关键字搜索难以准确理解用户的需求，从而导致搜索的结果往往不是用户所需 要的；通用搜索引擎面向的是互联网上所有主题的网页，不可能做到面面俱到； 通用搜索引擎面向的最小单位是网页，搜索结果对某些特定需求的用户来说往往 不是最贴切的。 在这种情况下，垂直搜索应运而生。垂直搜索针对某些行业搜索需求的用户， 提供专业化的搜索服务。概括地说，垂直搜索提供的是对某一个特定行业的搜索。 它只抓取某一主题的领域网站，并且把网站的信息分类、去重、分词并结构化成 所谓的元数据，经过深度的加工处理、优化，并在返回用户查询结果时提供良好 的用户体验。 以往的垂直搜索往往只针对静态的物体进行搜索，如租房，餐饮等，但当今 社会是不断变化的社会，用户往往很想知道周边的资讯事件。这种领域的搜索本 身是符合用户需求和富有创新的。本文的垂直搜索主要是为用户提供对事件的关 于空间和时间两个维度的搜索。本文在深入研究垂直搜索引擎技术的同时，对架 构进行了精细的设计，设计并实现了一个分布式爬虫的事件垂直搜索系统，并提 出了一种基于规则和图路径的地址分词算法。在对事件对象的排序研究上，提出 了一种基于p a g e r a n k 和p o p r a n k 的h o t r a n k 的排序算法，它对对象间不同的同 类引用赋予不同的权重。实验表明，h o t r a n k 模型能够有效地提高p o p r a n k 的排 序准确率。 关键词：垂直搜索引擎，爬虫，中文地址分词，p o p r a i l l ( ，h o t r a n k 中山人学硕1 ：毕业论文事件垂直搜索引擎的研究与实现 r e s e a r c ha n di m p l e m e n t a t i o no fa ne v e l l tv 缸i c a ls e 鲫c he n 百n e c o m p u t e ra p p l i c a t i o nt e c l l i l o l o g y j i n b i a ol i u a s s o c i a t ep r o f e s s o rc h a n 自iw a n g a b s t r a c t a l o n gw i t ht 1 1 er a p i de x p a n s i o no fw 曲2 0 ，g o o 百e ，b a i d ua n do m e rg e n e r a l s e a r c he n 西n e s ，、礼i c hf a c et ot h ea l ll ( i n d so ft h eu s e r sa j l da l lk i n do fm et o p i c s ，a r c i n c r e a s i n 酉yi n s u 衔c i e n t t h er e a s o n sa r ea sf o l l o w ：f i r s t l xi t i sd i 伍c u l tf o rt h e g e n e m ls e a r c he n 西n et o 如1 1 y 吼d e r s t a l l dt h en e e do ft h eu s e r so n l yb yt l l ek e y w o r d i i l p u t t e db yt h eu s e r s i tm i 曲t1 e a d st h ei n a p p r o p r i a t es e a r c hr e s u l tt 0t l l e u s e r s s e c o n d l y t h eg e n e r a ls e a r c he n 百n e sc o u l dn o td ow e l li na ud o m a i n so ft h ei n t 锄e t t h i r d ly ，b e c a u s et h es e a r c hr e s u l tp r o v i d e db yt 1 1 eg e n e r a ls e a r c he n 西n ec o n s i s t so f p a g e sa si t sm i n i m u mu n i t s ，i tc o u l dr l o tm e e tt h eu s e r sw i ms o m es p e c i f i cn e e d u n d e rs u c hc i r c u m s t a n c e s ，v e n i c a ls e a r c he n 百n ec o m e so u t v 缸i c a ls e a r c h e n 百n ea i m sa tt h ec e r t a i nu s e r si ns o m es p e c i f i cd o m a i n sa 1 1 dp m v i d e ss p e c i a l i z e d s e a r c hs e i c e s g e n e r a l l ys p e a l ( i n g ，m ev e n i c a ls e a r c he n 百n ep r o v i d e ss e a r c h s e r v i c e sf o rap a n i c u l a rd o m a i n i tc r a w l sm ew e bs i t e so fo n es p e c i f i cd o m a i n ， r e t r i e v e sa r l dc l a s s i f i e st h ei n f o m a t i o nd a t a丹o mm ep a g e s ， s e g m e n t s a n d r e c o m p o s e st h ed a t at om e t a d a t a ，觚dp r o v i d e sab e t t e rs e a r c he x p e r i e n c et ou s e r s f o 册e rv e n i c a 】s e a r c he n 百n e s0 1 1 l yp r o v i d es e a r c hs e r v i c ee i t h e rf o rs t a t i cd a t a ， s u c ha sr e s t a u r a n t ，h o u s er e n t i n g h o w e v t o d a y ss o c i e t yc h a l l g e sc o n s t a n n y ，i ti sa s 仃d n gd e s i r eo fu s e r st ow a n tt ok n o ww h a th a p p e n s 啪u n dt l l e m t h i sp a p e r d i s c u s s e st h es e a r c hs e r v i c e sf o re v e n t st ou s e r s ，i nt h et w od i m e n s i o n s ，n 锄e l yt i m e a 1 1 d1 0 c “o n u s e r sc o u l dq u e r ys o m el 【i n d so fe v e n t sw i t h j ns o m ec e r t a i nl o c a t i o n a n dw i t h i nc e n a i nt i m e t h i sp a p e rp r 0 v i d e sad i s t r i b u t e dp l u 哥i n - b a s e dc r a w l i n g s y s t 锄o fv e n i c a ls e a r c he n 西n eu s i n gj a v a i ta l s op r o p o s e sam l e b a s e dc 1 1 i n e s e a d d r e s ss e g m e n t a t i o na l g o r i t l l ma i l dar a n k i n ga l g o r i t h mc a l l e dh o t r a n k ，w h i c hi s b a s e do np a g e r a n ka 1 1 dp o p r a n k i ta s s i 印sd i 虢r e n tw e i 曲t st ot h el i n k so fm es 锄e t y p eb e 觚e e n 附oo b j e c t sa n dc o u l di m p r o v et h er a n k i n ga c c u r a c y k e yw o r d s ：v r e r t i c a l s e a r c h e n 百n e ， c r a w l e r ，c h i n e s e a d d r e s s s e 舀：n e n t a t i o n ，p o p r 龇l k ，h o t r a r l l ( i i i 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 司懒 同期： 砂刁g 年厂月8 r 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名： 1 j 钦椿 同期：抄0 5 年厂月2 同 导师签名：主亨丧 同期：硎年，月艿同 中山人学硕士毕业论文 事件垂直搜索引擎的研究与实现 1 1 研究背景 第1 章引言 从1 9 9 0 年第一个搜索引擎加c h i e 的出现到现在已经有1 8 年了。在这1 8 年 | 、日j ，各种不同种类的搜索引擎不断涌现，从最初的w o r l dw i d ew e bw 锄d e r e r 、 a l i w e b 、w e b c r a w l d l l 到w o r l dw i d ew e bw o m 、l y c o s 【2 1 、a 1 t a v i s t a ，再到现在 如日中天的y a h o o ! 、g o o 百e 、百度等通用搜索引擎。搜索引擎已经成为我们 2 l 世纪的互联网的生活中不可或缺的一部分。 在信息膨胀的w 曲2 o 狂潮和人们需求的不断提高之下，g o o 百e ，b a i d u 等 通用搜索引擎越来越显示出它们的局限性。由于互联网的网页数量极其庞大，通 用搜索引擎无法索引到互联网上所有的网页；通用搜索引擎通常很难只通过用户 输入的关键字来准确判断用户的意图，这将会导致搜索结果的不理想，用户搜索 出来的结果往往不是用户所需要的；由于互联网的特点，通用搜索引擎处理的通 常都是海量网页，但是有用的网页只是少数的一部分，通用搜索引擎返回给用户 的信息量往往过大，用户很难从中找到最适合自己需求的信息，这就是所谓的“信 息膨胀”问题；通用搜索引擎面向的最小单位是网页，搜索结果对某些特定需求 的用户来说往往不是最贴切的。 在这种情况下，垂直搜索应运而生。垂直搜索针对某些行业搜索需求的用户， 提供专业化的搜索服务，比如b a i d u 很早就提供对m p 3 等音乐的垂直搜索，还 有著名的生活垂直搜索提供商k o o x o o 提供租房、餐饮、火车票等专业搜索的服 务。著名的通用搜索引擎g o o 四e 也提供了类似的服务。概括地说，垂直搜索提 供的是某一个特定行业的搜索。它只抓取某一主题的领域网站，并且把网站的信 息分类、去重、分词并结构化成所谓的元数据，经过深度的加工处理、优化，并 在返回用户查询结果时提供良好的用户体验。 以往的垂直搜索往往只针对静态的物体进行搜索，如租房、餐饮等，但当今 社会是不断变化的社会，用户往往很想知道周边发生了什么事，比如用户想知道 附近哪里有哈利波特的电影，哪里有购物打折信息等等。这种领域的搜索本身是 符合用户需求和富有创新的。本文的垂直搜索引擎主要是为用户提供事件的搜 中山大学硕士毕业论文事件垂直搜索引擎的研究与实现 索。事件的搜索分为空间和时间两个维度的搜索。用户可以查询某个地点某个范 围以及某个时间的某种类别的事件。 本文的课题来源于i b m 中国研究院和北京移动公司在2 0 0 7 年全球性的高校 学生青出于蓝( e x t r e m eb 1 u e ) 创新项目的一个子项目，主要目的是为移动飞信 平台提供创新的搜索服务。 1 2 本文的研究工作 本文在深入研究垂直搜索引擎相关技术的基础上，构建了一个完整的事件垂 直搜索引擎，包括一个可拔插的分布式爬虫模型，可以为用户提供各种事件的两 个维度( 时间和空间) 的搜索。本文对爬虫模型、中文地址分词和对象搜索结果 排序算法做了创新的研究。 本文提出的基于可拔插的爬虫插件的垂直搜索引擎有如下几个主要工作： ( 1 ) 设计可拔插的分布式的爬虫体系模块和其中部分的开发工作，较好地 解决了垂直搜索引擎信息源的增删和维护问题，并利用j m x 技术实现爬虫系 统的分布式管理。 ( 2 ) 设计与实现了爬虫插件系统模块。 ( 3 ) 设计与实现了事件垂直搜索的搜索服务模块。 ( 4 ) 针对事件数据库的索引问题，提出了一种基于规则的地址分词算法， 在小词典的限制的情况下取得了不错的效果。 ( 5 ) 在事件搜索结果排序算法的研究中，提出了一种基于p a g e r a n k 和 p o p r a l l l 【的h o t r a n l ( 的排序算法。实验证明，h o t r a l l l ( 有效地提高了p o p r a n k 的排序效果。 1 3 本文的工作意义 本文的垂直搜索引擎的成功实现具有理论和应用上的重要意义： ( 1 ) 在理论上，深入地研究了垂直搜索引擎的相关技术，如爬虫模型、网页 信息结构化抽取、中文分词和超链分析等，并对爬虫模型、中文地址分词和对象 排序做出了积极的创新研究，并很容易地扩展到其他领域上。 ( 2 ) 在应用上，构建了一个完整的垂直搜索引擎，为用户提供各种丰富的事 2 中山大学硕士毕业论文事件垂直搜索引擎的研究与实现 件元素的搜索，一定程度上探索了互联网上的商业垂直搜索引擎的相关技术，具 有较为重要的实践意义。 1 4 本文的组织结构 本文一共分为5 章，除本章外，其它各章组织如下： 第2 章介绍了搜索引擎和垂直搜索引擎的国内外的研究现状，详细地介绍搜 索引擎的历史、分类、原理以及垂直搜索引擎的例子。 第3 章详细地介绍了垂直搜索引擎的关键技术，包括爬虫搜集策略和爬虫模 型、网页信息的结构化抽取、超链分析算法和中文分词算法。 第4 章是本文的研究重点，详细讲述了事件垂直搜索引擎的研究与实现，提 出并讲述了基于爬虫插件的可拔插爬虫模型、索引过程中的地址分词算法以及对 象排序算法h o t r a n l ( 。 第5 章总结全文，并对本文的进一步研究工作进行展望。 中山人学硕l 毕业论文 事件垂直搜索引擎的研究与实现 第2 章国内外的研究现状 2 1 搜索引擎的研究 搜索引擎的历史可以说也是互联网的历史。互联网刚出现的时候，那时候的 互联网网站比较少，信息查找比较容易。但进入到9 0 年代初，互联网的规模飞 速发展，从客观上促进了搜索引擎的研究。为了从信息膨胀的互联网上有效地查 找信息，搜索引擎应运而生。 2 1 1 搜索引擎的历史 1 9 8 6 年，1 1 1 t e n l e t 正式形成了。1 9 9 0 年，加拿大的一个叫蒙特利尔( m c g i l l ) 的大学生设计开发了一个f t p 文件名搜索引擎，取名为心c h i e ，首次使用了自 动爬虫( c r a w l e r 或者r o b o t ) 程序。a r c h i e 也被称之为现代搜索引擎的鼻祖。 1 9 9 3 年，m i t 的m a t t h e wg r a y 开发了第一个用于监测互联网发展规模的爬 虫程序w o r l dw i d ew e bw a n d e r e r 。它也是第一个可以自动搜集网页的爬虫程序。 它最初是用来统计互联网上的服务器数量，后来又被发展为统计互联网的规模。 1 9 9 3 年1 0 月，a l i w e b ( 缸c h i e l i k ei n d e x i n go f t h ew e b ) 出现，它要求互联网 上的网站事先做好自身的索引，然后向a l i w e b 注册并提供自身的索引。它也提 供一个基于p e r l 的查询程序去搜索收集到的各个网站总的索引。 1 9 9 3 年1 2 月，三个新的搜索引擎出现：j u m p s t a t i o n 、w o r l dw i d ew e bw o n n 和r b s es p i d e “r e p o s i t o 巧一b a s e ds o f 时a r ee n 百n e 甜n 曲。j u m p s t a t i o n 使用爬虫获 取i n t e m e t 网页的题目( t i t l e ) 和标题( h e a d e r ) ，并且使用一个简单的匹配算 法去匹配之前获得的网页。w o r l dw i d ew e bw o n l l 只索引了网页的题目( t i t l e ) 和网址( u r l ) ，用正则表达式搜索整个数据库。这两个系统都支持深度搜索和 广度搜索，但产生的搜索结果都没有经过相关性排序。r b s e 和在1 9 9 4 年4 月 2 0 号发布的w e b c r a w l d l 】是第一批能够根据网页的相关性对搜索结果进行排序 的互联网搜索引擎之一。w e b c r a w l e r 使用向量空间模型对搜索结果进行排序。 w e b c r a w l e r 也是第一个保存和索引整个网页的文本的搜索引擎。它索引了9 0 0 0 4 中山大学硕士毕业论文事件垂直搜索引擎的研究与实现 多个网站，超过5 0 0 0 0 多个网页，每天可以处理超过6 0 0 0 个查询。 第一个现代意义上的w e b 搜索引擎是1 9 9 4 年7 月c m u 机器翻译中心的 m i c h a e lm a u l d i n 开发的l y c o s 【2 1 。l y c o s 不仅能够提供搜索结果相关性排序，还 可以提供前缀匹配和单词相似搜索等其他功能，不过它与之前搜索引擎最大的优 势还是它索引的网页的数量。在1 9 9 4 年7 月2 0 号，l y c o s 索引了大概五万4 千 多个网页，到8 月份，这个数目增长到了3 9 万4 千。到1 9 9 5 年1 月份，索引的 网页数量已经达到了1 5 0 万。到了1 9 9 6 年，l y c o s 索引的网页数量已经超过6 百万。l y c o s 是当时最大的搜索引擎。l y c o s 的爬虫程序使用启发式的最优优先 ( b e s t f i r s t ) 算法，它定义了一个网页的流行度( p o p u l 撕t y ) 为指向该网页的其他 网站的数目。l y c o s 和w e b c r a w l e r 不一样，它保存的不是整个网页的文本，而 是该网页的摘要的。l v c o s 自动统计出与该网页的文本最相关的1 0 0 个关键字， 并且通过这些关键字、题目( t i t l e ) 、标题( h e a d c r ) 文本以及网页的前2 0 行 或者1 0 的行的内容，自动产生该网页的摘要，并将它作为网页的存档保存在数 据库中。 r b s e 、w e b c r a w l e r 、l y c o s 以及其他商业搜索引擎，采用的是倒排文件索 引。一个倒排文件索引是一个单词的列表，这些单词都是出现在某些网页上。对 于每个单词，搜索引擎都保存着一个包含该单词的网页的列表，通常也会包括该 单词出现在该网页的位置等信息。 1 9 9 5 年，斯坦福大学的两个博士生d a v i df i l o 和j e n yy a i l g 创建了y a h o o ! 。 y a l l o o ! 的目录搜索引擎是一个树状层次结构，树上的每个节点是一类网站，用户 通过这棵树找到最能描述他们网站的节点，并且为了能加入到这个节点，用户需 要向y a l l o o ! 提交他们网站的介绍。 同年，第一个元搜索引擎m e t a c r a w l d 3 】由w a s h i n 舀o n 大学的硕士生e r i c s e l b e r g 和o r e t z i o n i 创建。 1 9 9 5 年1 2 月，a 1 t a v i s t a 正式由p a l oa l t o 的d i 舀t a le q u i p m e n t 公司的研究实 验室发布。a l t a v i s t a 是搜索引擎发展的里程碑，它是第一个支持多种语言搜索的 搜索引擎，也是第一个提供自动机器翻译服务的搜索引擎。 1 9 9 8 年9 月由斯坦福博士生l a n yp a g e 以及s e r g e yb r i n 创建的g o o 西e 以其 独创性的p a g er 锄k 算法以及超文本链接技术使g o o 酉e 可以为用户提供质量很 中山人学硕上毕业论文事件垂直搜索引擎的研究与实现 高的搜索结果，成为迄今世界上最受欢迎的w e b 搜索引擎。 2 0 0 1 年1 0 月2 2 号，b a i d u 搜索引擎发布，它是迄今中国最受欢迎的中文搜 索引擎。 据估计，2 0 0 5 年互联网上可索引的网页超过1 1 5 亿【4 】。全球最大的g 0 0 9 l e 也只是宣称索引了8 0 亿。 2 1 2 搜索引擎的分类 随着互联网2 0 多年的迅猛发展，搜索引擎也得到了快速发展。一般来说， 搜索引擎可以分为下列几类【5 】：目录式搜索引擎( d i r e c t o 巧s e a r c he n 西n e ) ，通 用搜索引擎( g e n e r a ls e a r c he n 百n e ) ，元搜索引擎( m e t as e a r c he n g i n e ) ，垂直 搜索引擎( v ( 缸i c a ls e a r c he n 百n e ) 。 ( 1 ) 目录式搜索引擎( d i r e c t o r y 或者c a t e g o r y ) 目录搜索引擎是这样的搜索引擎，它不对网页进行自动搜集和索引，而是为 用户提供一定数目的网站目录。每个网站目录代表一类网站。这些网站目录往往 是以树状形式组织的。每添加一个网站，目录搜索引擎都要确定它属于哪个目录 类别。一般而言，目录搜索引擎可以采用自动录入或者人工干预两种方式决定新 添加网站的归类。因此，目录搜索引擎通常都会要求用户提交网站地址、网站 名称和网站介绍，以便更好地归类新添加的网站。 目录搜索引擎几乎是和全文搜索引擎一起出现的。1 9 9 3 年的a 1 i w e b 是最早 的目录搜索引擎之一。到了1 9 9 5 年，m o o ! 的创建，使目录搜索引擎的发展得 到了一个新的高峰。y a h o o ! 目录甚至一度成为网友上网的指向标。另外一个比 较有名的目录搜索引擎是l o o k s m a f t 。 ( 2 ) 通用搜索引擎 通用搜索引擎和目录搜索引擎不一样，它是基于自动爬虫的搜索引擎。通用 搜索引擎往往有2 4 小时自动搜集网页并进行索引的爬虫系统。通用搜索引擎会 对自动搜集而来的网页进行全文索引，包括网址、网页名称和网页内容等等，并 根据网页内容和网页链接计算该网页的相关性。相对于目录搜索引擎而言，通用 搜索引擎的数据库要大的多，主要是因为： 1 ) 通用搜索引擎不要求用户提供对其网站的描述信息来确定该网站的内容 6 中山大学硕1 ：毕业论文事件垂直搜索引擎的研究与实现 和主题，而是通过一定的算法对网页内容进行处理并确定。 2 ) 通用搜索引擎会对一个网站的多个页面进行索引，但目录搜索引擎通常 只会收录用户网站的一个页面。 早期因为技术问题，通用搜索引擎的发展远没有目录搜索引擎快。早期的通 用搜索引擎有l y c o s 、a 1 t a v i s t a 、i n f o s e e k 。随着近1 0 年的发展，通用搜索引擎 的发展越来越迅速，特别是1 9 9 8 年g o o g l e 的成立以及后来取得的巨大成功，更 是掀起了通用搜索引擎发展的高潮。 ( 3 ) 元搜索引擎( m e t as e 2 u r c he n 百n e ) 元搜索引擎会把用户的查询转发到多个通用搜索引擎，并对来自多个通用搜 索引擎的查询结果进行去重、归类、可视化处理和重排序等等。元搜索引擎关注 的是如何提高搜索结果的质量和用户体验，例如a s l 【j e e v e s 可以接受用户英文问 句的查询，比如：“h o wc a nis c a np h o t o 铲a p h s ? ”。m e t a c r a w l d 3 】是最早的元搜索 引擎之一。 ( 4 ) 垂直搜索引擎( 舡i c a ls e a r c he n 百n e ) 垂直搜索引擎是特定行业或者主题的通用搜索引擎。它与通用搜索引擎的不 同之处在于，它只关注与某个行业或者主题相关的网页。垂直搜索引擎与通用搜 索引擎的技术和思想很相似，也是依赖于自动爬虫系统对特定行业网页进行收集 和索引。但垂直搜索引擎是面向特定行业和主题的，它只搜集某个行业相关的网 页，并对网页的信息进行抽取、分类和再加工等等。因为垂直搜索引擎是面向行 业的专业化搜索引擎，用户的查询词歧义在垂直搜索引擎的眼中远比通用搜索引 擎要小的多，所以它比通用搜索引擎更能准确地理解用户的查询需求。 垂直搜索引擎可再细分为网页级垂直搜索引擎( p a g e l e v e lv e ：n i c a ls e a r c h e n 酉n e ) 和对象级垂直搜索引擎( o b j e c t - l e v e lv e n i c a ls e a r c he n 百n e ) 。前者跟通 用搜索引擎一样，处理的最小单位是网页。后者则会对网页上的数据进行数据抽 取( 1 1 1 f o 彻a t i o ne x t r a c t i o n ) ，形成结构化对象作为其处理的最小单位。垂直搜索 引擎会在2 2 节详细介绍。 2 1 3 搜索引擎的原理 自从最早的搜索引擎之一w 矾dw i d ew 曲w 6 肌( w w w w ) 发布以来，对搜 7 中山火学硕士毕业论文事件垂直搜索引擎的研究与实现 索引擎的研究一直没间断过。w e b c r a w l e r 、l y c o s 和m e t a c r a w l e r 等商业或者学 术的搜索引擎不断涌出。但搜索引擎的原理架构基本上没有改变【6 一。下图是一 个典型的搜索引擎架构： 图2 1 搜索引擎的架构 如图2 1 所示，搜索引擎一般包括爬虫程序( c r a w l e r ) ，索引器( i n d e x e r ) ， 查询器( s e a r c h e r ) 和用户接口( u s e ri n t e 晌c e ) 。它的基本原理一般是这样的： 首先爬虫程序按照一定策略从网络上获取网页资源，并把网页信息进行提取，分 词，形成各个倒排文档并进行索引，并根据不同算法对网页进行排序、分类。搜 索引擎一般还会有一个良好的w 曲端界面供用户查询。当搜索引擎接收到用户 的查询短语，便会从倒排数据库中得到相应的结果，并根据一定的策略进行排序， 最后通过w 曲或者其他界面显示给用户。 ( 1 ) 爬虫程序( c r a w l e r ) 爬虫程序一般被称作s p i d e r 或者c r a w l e r 。搜索引擎一般都会依赖爬虫程序 来获取网页。爬虫程序可以按照搜索引擎设定的策略去遍历互联网，比如图的广 度搜索或者宽度搜索。简单地说，爬虫程序会从一个初始的u r l 集合开始，每 次从u r l 集合按照一定策略取得一个u r l ，从网络上获取该u r l 对应的网页， 并对该网页进行解析，提取该网页的u r l s 。爬虫把新解析出来的u r l s 放入到 之前的u r l 集合，同时把被解析的网页的其他信息，如题目、标题、正文和超 链接等，连同u r l 存放到既定的网页文档数据库，并继续从u r l 集合中取出下 一个要获取的u r l 。这样循环重复，直到u r l 集合为空或者达到搜索引擎的要 中山大学硕：卜毕业论文事件垂直搜索引擎的研究与实现 求而停止为止。 通常一个爬虫程序只会负责一部分u r l 的抓取，如g 0 0 百e 使用一个叫 u r l s e r v e r 的程序管理如何把u r l 派遣到哪个爬虫程序。为了提高效率，爬虫 程序往往使用多线程或者多进程技术【引。 ( 2 ) 索弓i 器( i n d e x e r ) 索引器的功能是把网页中有用的文本从复杂的h t m l 标签中解析出来并建 立索引。在搜索引擎发展历史的前期，由于技术问题，搜索引擎通常只会索引网 页的网址( u r l ) 、题目( t i t l e ) 和标题( h e a d e r ) 等信息。由于数据量很小， 通常使用的是数据库和正规表达式匹配等等。例如j u m p s t a t i o n 和w 6 r l dw i d e w 曲w b n l l 。随着互联网的网页数目的急速膨胀和搜索引擎的发展，全文索引成 为大势所趋。这种低效的索引办法逐步被高效的倒排索引文件代替。一般而言， 索引分为三个部分。 1 ) 解析 这个过程是把网页中的h t m l 标签去掉，把有用的文本抽取出来。由于历 史原因，互联网上的网页依赖于松散的h t m l 标准，这导致开发一个高效的、 容错性好的解析器并不容易。 2 ) 把网页切分出单词形成顺排索引文件 在这个过程中，每一个网页都会被赋值一个i d 值，叫d o c i d 。g o o 百e 的 u r l r e s o l v e r 的功能就是确保每一个网页都有一个不同的d o c i d 。而每一个网页 也都会按照一定的算法切分为一定数目的单词。这种单词以及它们在该网页出现 的相关信息被称之为h i t 。如果是英文网页的话，这种切分就比较简单，因为英 文单词通常是根据空格和标点符号来分割开的。但如果是中文网页的话，就涉及 到中文分词技术。中文分词技术会在后面详述。 每一个h i t 至少包括它本身的单词和该单词在该网页的位置，有时还会包括 单词的大小，以及是否大小写等信息。每一个h i t 也都会被赋值一个i d 值，叫 w 6 r d i d 。索引器根据这些h i t s 的d o c i d 把它们散布在桶集合中，比如d o c i d 为 0 到1 0 0 0 的网页归入到桶o ，最后形成所谓的顺排索引文件。 3 ) 把顺排索引文件重新排序，形成倒排索引文件 接着对每个桶的h i t s 根据w b r d i d 进行排序，形成整个倒排索引文件。这个 9 中山大学硕上毕业论文 事件垂直搜索引擎的研究与实现 过程由于计算机的内存有限，无法一次性形成倒排索引文件，通常会涉及到外存 归并排序和分布式技术。 下图是一个倒排索引列表的简单例子。例子中假设c o m p u t e r 的w ，o r d i d 是 1 0 0 0 2 3 ，s e a r c h e r 的w r o r d i d 是1 0 0 0 2 4 。网页a 的d o c i d 是4 9 3 2 ，它在位置4 0 有c o m p u t e r 这个单词，在位置4 9 有s e a r c h e r 这个单词。网页b 的d o c i d 是4 9 3 3 ， 它在位置5 0 有c o m p u t e r 这个单词，在位置5 9 有s e a r c h e r 这个单词。这个例子 所形成的顺排索引文件和倒排索引文件如图2 2 和图2 3 所示。 d o c i d ： i w o r d i d ：h i t s ：位置 i卜 l 4 9 3 2 i 1 0 0 0 2 34 0 i w o r d i d ：h i t s ：位置 1 0 0 0 2 44 9 i d o c i d ： l w b r d i d ： h i t s ：位置 l卜+ l 4 9 3 3 i 1 0 0 0 2 35 0 ll w o r d i d ： h i t s ：位置 r 1 0 0 0 2 45 9 h i t s ：位置 _ ； ： 卜一一一一一一一一= 一h i t s = 位置i i 一：一j 一三函1 ； ： i _ 一一一一一一一一一一 一h i t s 位置1 图2 2 顺排索引文件 1w b r d i d ：i d o c i d ： h i t s ：位置 i卜 啼 i 1 0 0 0 2 3 l 4 9 3 24 0 li d o c i d ：h i t s ：位置 4 9 3 35 0 h i t s ：位置 卜一一一一一一一 一h i f s ：位置 i 1w b r d i d ：i d o c i d ：h i t s ：位置 l卜 呻 l 1 0 0 0 2 4 i 4 9 3 2 4 9 ii d o c i d ： h i t s = 位置 啼 4 9 3 35 9 h i t s ：位置 h i t s ：位置 h i t s ：位置 h i t s ：位置 图2 3 倒排索引文件 这样，从图2 3 的倒排索引文件列表可以得知，c o m p u t e r 这个单词在d o c i d 为4 9 3 2 的网页和d o c i d 为4 9 3 3 的网页中有出现。 除此之外，索引器通常还会做其他的处理，比如自动对网页产生摘型2 1 ，对 1 0 中山大学硕士毕业论文 事件垂直搜索引擎的研究与实现 网页进行分类和聚类等。另外通常还会建立一个网页链接图的映像。我们称指向 该网页的u i u 为该网页的1 1 1 1 i n k ，该网页指向别的网页的u r l 为该网页的 o u n i i l k 。这样，每个网页可以被看作图的一个节点。如果网页a 有指向网页b 的一个链接，我们就说节点a 到节点b 有一条有向边。这个链接图的映像是后 续所说的各种基于链接的技术的基础。 ( 3 ) 查询器( s e a r c h e r ) 简单地说，查询器就是根据用户输入的查询短语，从索引数据库中找出包含 用户输入的查询短语的网页文档，并根据一定的算法对搜索结果进行相关性排 序，最后把结果返回给用户。 查询器首先把用户输入的查询短语解析成单词串，并把单词串转换为相应的 w 6 r d i d 。对于每一个w b r d i d ，从倒排索引数据库找到对应的d o c i d 列表。并根 据该d o c i d 列表得到所有包含w r o r d i d 的网页文档，然后对搜索出来的网页文档 进行相关性排序，最后把前k 个结果返回给用户。 查询器一般使用向量空间模型或者超链接分析模型来进行网页相关性排序。 ( 4 ) 用户接口( u s e ri n t e r f a c e ) 一般搜索引擎都会提供各种形式的用户界面，让用户更好地使用搜索引擎。 用户接口一般包括搜索引擎支持的查询语法，是否可以多语种搜索，友好的查询 结果排列形式，显示界面的设计( 字体、色彩和布局等) 。如g o o g l e 就以人性化 的网页界面得到大量用户的喜爱，g 0 0 舀e 还为用户提供了手机端界面。 2 1 4 通用搜索引擎的局限性 随着互联网信息的不断膨胀和人们需求的不断提高，通用搜索引擎越来越显 示出它们的局限性： ( 1 ) 由于互联网的网页数量极其庞大，通用搜索引擎无法索引到互联网上所 有的网页。即使是全球最大的搜索引擎g o o 西e ，它也最多只有7 0 多的索引覆 盖率【4 1 。 ( 2 ) 通用搜索引擎很难只通过用户输入的查询短语来准确判断用户的意图， 而这将会导致搜索结果的不理想，搜索出来的网页往往只是含有该用户输入的关 键字，但并不是用户真正的意图。这就是所谓的“搜索歧义”。 中山大学硕上毕业论文事件垂直搜索引擎的研究与实现 ( 3 ) 由于互联网的特点，通用搜索引擎处理的通常都是海量网页，但是有用 的网页只是少数的一部分，而通用搜索引擎返回给用户的信息量往往过大，用户 很难从中找到最适合自己需求的信息，形成所谓的“信息膨胀”问题。 2 2 垂直搜索引擎的研究 随着瓦联网的不断增长，通用搜索引擎已经不能够满足大部分用户对某个主 题的搜索。各种主题垂直搜索引擎应运而生，为用户提供更为精确的主题搜索。 垂直搜索引擎也叫做主题或专业搜索引擎。与通用搜索引擎不一样的是，垂直搜 索引擎是某一个领域或行业的搜索引擎，它可以对特定行业的网页进行深层加工 或者结构化整合等，因此它可以给用户带来不同于通用搜索引擎的更为贴近行业 的用户体验。 一般而言，垂直搜索引擎可以大致分为两种类型【9 】。一种是服务器端的搜索 引擎，另一种是客户端的搜索代理。前者跟通用搜索引擎类似，通过爬虫自动收 集特定主题的网页，建立相关的索引，并通过w 曲界面为用户提供搜索服务。 后者是一个运行在用户电脑上的程序，叫做搜索代理的。它可以从网络上搜集网 页，也可以从其他搜索引擎获得搜索结果。这种方式让用户有着更大的控制性。 t u e m o s a i c 【1 0 】是其中一个例子。t u e m o s a i c 让用户可以指定搜索关键字以及遍历链 接的深度和宽度，并从特定的主页搜索结果。另外的一个例子是l e i t i z i a 【】，在 用户浏览网页的过程中，它使用广度优先的算法从用户浏览的网页开始并发地收 集和分析其他网页，并使用t f i d f ( t e mf r e q u e n c yt i m e si i l v e r s ed o c u m e n t f r e q u e n c y ) 模型把与用户当前浏览的网页最相似的网页推荐给用户。 由于后者是在用户电脑上即时搜索网页并进行处理，虽然有其更强的用户自 定义等优点，但并不适合大规模的行业网页搜索。 垂直搜索引擎大致可以分为网页级垂直搜索引擎和对象级搜索引擎。网页级 垂直搜索引擎处理的最小对象和通用搜索引擎一样是网页，这种垂直搜索引擎的 思想和通用搜索引擎很类似，可以利用通用搜索引擎的大部分技术。两者的区别 主要在于网页级垂直搜索引擎的爬虫的搜集策略是主题式收集( f o c u s e d c r a w l i n g ) 。网页级垂直搜索引擎提供给用户的搜索结果和通用搜索引擎一样， 最小单位是网页。对象级搜索引擎会对网页进行信息抽取，形成结构化数据，最 1 2 中山大学硕士毕业论文事件垂直搜索引擎的研究与实现 后提供给用户的搜索结果不再是网页，而是结构化数据，从而可以很容易地经过 可视化加工和再处理给用户提供更好的用户体验。 针对垂直搜索引擎的研究已经有了很多【1 2 - 1 9 1 。大都是集中在爬虫的策略 ( f o c u s e dc r a w l i n g ) 、网页信息抽取( i n f o n l l a t i o ne x t r a c t i o n ) 、中文分词( c h i n e s e s e g m e n t a t i o n ) 和搜索结果排序( o b j e c tr a i 此n g ) 。这些技术会在第三章详细讨 论。 2 2 1 垂直搜索引擎网站的例子 当今互联网上有很多成功的垂直搜索引擎网站，它们大都专注在某一领域， 为用户提供专业化的行业搜索，比如： ( 1 ) l a w c r a w l e r i 堕鲨迎! 垦型堡垒巡! 曼曼q m ) l a w c r a w l e r 是f i n d c r a w l e r 网站的搜索引擎，它提供针对专业人士、学生、 公众或者商业上与法律相关的各种资源的搜索，比如各个地区的法律相关的新 闻、法律案例等等，另外它还提供搜索各个地区的律师工作等服务。 ( 2 ) b u i l d i n g o n l i n e ( 坚垒丛垒坠i ! 立i 旦g q 丑! i 垒曼：曼q l 坠) b u i l d i n g o n l i n e 是热门的建筑行业搜索引擎，它为用户提供与住址设计、建 筑、住房改善、木材以及其他建筑产品产业相关的搜索。它每周会对超过2 0 4 0 0 0 个与建筑行业相关的网页进行更新。 ( 3 ) s c i s e e k ( 堕巡墨曼i 墨皇星k ：曼q 卫! ) s c i s e e k 是一个科学与自然领域方面的学术搜索目录和搜索引擎，提供农业、 工程、环境、健康、医药、生物、化学和物理等方面的科技期刊以及其他相关信 息的搜索。 ( 4 ) b i o e w ( 鲨幽型：毯q 五星盟曼q 堡) b i o e w 是一个能为用户提供生物技术和药物相关信息的搜索引擎，并可以 提供生物技术和药物相关工作的搜索。 ( 5 )g o l f h e