（计算机应用技术专业论文）基于统计的搜索引擎中文输入纠错技术研究.pdf

j 1 ；， 一- 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：7 弓枷冬 日期：锄加 。 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：1 吾铭鸭日期：乡刀口7 1 0 导师签名：妈风终 日期： 少f ，9 f f 9 o r 北京邮电大学硕士学位论文基于统计的搜索引擎中文输入纠错技术研究 基于统计的搜索引擎中文输入纠错技术研究 摘要 在已经到来的w e b2 0 时代，搜索引擎在互联网上扮演了越来越 重要的角色，而日益增多并且成熟的互联网用户对搜索引擎的要求也 越来越高，其功能也在不断丰富和完善当中，输入自动检查纠错功能 就是一项非常重要的附加技术，并且已经得到了较为广泛的应用和推 广。 对于中文搜索引擎来说，输入自动检查纠错功能是指，用户在输 入关键词进行搜索之后，如果搜索引擎在返回结果中计算出与此关键 词相似的另一形式( 如词组中出现同音不同字，或者某一错别字现象) 得到大量的搜索结果，用户将会在搜索结果页面看到系统提供的推测 到的关键词项。 针对以上问题，首次将一种完全通过分析上下文统计信息的方法 引入搜索引擎的输入纠错技术中( 未见文献报道) ，根据中文语言的 特点，对中文语料库建立了n g r a m 统计语言模型，并且对其进行了 详细的分析，确定了语言模型所必需的参数，以及对其进行了优化处 理，使其更加接近真实情况下的语言。研究中引入了t f f l d f 权重计 算方法，将初步统计语言模型得出的纠错检查结果再次计算比较，最 终得出优化的纠错结果。 以上所提出的理论模型，在以n u t c h 和h a d o o p 为基础搭建的分 布式搜索引擎平台上进行了实验验证，采用了不同规模数量级的语料 库( 数量级从1 0 0 k 左右到5 个g b 左右) ，将检查纠错的统计分析和 比较结果通过图表的方式进行展现，验证了完全通过上下文统计信息 来对进行中文搜索引擎的输入检查纠错是能够取得较好的效果的，并 且上下文语境信息越多，纠错的召回率和准确率也就越高。 关键词：搜索引擎输入纠错n g r a m 模型t f i d f 分布式计算 北京邮电大学硕士学位论文 基于统计的搜索引擎中文输入纠错技术研究 - 一一 北京邮电大学硕士学位论文 基于统计的搜索引擎中文输入纠错技术研究 c h i n e s es p e l l i n gc o i u 之e c t i o nr e s e a r c h i ns e a r c he n g i n e s b a s e do ns t a t i s t i c a lm o d e l a b s t r a c t n m o 一 一 l h es e a r c he n g i n el i a rt h ei n t e r n e th a sp l a y e dam o r ea n dm o r e i m p o r t a n tr o l ea s i nt h ed e v e l o p m e n to fw e b2 0 f o rt h en u m b e ro f s e a r c h e n g i n e u s e r sa r e g r o w i n gq u i c k l y , a n dt o g e t h e rw i t ht h e r e q u i r e m e n t s f o rs e a r c he n g i n e sa r eh i g h e ra n dh i g h e r ，i t s f u n c t i o n s c o n t i n u o u s l yi m p r o v e d t h es p e l l i n ga u t o c h e c k i n ga n dc o r r e c t i n g f u n c t i o ni sav e r yi m p o r t a n ta d d i t i o n a lt e c h n o l o g y , a n dh a sb e e na p p l i e d a n dp r o m o t e d w i d e l y i nt h ec h i n e s es e a r c he n g i n e ，t h ed e f i n i t i o no fs p e l l i n ga u t o c h e c k i n g a n dc o r r e c t i n gf u n c t i o ni st h a tw h e na u s e ri n p u ts o m ek e y w o r d st os e a r c h o ni n t e r n e tt h r o u g ht h es e a r c he n g i n e ，i tw i l lr e t u mal a r g en u m b e ro f s e a r c h i n gr e s u l t sw h i c hi n c l u d i n ga l lt h es i m i l a rw o r d st ot h o s eo r i g i n k e y w o r d s ( s u c ha st h ep h r a s e 印p e a r si nh o m o p h o n ed i f f e r e n tw o r d s ，o r s p e l l i n ge r r 0 0 ，a n du s e r sw i l ls e et h ek e y w o r dr e s u l tw h i c ht h es y s t e m s p e c u l a t e da n dp r o v i d e di nt h es e a r c hr e s u l t sp a g e a n g r a ms t a t i s t i c a ll a n g u a g em o d e lw h i c hb e e ns e tu pb a s e do na m e t h o dt h a ta n a l y s i sc o n t e x ts t a t i s t i c a li n f o r m a t i o nc o m p l e t e l yi sf i r s t l y i n t r o d u c e dt ot h ef i e l do fc h i n e s e s p e l l i n gc o r r e c t i o ni ns e a r c he n g i n e s i n t e r m so ft h ec h a r a c t e r i s t i c so fc h i n e s el a n g u a g e ，t h em o d e li s a l s o a n a l y z e dd e t a i l e d l yt od e t e r m i n e dt h en e c e s s a r yp a r a m e t e r s o nt h i sb a s i s ， t h el a n g u a g em o d e lw i l lb e o p t i m i z e da n dc l o s e rt or e a ll a n g u a g e t h em e t h o do ft h et f i d fw e i g h t i n g ，w h i c hc a l c u l a t ea n dc o m p a r e t h ep r e l i m i n a r yc h e c k i n gr e s u l t s ，i si n t r o d u c e da n dt h e nt h eb e t t e rr e s u l t s o f s p e l lc h e c k i n ga n dc o r r e c t i n gw i l lb er e t u r n e d a 1 lt h et h e o r e t i c a lm o d e l sp r o p o s e di nt h i sp a p e rw e r ea l lv e r i f i e d b a s e do nn u t c ha n dh a d o o pd i s t r i b u t e ds e a r c he n g i n ep l a t f o r m ( d a t as i z e f r o ma b o u t10 0 kt o5 g b ) ，a n da n a l y s i sr e s u l t sa r ep r e s e n t e db yt h ec h a r t 北京邮电大学硕士学位论文 基于统计的搜索引擎中文输入纠错技术研究 i tv e r i f i e dt h a tt h em o d e l sc a na c h i e v eg o o dr e s u l t sb yt h es t a t i s t i c a l a n a l y s i sa n dc o m p a r i s o nc o m p l e t e l yw h e nt h ei n p u tk e y w o r d sw e r ee r r o r , a n dt h em o r ec o n t e x t u a li n f o r m a t i o n ，t h eh i g h e re r r o rc o r r e c t i o nr e c a l l a n dp r e c i s i o n k e y w o r d s ：s p e l l i n gc o r r e c t i o n ，n g r a m sm o d e l ，t f i d fw e i g h t ， s e a r c he n g i n e ，d i s t r i b u t e dc o m p u t i n g 北京邮电大学硕七学位论文 目录 目录 第一章引言l 1 1 研究背景与意义1 1 2 研究现状分析2 1 3本文的主要研究内容。5 1 4 本文的组织结构5 第二章搜索引擎及其应用技术概述7 2 1 搜索引擎的基本原理与体系结构7 2 1 1网页爬取7 2 1 2 预处理阶段9 2 1 2 1 关键词的提取9 2 1 2 2网页去重9 2 1 2 3 链接分析9 2 1 2 4网页查询结果排序1 0 2 1 3 查询结果1 0 2 1 4搜索引擎的体系结构1 1 2 2 l u c e n e 全文检索工具包1 2 2 2 1 l u c e n e 的简介一1 2 2 2 2 l u c e n e 全文检索包与本文研究内容的关系1 3 2 3 本章小结1 4 第三章统计语言模型的分析与建立1 5 3 1 基于n g r a m 的语言模型1 5 3 2 n 值的选定1 6 3 3 模型的建立18 3 4 数据稀疏问题2 0 3 4 1 齐普夫( z i p f ) 定律2 0 l 北京邮电大学硕士学位论文 目录 3 4 2平滑技术的引入2 l 3 5 输入关键词的分析与统计信息的比较2 2 3 6 本章小结2 3 第四章关键词的权重统计比较2 5 4 1 词频率逆向文档频率( t f i d f ) 2 5 4 2 权重的分析比较2 6 4 3 本章小结2 6 第五章实验平台与实验数据分析2 9 5 1理论模型与实验平台搭建的选择2 9 5 2n u t c h + h a d o o p 实验平台。2 9 5 2 1 n u t c h 和h a d o o p 概述2 9 5 2 2 实验环境31 5 2 3 系统架构31 5 3 实验标准评价3 2 5 4 实验数据集3 3 5 5 实验数据统计3 3 5 5 1初始状态下的查询成功率。3 4 5 5 2建立语言模型后的数据分析3 4 5 5 3 分析关键词权重后的统计结果3 6 5 6 实验数据分析3 7 5 7本章小结。3 7 第六章全文总结与研究展望3 9 6 1 全文总结3 9 6 2进一步的研究4 0 参考文献4 3 致 谢4 7 攻读学位期间发表的学术论文目录4 9 尹 r 北京邮电大学硕士学位论文 目录 附录1 中文分析器核心代码5 l i i i 北京邮电大学硕士学位论文 目录 i v 一 广 北京邮电大学硕士学位论文第一章引言 1 1研究背景与意义 第一章引言 搜索引擎( s e a r c he n g i n e ) 是信息检索技术的一项重要应用，它的主要工作 是自动搜寻w e b 服务器的信息，将信息进行分类、建立索引，然后把索引的内 容存放到数据库中，便于以查询和利用的方式提交给用户。 2 0 世纪9 0 年代初期，互联网的发展刚刚起步，网络信息相对较少，信息的 检索和查找比较容易，然而随着互联网爆炸性的发展，普通网络用户想找到所需 的信息已经无从查起，这时为满足大众信息检索需求的专业搜索网站便应运而 生。 现代意义上的搜索引擎的祖先，是1 9 9 0 年由蒙特利尔大学学生a l a ne m t a g e 发明的删e 【l 】。虽然当时w o r l dw i d ew e b 还未出现，但网络中文件传输还是 相当频繁的，而且由于大量的文件散布在各个分散的f t p 主机中，查询起来非 常不便，因此a l a ne m t a g e 想到了开发一个可以以文件名查找文件的系统，于是 便有了a r c h i e 。 a r c h i e 工作原理与现在的搜索引擎已经很接近，它依靠脚本程序自动搜索网 上的文件，然后对有关信息进行索引，供使用者以一定的表达式查询。由于 a r c h i e 深受用户欢迎，受其启发，美国内华达s y s t e mc o m p u t i n gs e r v i c e s 大学于 1 9 9 3 年开发了另一个与之非常相似的搜索工具，不过此时的搜索工具除了索引 文件外，已能检索网页。 当时，“机器人 一词在编程者中十分流行。电脑“机器人”( c o m p u t e rr o b o t ) 是指某个能以人类无法达到的速度不间断地执行某项任务的软件程序。由于专门 用于检索信息的“机器人 程序象蜘蛛一样在网络间爬来爬去，因此，搜索引擎 的“机器人 程序就被称为“蜘蛛”程序。 世界上第一个用于监测互联网发展规模的“机器人 程序是m a t t h e wg r a y 开发的w r o r l dw i d ew e bw a n d e r e r 。刚开始它只用来统计互联网上的服务器数量， 后来则发展为能够检索网站域名。 与w a n d e r e r 相对应，m a r t i nk o s t e r 于1 9 9 3 年1 0 月创建了a l i w e b ，它是 a r c h i e 的h t t p 版本。a l i w e b 不使用“机器人”程序，而是靠网站主动提交 信息来建立自己的链接索引，类似于现在我们熟知的y a h o o 。 随着互联网的迅速发展，使得检索所有新出现的网页变得越来越困难，因此， 北京邮电大学硕： 学位论文第一章引言 在m a t t h e wg r a y 的w a n d e r e r 基础上，一些编程者将传统的“蜘蛛”程序工作原 理作了些改进。其设想是，既然所有网页都可能有连向其他网站的链接，那么从 跟踪一个网站的链接开始，就有可能检索整个互联网。到1 9 9 3 年底，一些基于 此原理的搜索引擎开始纷纷涌现，其中以j u m p s t a t i o n 、1 1 l ew o r l dw i d ew e bw o r m ( g o t o 的前身，也就是今天o v e r t u r e ) ，和r e p o s i t o r y - b a s e ds o f t w a r ee n g i n e e r i n g ( r b s e ) s p i d e r 最负盛名。 然而j u m p s t a t i o n 和w w ww o r m 只是以搜索工具在数据库中找到匹配信息 的先后次序排列搜索结果，因此毫无信息关联度可言。而r b s e 是第一个在搜索 结果排列中引入关键字串匹配程度概念的引擎。 最早现代意义上的搜索引擎出现于1 9 9 4 年7 月。当时m i c h a e lm a u l d i n 将 j o h i ll c a v i t t 的蜘蛛程序接入到其索引程序中，创建了大家现在熟知的l y c o s 。同 年4 月，斯坦福( s t a n f o r d ) 大学的两名博士生，d a v i df i l o 和美籍华人杨致远( g e r r y y a n g ) 共同创办了超级目录索引y a h o o ，并成功地使搜索引擎的概念深入人心。 从此搜索引擎进入了高速发展时期。目前，互联网上有名有姓的搜索引擎已达数 百家，其检索的信息量也与从前不可同日而语。 为了提高搜索效率和方便信息查询，在搜索技术上越来越成熟的互联网公司 研发出了更多的附加搜索功能，比如：网页快照( c a c h e ) 、相关搜索等。搜索 引擎的输入拼写检查纠错功能也是一项重要的附加功能。 搜索引擎的输入自动检查纠错【2 】功能是指，用户在输入关键词进行搜索的时 候，如果搜索引擎在返回结果中计算出与此关键词相似的另一形式( 如词组中出 现同音不同字，或者某一错别字现象) 得到大量的搜索结果，用户将会在搜索结 果页面看到系统推测提供的关键词项。 搜索引擎技术是当今互联网时代的一项重要应用，研究搜索引擎本身的技术 对着互联网技术的发展，乃至信息检索技术的发展有着重要的意义，搜索引擎的 输入自动检查纠错功能集中了信息检索，自然语言处理两大学科的关键技术，对 增强目前搜索引擎的实用性，提高检索的效率有着十分重要的作用。 1 2研究现状分析 搜索引擎中的自动纠错检查功能结合了计算语言学的信息检索和文本自动 勘校两方面的应用，也包括了信息论( i n f o r m a t i o nt h e o r y ) 在自然语言处理技术 中的应用。 在针对英文的检查纠错【3 】【4 】中，由于英文的每个单词之间都有空格，所以不 2 北京邮电大学硕士学位论文 第一章引言 用考虑到分词问题，所以只需要对每个单词进行拼写检查( s p e l l i n gd e t e c t i o n ) ， 常用的方法是利用编辑距离( l e v e n s h t e i nd i s t a n c e ) 来确定词与词之间的相似 程度，另外考虑每个词在文本中的统计信息来最终判断错误拼写。而对于中文， 考虑到汉语语言的特殊性，首先要对文本进行切割分词，然后再进行错误检查和 校正，常见的方法包括基于字典【5 】【6 】和基于文本统计信息两种。 基于字典的分词方法【7 】又称作机械分词方法，它是按照一定的策略将待分析 的汉字串与一个“充分大的机器词典 中的词条进行匹配，若在词典中找到某个 字符串，则匹配成功。按照扫描方向的不同，该分词方法可以分为正向匹配和逆 向匹配；按照长度的不同，可以分为最大匹配和最小匹配。常见的几种基于词典 的分词方法为：正向最大匹配算法【引、逆向最大匹配算法【9 】和全二分最大匹配算 法【嘲。基于字典的分词算法优点是易于实现，在对精确率要求不高的系统中得 到了很好的应用。其缺点在于由于字典是在分词之前准备的，其规模和内容受到 了限制，对于未登录词的补充较难实现，并且需要一定的维护代价，而随着网络 和自然语言的飞速发展，仅仅依靠不断扩大的字典的收录规模来进行纠错越来越 难以满足搜索引擎所要求的效率。 基于统计信息的分词方法较为常见的有，基于互信息的概率统计算法【1 1 1 ， n g r a m 算法【1 2 】，基于组合度的汉语分词决策算法【1 3 】等等。基于统计的分词方法 优点【1 2 】在于它可以从已有的大量实例中进行归纳总结，分析语言内在的关联信 息，将其加入到统计模型中去。简单的统计方法不需要词典，而是通过训练语料 的迭代，建立统计模型。但统计方法本身也有一定的局限性，尤其是对常用词的 识别精确度较差。 文献 1 4 1 5 】【1 6 1 7 】中文分词的方法原理进行了大量的研究。 搜索引擎的输入检查纠错功能是分词技术与文本校对技术的结合，中文文本 校对主要面向的是含有错误的文本【l 引，因此，汉语自然语言理解的研究也就成 了计算机中文文本自动校对的基础。由于汉语与英语本质上的不同，在对中文文 本进行查错纠错分析时，必须要基于自然语言的理解技术，通过研究上下文间 的依存关系才能实现，这显然是比较复杂和困难的，某些适于英文单词校对的技 术和方法对汉语文本并不太适用。目前，国内有不少单位开展了中文文本校对理 论和技术的研究，除了微软亚洲研究院、i b m 中国研究中心等科研院所外，一些 有实力的高新技术公司，如北大方正公司、金山公司等都丌展了中文文本校对软 件的研究与开发。 自动纠错是文本自动校对的一个重要组成部分，它为自动查错时侦测出的错 误字符串提供修改建议，辅助用户改正错误。修改建议的有效性是衡量自动纠错 3 北京邮电大学硕士学位论文第一章引言 性能的主要指标，它有两点要求： 1 、提供的修改建议中应该含有正确或合理的建议； 2 、正确或合理的修改建议应尽可能排列在所有建议的前面。因此，纠错修 改建议的产生算法及排序算法是自动纠错研究的两个核心课题。 由于中文文本自动校对理论和技术尚不太成熟，自动纠错研究的论述还不多 见。东北大学【l9 】采用模式匹配方法对长词进行纠错处理，但没有充分利用出错 字符串的特征，算法计算量大。i b m 中国研究中心【2 0 】提出一种替换字表结合主 词典，通过加字和换字对侦测出来的错误字符串提供修改建议的纠错算法，但该 算法的纠错建议局限于替换字表，没有考虑。上下文启发信息，主要考虑对错字 这种错误类型进行纠错，对漏字、多字、易位、多字替换、英文单词拼写等错误 类型的纠错能力较弱。山西大学【2 l 】提出了一种基于似然匹配的纠错建议候选集 产生算法，对漏字、多字、易位、多字替换等错误类型的纠错能力有了较大的提 高。 目前的中文搜索引擎输入检查纠错功能是以基于字典的中文分词和文本校 对为基础，以目前市场上最流行的中文搜索引擎百度( w w w b a i d u c o m ) 为例， 根据每个字词最常见的拼法来检查查询。当该检查纠错功能计算出使用替代拼写 可以得到数量更多的相关搜索结果时，就会在您的搜索结果页顶部显示“您要找 的是不是：( 更常见的拼写) ”。如图1 1 所示： 一“” “o ? “= ”“，”“? 叩p “- “、 臻l 荟震攫褰- j 绢玛l 建 新闻同页贴吧知道m p 3 图垃塑题 鼬l 乏s 露度j 隶奥遣汇“匪重! 三要星薹蔓里圈 理亘鏖逞盘圭垂 您要找的是不是：j i 直塞重金 图1 - 1 百度搜索纠错示例 百度【6 】【2 2 1 是将分词词典里面每个词条利用拼音标注程序标注成拼音，然后形 成同音词词典，百度的这个同音词典是自动生成的，而且没有人工校对，在自动 生成同音词典的过程中，百度不是根据对一篇文章标注拼音然后在抽取词汇和对 应的拼音信息获得的，而是完全按照某个词典的词条来标注音节的，所以两个词 典是同样大的，而且这个词典也随着分词词典的增长而在不断增长。至于标注过 程中多音字百度没有考虑，如果是多音字就标注成多个发音组合，通过这种方式 形成同音词词典。这就是百度的拼写检查错误功能的原理。 4 北京邮电大学硕士学位论文 第一章引言 1 3本文的主要研究内容 针对以上所提出的问题和目前搜索引擎功能发展的现状，输入检查纠错功能 是一项非常重要的功能，但是由于基于字典的方法必须靠维护一套数量级非常庞 大的字典，不符合互联网的发展规律，而基于统计的方法是依据互联网的发展趋 势，以网络用户的数据作为参考，在这个信息爆炸，咨询更新速度极快的时代， 基于统计的方法更符合人们的使用网络习惯。 在此基础上提出将一种完全基于上下文统计信息的文本校对方法应用于中 文信息检索领域中的自动输入检查纠错。依据提出的统计思想，对中文建立统计 统计语言模型，在此模型的基础上对输入的关键词进行比较分析。 提出的所有理论模型，设计思想最终的实验方案都将在n u t c h 和h a d o o p 的分 布式云计算平台上搭建的搜索引擎上进行实现，并且统计分析检查纠错的结果， 最终通过不同数量级别的实验数据得出的纠错结果对论文研究内容进行展示。 1 4本文的组织结构 本文的组织结构共分为六章。 第一章为本文的引言部分，主要介绍搜索引擎技术的发展历程，研究现状以 及问题，另外，介绍搜索引擎中重要的附加功能自动检查纠错，介绍了其研究方 法，以及其应用现状，并且描述了本文的大致研究内容。 第二章介绍了关键的搜索引擎及其应用技术，主要包括了搜索引擎的基本技 术原理，分别阐述了各个技术模块的主要任务，以及整体的体系结构，并且介绍 了l u c e n e 这个非常成熟和流行的信息检索工具包。 第三章介绍了统计语言模型相关的内容，主要包括了基于统计的思想，以及 统计语言模型的介绍，根据实际情况，选定了语言模型的各种参数，以及介绍了 语言模型优化的思想。在建立统计模型的基础上，对输入的错误关键词进行初步 统计分析，得到初步的筛选结果，并且给出了简单的示例。 第四章是在第三章建立的统计语言模型的基础上，对初步的筛选结果进行优 化再处理，具体的处理思想是利用初步关键词集合第一次搜索出来的比较结果， 然后利用各自的权重得出最终的优化结果。 第五章主要内容是实验的平台环境介绍和实验数据统计分析部分，主要包括 了系统的体系结构，各个模块的组成和功能介绍，以及评价实验结果的标准介绍， 测试数据集的组成、来源以及使用方法，最后将通过具体的实验结果进行不同的 学位论文第一章引言 全文的总结和展望部分，在此对本文的研究内容进行归纳总结，并 的研究工作做了进一步的展望。 6 北京邮电大学硕士学位论文 第二章搜索引擎及其应用技术概述 第二章搜索引擎及其应用技术概述 2 1搜索引擎的基本原理与体系结构 搜索引擎是一个网络应用软件系统，它的工作并不是直接在互联网上进行检 索，它搜索的范围实际上是预先储存好的网页索引数据库。如今主流的搜索引擎 也不能真正理解网页上的内容，它只能机械地匹配网页上的文字。 对它的基本要求如下： 能够接受用户通过浏览器提交的关键字或者关键词，记作q ，例如“甲流一， “北京奥运会，“唐诗三百首一等等。 在一个用户可以接受的时间内返回一个和该用户查询匹配的网页信息摘要 列裂2 3 1 ，记作l 。这个列表中的每一条目至少包含三项内容( 标题，网址链接， 摘要) ，如果又需要还会保存有该网页的缓存存放链接。 图2 - 1 搜索流程之一 目前通用的高质量搜索引擎的基本原理都是通过如下图所示的三段式的工 作流程，即网页爬取，预处理和查询。 k 网页爬取 彳k 预处理 k 。 查询 矿n旷 2 1 1 网页爬取 图2 - 2 搜索流程之二 搜索引擎系统所操作的数据不但包括内容不可预测的用户查询，还要包括在 数量上动态变化的海量网页，并且这些网页不会主动送到系统来，而是需要由系 统去抓取。 首先，我们考虑的是事先抓取，还是当用户查询的时候再去抓取，即及时抓 取，一般情况下，从网上下载一篇网页大约需要1 秒钟左右，因此如果在用户查 7 北京邮电大学硕士学位论文第二章搜索引擎及其应用技术概述 询的时候即时去网上抓来成千上万的网页，一个个分析处理，和用户的查询匹配， 不可能满足搜索引擎的响应时间要求。不仅如此，这样做的系统效益也不高( 会 重复抓取太多的网页) ；面对大量的用户查询，不可能想象每来一个查询，系统 就到网上“查询 一次。因此我们看到，大规模搜索引擎的基础应是一批预先搜 集好的网页( 直接或者间接) 。这一批网页如何维护? 可以有两种基本的考虑。 定期搜集，每次搜集替换上一次的内容，称之为“批量搜集。另一种称为 增量搜集，开始时搜集一批，往后只是搜集以下三类型的网页： ( 1 ) 新出现的网页； ( 2 ) 在上次搜集后有过改变的网页； ( 3 ) 发现自从上次搜集后已经不再存在了的网页，并从库中删除。 以上是系统网页数据库维护的基本策略。在具体搜集过程中，抓取一篇篇的 网页，具体的思想是将网页集合看成是一个有向图，搜集过程从给定起始u r l 集合s ( 或者说“种子 ) 开始，沿着网页中的链接，按照一定的遍历策略，不 停的从s 中移除u r l ，下载相应的网页，解析出网页中的超链接u r l ，看是否已 经被访问过，将未访问过的那些u r l 加入集合s 。整个过程可以形象地想象为一 个蜘蛛( s p i d e r ) 在蜘蛛网( w e b ) 上爬行( c r a w l ) 。后面我们会看到，真正的 系统其实是多个“蜘蛛”同时在爬。 网络爬虫在爬取网页的时候一般采用的两种策略：深度优先策略和广度优先 策略。广度优先搜索算法是指爬虫程序会先抓取起始网页中的链接的所有网页， 然后选择其中的一个链接网页，继续抓取在此网页中链接的所有网页，依次类推。 该算法策略保证一个服务器上至少有一篇文档加入到索引数据库，它降低同一服 务器被访问的频度，缺点是不能深入文档。另外由于该方法可以让网络爬虫并行 处理，提高了爬取取速度，因此该方法是最常用的方式；深度优先算法是指爬虫 程序会从互联网的一个起始页开始，提取出该页所有的u r l ，再从一个未被访问 的u r l 出发，深度优先遍历u r l ，直到该起始页相连的页面都被访问，处理完这 条线路之后再转入下一个起始页，继续遍历链接。直至所有的u r l 被访问。该算 法策略能较好地发掘文档结构，如互相参照的链接结构，而且相对比较稳定，缺 点是有可能进入无限循环。 在实际的搜索引擎爬取过程中，为了保证获取网页的及时性，全面性，还有 多个爬取程序的分工和合作问题，往往有复杂的控制机制【2 4 1 。如g o o g l e 在利用爬 虫程序获取网络资源时，是由一个认为管理程序负责任务的分配和结果的处理， 多个分布式的爬虫程序从管理程序活动任务，然后将获取的资源作为结果返回， 北京邮电大学硕士学位论文 第二章搜索引擎及其应用技术概述 并从新获得搜集任务。 2 1 2预处理阶段 通过第一步的网页爬取阶段，得到海量级别的原始网页集合，但是这距离一 个搜索引擎要求的可以搜索的数据库之间还有很大的差距，在提供给用户查询之 前，搜索引擎需要提供一个中间程序，将原始的网页数据库转换为一种可以供查 询系统进行检索的合适的数据结构组成的数据库，而最有效的数据结构就是“倒 排文件 ( i n v e r t e df i l e ) ；倒排文件的数据结构是用文档中的关键词作为索引， 而把海量网页集合转换为倒排索引文件的过程就是本阶段预处理需要做的工作， 其中包含的主要问题有：关键词的提取，网页去重，链接分析和查询结果排序等。 2 1 2 1 关键词的提取 预处理阶段的基本任务，就是要提取出网页源文件的内容部分所含的关键 词。对于中文来说，就是要根据一个词典，用一个所谓“切词程序 ，从网页 文字中切出所含的词语来。一般来讲，我们可能得到很多词，同一个词可能在 一篇网页中多次出现。从效果和效率的角度来考虑，不应该让所有的词都出现在 网页的表示中，要去掉诸如“的，“在 等没有内容指示意义的词，称为“停 用词 ( s t o pw o r d ) 。这样，对一篇网页来说，有效的词语数量大约在2 0 0 个左右。 2 1 2 2 网页去重 由于数字化和网络化给网页的复制以及转载和修改再发表带来了便利，因此 w e b 上的信息存在大量的重复现象【2 5 1 。据统计分析表明，网页的重复率平均大约 为4 。也就是说，当你通过一个u r l 在网上看到一篇网页的时候，平均还有另外3 个不同的u r l 也给出相同或者基本相似的内容。这种现象对于广大的网络用户来 说是有正面意义的，因为有了更多的信息访问机会。但对于搜索引擎来说，则主 要是负面的；它不仅在搜集网页时要消耗机器时间和网络带宽资源，而且如果在 查询结果中出现，无意义地消耗了资源，也会引来用户的抱怨。因此，消除内容 重复或主题内容重复的网页是预处理阶段的一个重要任务。 2 1 2 3 链接分析 传统的互联网应用技术大多是基于文档内容的，与经典的信息检索技术和数 据库技术有着密切的关系。互联网环境中的另一种信息正越来越受到研究者的注 意，即互联网的超链接结构【2 6 】。这种信息的有效利用为当今复杂的互联网信息 9 北京邮电大学硕士学位论文第二章搜索引擎及其应用技术概述 查找提供了方便。链接分析已被用来作为衡量主题网页的权威性、网页知名度和 网页间距离的有效工具。 2 1 2 4 网页查询结果排序 用户提交了查询的关键词后，搜索引擎返回给用户的结果信息列表的顺序是 一个非常关键的问题。由于不同的用户有着千变万化的需求，所以返回的结果信 息肯定不是所有用户都能满意的，或者说达到最高的满意度，所以搜索引擎力争 的结果是追求一种统计意义上满意度。 对查询结果的排序要考虑的因素有很多，这是在预处理阶段完成的很重要的 一项任务。在用户查询之前，预处理阶段需要做的就是给所需要查询的所有网页 赋以一个独特的网页权重值，而人们评价一个网页的重要性的方式，一般就是“引 用次数”来作为参考标准。“引用的概念在以h t m l 格式存在的网页超链接之 间得到最好的体现。例如，作为g o o g l e 核心技术f l 勺p a g e r a n k 2 7 】思想就是这方面 的最典型代表。 2 1 3 查询结果 将原始的海量网页集合经过预处理阶段，得到的可以直接可以查询的倒排索 引结构的文件。用户通过提供关键词或者关键词集合，查询服务将提供包含以下 三个方面的工作： 原始网页文档 u r l 、标题和网页摘要 网页编号 网页的重要性排序 搜索引擎返回给用户的是一个有序的条目列表，每一个条目有三个基本的元 素：标题，网址和摘要。其中的摘要需要从网页正文中生成。一般来讲，响应查 询的时候，根据查询词在文档中的位置，提取出周围的文字来，在显示时将查询 词标亮。这是目前大多数搜索引擎采用的方式。为了保证查询的效率，需要在预 处理阶段分词的时候记住每个关键词在文档中出现的位置。另外，网页列表的 排序是根据用户提交的查询与查询结果的相关度来确定的，这个相关度的评价标 准有两个，一个是每一个词在该文档中出现的次数，即词频，而倒排文件中每个 倒排表的长度则对应着一个词所涉及的文档的篇数，即文档频率。然而，由于网 页编写的自发性、随意性较强，仅仅针对词的出现来决定文档的顺序，在w e b 上做信息检索表现出明显的缺点，需要有其他技术的补充。这方面最重要的成果 就是前面提到过的p a g e r a n k 。通过在预处理阶段为每篇网页形成一个独立于查询 l o 北京邮电大学硕士学位论文 第二章搜索引擎及其应用技术概述 词( 也就和网页内容无关) 的重要性指标，将它和查询过程中形成的相关性指标 结合形成一个最终的排序，是目前搜索引擎给出查询结果排序的主要方法。 以上是搜索引擎的工作原理，本文研究的主要内容是搜索引擎的输入自动检 查纠错功能，其中主要涉及的技术都是在预处理阶段完成的，比如涉及到的关键 词提取和查询结果排序的算法思想。 2 1 4搜索引擎的体系结构 根据以上提出的搜索引擎工作原理，以下是整个系统的体系结构： 图2 - 3 搜索引擎体系结构 户 北京邮电人学硕士学位论文第二章搜索引擎及其应用技术概述 2 2l u c e n e 全文检索工具包 2 2 1l u c e n e 的简介 l u c e n e 【2 8 】【2 9 1 是个基于j a v a 的全文信息检索工具包，它不是一个完整的搜 索应用程序，而是为你的应用程序提供索引和搜索功能。l u c e n e 目前是a p a c h e j a k a r t a 家族中的一个开源项目，也是目前最为流行的基于j a v a 开源全文检索 工具包。l u c e n e 的目的是软件开发工程师以及研究员提供一个简单易用的工具 包，以方便地在目标系统中实现全文检索的功能，或者是以此为基础建立起完整 的全文检索引擎。 l u c e n e 的原作者是d o u gc u t t i n g ，他是一位资深的全文索引检索领域的专 家，曾经是v - t w i n 搜索引擎的主要开发者，其后他在e x c i t e 担任高级系统架构 设计师，目前从事于一些i n t e m e t 底层架构的研究。 目前，经过多年的发展，l u c e n e 在全文检索领域已经有了很多的成功案例， 并且积累了良好的声誉。基于l u c e n e 的全文检索产品和应用l u c e n e 的项目在世 界各地已经非常之多，其中比较知名的如下几例： e c l i p s e ：主流j a v a 开发工具，其帮助文档采用l u c e n e 作为检索引擎； j i v e ：知名论坛系统，其检索功能基于l u c e n e 。 在以上案例中，开源应用占了很多一部分，但是更多的还是商业化产品和网 站，l u c e n e 的出现，一定程度地推动了全文检索技术在各个行业或者领域中的 更深层次地应用。 l u c e n e 能够为文本类型的数据建立索引，所以你只要能把你要索引的数据 格式转化为文本的，l u c e n e 就能对你的文档进行索引和搜索。比如你要对一些 h t m l 文档，p d f 文档进行索引的话你就首先需要把h t m l 文档和p d f 文 档转化成文本格式的，然后将转化后的内容交给l u c e n e 进行索引，然后把创建 好的索引文件保存到磁盘或者内存中，最后根据用户输入的查询条件在索引文件 上进行查询。不指定要索引的文档的格式也使l u c e n e 能够几乎适用于所有的搜 索应用程序。 图2 4 表示了搜索引擎的应用程序与l u c e n e 软件