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

武汉理工大学硕+ 学位论文 摘要 随着i n t e m e t 的飞速发展，w e b 中所容纳的信息量越来越大，在存储，信息 采集等方面通用搜索引擎正面巨大的挑战。而且，由于通用搜索引擎是面向各 种各样的用户，它们的目的是保证在返回结果上做到面面俱到，但是各种各样 的结果实际上并不能满足用户对精确度高的搜索的需求。因此，面向专业领域 的搜索引擎即垂直搜索引擎便应运而生。 和传统的搜索引擎所不同的是，垂直搜索引擎的网络蜘蛛只是采集w e b 中 的一部分信息。通过对网页的主题相关度进行预测和判断，专业网络蜘蛛在爬 行时就会避开大量的与主题无关的信息。由于只采集那些和主题相关的网页， 从而使垂直搜索引擎在查询的准确率和效率上都有显著的提高。目前，垂直搜 索引擎的中文分词和主题预测有待迸一步提高精度，网络蜘蛛的搜索策略也有 待进一步改进以提高搜索引擎的覆盖率和运行效率。 本文在分析目前常用的主题爬行策略的基础之上，根掘p a g e r a n k 算法的思 想，结合基于文本内容的启发式策略和基于w e b 超链分析的策略二者之间的优 点，提出了一种新的主题爬行策略，既可以利用链接分析扩大某个主题的资源 覆盖度，又可以保证搜索结果与主题的高度相关。 此外，本文通过研究和分析传统的p a g e r a n k 算法及其不足，在基于用户点 击网页内的各个链接的概率是不均等的情况下，提出一种基于概率的p a g e r a n k 改进算法，该算法可以用于领域搜索引擎的主题相关度预测，能有效地避免主 题漂移现象。 最后，基于l u c e n e 框架和改进的h e r t r i x 开源爬虫框架，设计并构建了一个 面向电子产品信息的垂直搜索引擎的原型系统。 关键词：垂直搜索引擎，主题爬虫，爬行策略 武汉理工大学硕士学位论文 a b s t r a c t w i t ht h er a p i dg r o w t ho ft h ei n t c r n c t ，t h ei n f o r m a t i o nc o n t a i n e di ni tw i l lb e c o m e m o r ea n dm o r e i tp o s e su n p r e c e d e n t e dc h a l l e n g e sf o rg e n e r a l p u r 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 ls e a r c he n g i n e sp r o v i d es e r v i c ef o ra l lu s e r s ，s ot h er e s u l t sf r o m t h e ma r et o oe x h a u s t i v e m i l l i o n sa n dt h o u s a n d so fi r r e l a t i v er e s u l t so b v i o u s l yd o n t m e e tt h ep r 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 r t i c a ls e a r c he n g i n ew h i c hp r o v i d e s s e r v i c ei na s i n g l 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 e 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 l eq u e r i e s ，af o c u s e dc r a w l e ra n a l y s i si t sc r a w lb o u n d a r yt of i n dt h e l i n k st h a ta r el i k e l yt ob em o s tr e l e v a n tf o rt h ec r a w l a n da v o i d si r r e l e v a n tr e g i o n so f t h ew e b a so n l yr e l a t e dp a g e sa r ec r a w l e d ，a c c u r a c ya n de f f i 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 sh a v ei m p r o v e dr e m a r k a b l y c u r r e n t l y , a c c u r a c y o fc h i n e s ew o r d s e g m e n t a t i o na n 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 t r a t e g yo f f o c u s e dc r a w l e rh a sy e tt ob ef u r t h e ri m p r o v e dt oe n h a n c es e a r c he n g i n ec o v e r a g e a n de f f i c i e n c y b a s e do na n a l y z i n gt h er e c e n tc r a w l i n gs t r a t e g i e so fs u b j e c t i n gs e a r c h i n gi n c o n l m o nu s ea n dt h et h i n k i n gi np a g e r a n ka r i t h m e t i c ，an e wc r a w l i n gs t r a t e g yw a s p r o p o s e dt h a th a v et h em e r i t so f t h et w oo ft h ee n l i g h t e n i n gs t r a t e g yb a s e do nc o n t e n t a n dt h es t r a t e g yb a s e do nh y p e r l i n ka n a l y s i s i tw a sp o s s i b l et oe n l a r g et h er e s o u r c e d e g r e eo fc o v e r a g et h r o u g hh y p e r l i n ka n a l y z i n ga 8w e l la st oe n s u r et h es e a r c h i n g r e s u l t sh i 曲c o r r e l a t et ot h es u b j e c t an e wi m p r o v e dp a g e r a n ka l g o r i t h mw a sd e s i g n e db yr e s e a r c h i n ga n da n a l y z i n g t h es h o r t c o m i n go ft r a d i t i o n a lp a g e r a n ka l g o r i t h m ，w h i c hb a s e do nt h eu n e q u a l p r o b a b i l i t yw h e nu s e r se l i c ko nt h ew e b s i t e t h ee x p e r i m e n t ss h o wt h a tt h ea l g o r i t h m c a nb eu s e dt ot h es u b j e c ts e a r c he n g i n ea n da v o i dt h et o p i cd r i f tp h e n o m e n o n e f f i c i e n t l y f i n a l l y , w i t ht h ei m p r o v e dh e r i t r i xf r a m ea n dt h el u c e n ef r a m ed e s i g n e da n d r e a l i z e dai n d i v i d u a l i z e dv e r t i c a ls e a r c he n g i n e ，a n dc o n s t r u c t e do n ep r o t o t y p es y s t e m o fv e r t i c a ls e a r c he n g i n ew h i c hf a c e dt ot h ee l e c t r o n i cp r o d u c ti n f o r m a t i o n k e yw o r d s ：v e r t i c a ls e a r c he n g i n e ；t o p i c f o c u s e dc r a w l e r ； c r a w l i n gs t r a t e g y 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方以外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究的任何贡 献均已在论文中作了明确的说明并表示了谢意。 研究生( 签名) ： 到豳日期：垒幽：笪 学位论文使用授权书 本入完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权武汉理工大学可以将本学位论文的全部内容编入有关数据库 进行检索，可以采用影印、缩印和其他复制手段保存或汇编本学位论文。同时 授权经武汉理工大学认可的有关机构或论文数据库使用或收录本学位论文，并 向社会公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ： 建l _ 碰j 导师( 签名) ：耋盔墨! 日期：坦皇皇i 主 武汉理工大学硕士学位论文 1 1 本课题的研究背景 第1 章绪论 据中国互联网中心的第2 3 次互联网发展报告报道，截至到2 0 0 9 年1 月1 3 日，中国网站总数达到2 8 7 8 0 0 0 个，网页总数已经超过1 6 0 9 亿个，网页字节总 数为4 6 0 2 1 7g b 。由于i n t e m e t 上的信息呈几何级数增长，而这些信息又是极 其无序的，因此想要在这个浩瀚无垠、瞬息力变的信息海洋中迅速、准确地找 到自己所需要的信息无异于“大海捞针。搜索引擎正是为了解决这个“迷航 问题而出现的技术。搜索引擎以一定的策略在互联网中搜集、发现信息，对信 息进行理解、提取、组织和处理，并为用户提供检索服务，从而起到信息导航 的目的。搜索引擎提供的导航服务已经成为互联网上非常重要的网络服务，搜 索引擎站点也被美誉为“网络门户 。自1 9 9 4 年基于w e b 的搜索引擎出现以来， 搜索引擎便得到了极大的发展。根据统计，大约8 5 的用户使用搜索引擎去定 位他们需要的信息。因此，搜索引擎研究对于网络信息资源的有效丌发和利用 具有重要的意义。 1 2 通用搜索引擎 通用搜索引擎( s e a r c he n g i n e ) 是对互联网上的信息资源进行搜集整理，然 后供用户查询的系统，它包括信息搜集、信息整理和用户查询三部分口1 。搜索引 擎是一个为用户提供信息“检索”服务的网站，它使用某些程序把因特网上的 所有信息归类以帮助用户在网络的海洋中搜寻到所需要的信息。 1 2 1 通用搜索引擎的发展史 早在w e b 出现之前，互联网上就己经存在共享的信息资源了。这些资源当 时主要存在于各种允许匿名访问的f t p 站点，查询起来非常不便，于是1 9 9 0 年， 加拿大麦吉尔大学( u n i v e r s i t yo fm c g i l l ) 计算机学院的师生开发出a r c h i e ，人们 通过f t p 来共享交流资源。虽然a r c h i e 搜集的信息资源不是网页( h t m l 文件) ， 武汉理工大学硕十学位论文 但和搜索引擎的基本工作方式是一样的：自动搜集信息资源、建立索引、提供 检索服务。所以，a r c h i e 被公认为现代搜索引擎的鼻祖。 19 9 3 年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 ，这是第一个利用 h t m l 网页之间的链接关系来检测万维网规模的“机器人( r o b o t ) 程序。开始， 它仅仅用来统计互联网上的服务器数量，后来也能够捕获网址( u r l ) 。 1 9 9 4 年4 月，斯坦福大学( s t a n f o r du n i v e r s i t y ) 的两名博士生，美籍华人j e r r y r a n g ( 杨致远) 和d a v i df i l o 共同创办了y a h o o 。因为y a h o o 的数据是手工输入的， 所以不能真正被归为搜索引擎，事实上只是一个可搜索的目录。 1 9 9 4 年7 月，卡内基梅隆大学( c a r n e g i em e l l o nu n i v e r s i t y ) 的d r m i c h a e l m a u l d i n 将j o h nl e a v i t t 的s p i d e r 程序接入到其索引程序中，创建了l y c o s 。除了 相关性排序外，l y c o s 还提供了前缀匹配和字符相近限制，l y c o s 第一个在搜索 结果中使用了网页自动摘要，而最大的优势还是它远胜过其它搜索引擎的数据 量。 1 9 9 5 年1 2 月，d e cj 下式发布a l t a v i s t a 。a l t a v i s t a 是第一个支持自然语言 搜索的搜索引擎，第一个实现高级搜索语法的搜索引擎( 如a n d ，o r ，n o t 等) 。 用户可以用a l t a v i s t a 搜索新闻组( n e w s g r o u p s ) 的内容并从互联网上获得文章， 还可以搜索图片名称中的文字、搜索t i t l e s 、搜索j a v aa p p l e t s 、搜索a c t i v e x o b j e c t s 。a l t a v i s t a 也声称是第一个支持用户自己向网页索引库提交或删除u r l 的搜索引擎，并能在2 4 小时内上线。 1 9 9 6 年，i n k t o m i 公司成立，强大的h o t b o t 出现在世人面前，其声称每天 能抓取索引一千万页以上，所以有远超过其它搜索引擎的新内容。h o t b o t 也大 量运用c o o k i e 储存用户的个人搜索喜好设置。 1 9 9 9 年出现的g o o g l e 以网页级雯n p a g e r a n k ) 为基础，来判断网页的重要性， 使得搜索结果的相关性大大增强。 中文搜索相对起步比较晚。o p e n f i n d 创立于1 9 9 8 年1 月，其技术源自台湾 中正大学吴升教授所领导的g a i s 实验室。o p e n f i n d 起先只做中文搜索引擎，鼎 盛时期同时为门户新浪，雅虎等提供中文搜索引擎。 2 0 0 0 年1 月，两位北大校友，超链分析专利发明人，前i n f o s e e k 资深工程 师李彦宏与好友徐勇在北京中关村创立了百度公司。2 0 0 1 年8 月发布b a i d u t o m 搜索引擎b e t a 版，2 0 0 1 年1 0 月正式发布b a i d u 搜索引擎，专注于中文搜索。 2 0 0 3 年1 2 月，原慧聪搜索正式独立运做，成立了中国搜索。2 0 0 4 年2 月， 2 武汉理工大学硕士学位论文 中国搜索发布桌面搜索引擎网络猪v 1 0 。2 0 0 6 年3 月中搜将网络猪更名为 i g ( i n t e r n e tg a t e w a y ) 。 s o h u 于2 0 0 4 年8 月独立域名的搜索网站“搜狗 ，自称“第三代搜索引擎 。 2 0 0 5 年6 月，新浪正式推出自主研发的搜索引擎“爱问 。 1 2 2 通用搜索引擎的分类和工作流程 通用搜索引擎按其工作方式主要可分为三种，分别是目录式搜索引擎、基 于网络蜘蛛全文搜索引擎和元搜索引擎【3 】。 1 ) 目录式搜索引擎 目录式搜索引擎主要依靠人工维护网站索引，基于目录的搜索引擎通过人 工浏览各站点的信息，按照一定的分类规则或分类体系，对网站进行分类1 4 】。一 般来说，它们具有结构清晰、错误较少，比较符合人们的阅读习惯的优点，而 缺点是工作人员多、整理周期长、速度慢、人工干预成分多，不能适应w e b 资 源的规模发展，另外如果查找的信息没有对应的分类项，则无法进行搜索。代 表网站：早期的雅虎( w w w y a h o o c o m ) 。 2 ) 基于网络蜘蛛的全文搜索引擎 网络蜘蛛是指可以在w e b 上漫游并按照一定规则自动从w c b 下载网页的计 算机程序，对应的同义词有机器人( r o b o t ) 、爬行器( c r a w l e r ) ，漫游者( w a n d e r e r ) 等。基于网络蜘蛛的搜索引擎的全部工作基本上由程序自动完成，人工参与成 分很少。它通过网络蜘蛛在网上自动爬行，将搜索到的网页自动地加入到本地 索引数据库中，用户可以很快从索引数据库查到更新后的信息。它的优势在于 自动化程度高、维护费用低，更强调技术上的创新和提高，也更适合于开展研 究工作，因而成为当前研究的热点。代表网站：谷歌( w w w g o o g l e c o r n ) 。 3 ) 元搜索引擎 元搜索引擎是一种通过调用其它独立搜索引擎而完成搜索服务的搜索引 擎，是用户同时使用多个独立搜索引擎进行网络搜索的中介。用户只需递交一 次检索请求，由元搜索引擎负责转换处理后提交给多个预先选定的独立搜索引 擎，并将所有查询结果集中起来以整体统一的格式呈现到用户面前。元搜索引 擎通过综合利用多个搜索引擎的搜索服务，可以在一定程度上弥补单个搜索引 擎的不足，但是元搜索引擎的出现，并不能使搜索引擎技术得到质的飞跃。代 表网站：纳索网( w w w n a s u o c o m ) 。 3 挲，一：。凳i 一霉! 圆 索引库 0 链接库 ?、 一j 。j y 武汉理工大学硕士学位论文 一个词放入分词词典里，全国有那么的名字，收录这些人的姓名就是一个很浩 大的工程。有统计表明，单纯使用该方法的匹配错误率为1 1 6 9 ，这种精度还远 远不能满足实际的需要【b 】。实际使用的分词系统，都是把机械分词作为一种初 分手段，还需通过利用其它的语言信息来进步提高切分的准确率。 2 ) 逆向最大匹配法( r e v e r s em a x i m u mm a t e 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 t 1 5 】。 3 1 逐词遍历法 逐词遍历分词方法是将词典中的词条由长到短递减的顺序，逐个在待处理 的字串或句子中搜索，直到切分出所有的词为止。不论分词词典多大，都得把 整个分词词典匹配一遍。故这种方法的时间复杂度比较高，分词的速度慢、效 率不高。 4 ) 双向扫描法 双向扫描法的基本原理是分别用m m 法和r m m 法进行初步的切分，并将 m m 法切分的结果与r m m 法切分的结果进行比较，如果两种结果一致，则判定 切分正确；如果两种结果不一致，则采用人工干预的方式，或者记频度的算法， 或者结合上下文相关信息选取一种切分。该算法能发现所有的交集型歧义字段， 但对于正、逆向的扫描结果一致但实际切分不j 下确的字串仍然不能正确处理。 5 1 设立切分标志法 该方法首先在待切分字符串中识别出一些带有明显特征的词，并以这些词 作为断点，可将原字符串切分为较小的串后，再进行机械分词，从而减少匹配 的错误率。 6 ) 最佳匹配法 ，最佳匹配法的原理：在词典中按词的出现频率大小排列词条，高频率的词 排在前，低频率的词排在后，从而缩短分词词典的检索时间，达到最佳效果， 加快分词速度。 7 ) 二次扫描法 有统计表明，汉语中词的平均长度为1 8 3 。因此，每次从待切分的字符串 中取两个字符，比取分词词典中最大长度的子串来进行匹配的方法相比，前者 的效率更高。 1 4 武汉理工大学硕士学何论文 该方法的基本做法是：首先从待切分的字符串中取两个汉字记为s 仃，检查 分词词典中是否有这样一个词，它的前两个汉字和s 仃相同，若有的话，则取待 切分的字符串中的前三个汉字记为s 仃，重新在分词词典中查找前三个字相同的 词条，如果匹配成功则继续上述过程，直到进行了n 个汉字为止( 设n 为词典中 最长词所含汉字的个数) ，则切分出一个n 字词；如果匹配不成功则完成了一次 扫描；把s 仃中最后一个汉字去掉，使用m m 方法或r m m 方法进行第二次切分。 二次扫描法只是改变了m m 分词法从词条的最大长度开始匹配的做法，而 是从长度为2 的词条开始匹配，这样可以大量地减少匹配失败的次数，从而提 高了分词的效率。 2 1 2 基于统计的分词方法 基于统计的分词方法的基本原理：从形式上看，词是稳定的字的组合，因 此在上下文中，相邻的字，如果同时出现的次数越多，就越有可能构成一个词。 字与字相邻共同出现的频率或概率能够较好地反应成词的可信度。 当紧密程度高于某一个阀值时，便可认为此字组可能构成了一个词。这种 方法只需对字组合的频度进行统计，不需要切分词典，因而又叫做无词典分词 法。但这种方法也有一定的局限性，会经常抽出些共现频度高、但并不是词 的常用字组，例如“我的”，“你的”，“他的”等，并且对常用词的识别精 度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分词词典( 常 用词词典) 进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计 和串匹配结合起来，既发挥机械分词切分速度快、效率高的特点，又利用了基 于统计分词方法结合上下文识别生词、自动消除歧义的优点。 计算汉字间紧密程度的统计模型主要有：互信息、t 测试两种。 1 互信息 定义l ：对一包含汉字x 和y 的字符，x 和y 之间的互信息定义为 i ( x , d = k 器 ( 2 1 ) 式( 2 1 ) 中： i ( x ，y ) 表示汉字x 和y 的互信息： p ( x ，y ) 表示汉字x 和y 联合出现的概率； 1 5 武汉理工大学硕士学位论文 p ( ) ( ) 表示汉字x 出现概率： p ( y ) 表示汉字y 出现概率。 互信息体现了汉字之间结合关系的紧密程度，当紧密程度高于某一个阀值 时，便可认为此字组可能构成了一个词。在公式2 1 中，p ( x ，、p ( 的，p 0 0 可以通过以下公式计算得出： p ( x ，y ) ：n ( x y ) p ( x ) ：塑( 2 2 ) h 】，) ：幽 公式2 - 2 中，汉字串x ，y 和x y 出现的次数分别计为n ( x ) ，n m ，n ( x y ) ， 汉字串总长度为r l 。 而互信息则是用于定量估计两个汉字间的结合力：两汉字间互信息越大， 两个汉字结合的紧密程度越高，则就可以认为这俩个汉字可以组成一个词语： 互信息越小，结合的紧密程度越低，则俩个汉字组成一个词语的可能性就小。 2 ) t 测试原理 定义2 ：对有序汉字串x y z ，汉字y 相对于x 及z 的t 测试定义为 t x , r ( y ) 2 万雨p ( z 丽y ) 雨- p ( 丽y x ) ( 2 3 ) p ( z y ) ：z 关于y 的条件概率 p ( y x ) ：y 关于x 的条件概率 万2 ( 以z y ”：z 关于y 的方差 6 2 ( p ( y x ) ) ：y 关于z 的方差 从t 测试的定义，可知： a ：t 测试 0 时，字y 有与后继字符z 相连的趋势，值越大，相连趋势越 强； b - t 测试= o 时，不反映任何趋势； c ：t 测试 u p p e r l i m i t ) a d d q u e u e ( p r i o r q u e u e ，u r l ) ； ) 如果当前页面的内容的相关度介于u p p e r l i m i t 和l o w e r l i m i t 之间 e l s ei f ( s i m ( c u r r e n t c o n t e n t ，k e y s v e c t o r ) l o w e r l i m i t ) 如果锚文本和u r l 字符串中含有关键项 i f ( c h i l d u r l g e t s t r i n g ( ) c o n t a i n s ( k e y s ) l i c h i l d u r l g e t a n c h o r t x t c o n t a i n s ( k e y s ) ) a d d q u e u e ( p r i o r q u e u e ， u r l ) ： 以上条件都不满足，则应该根据子节点的预测相关度 来决定队列的归属 e l s ei f ( p o t e n t i a l s c o r e ( c h i l d u r l ) m i n p r i o r ) a d d q u e u e ( p r i o r q u e u e ， u r l ) ： e l s ei f ( p o t e n t i a l s c o r e ( e h i l d u r l ) m i n n o r m a l ) a d d q u e u e ( n o r m a l q u e u e ，u r l ) ； ) 如果当前页面的内容相关度小于l o w e r l i m i t e l s ei f ( s i m ( c