（计算机应用技术专业论文）反馈式ftp搜索引擎的实现.pdf

摘要 人类社会已经步入了一个信息量高速增长的信息化时代。搜索引擎技术使得 人们能够更方便的寻找信息。但是，信息的持续增长让传统的搜索引擎也显得难 于处理，为了解决海量w | e b 信息的搜索问题，人们提出了新一代搜索引擎技术 的概念。 本文所研究的反馈式搜索引擎( f s e ) 正是新一代的搜索引擎技术的一种， 文章展示说明了反馈式搜索引擎框架的概念，工作原理和核心算法。同时，本文 介绍了一个开源搜索引擎n u t c h ，并且参考它的结构和解决方案实现了一个反馈 式f t p 搜索引擎。该f t p 搜索引擎采用了内容相关性挖掘算法作为其实现反馈 式功能的核心算法，这个算法对用户使用搜索引擎期间的点击行为作出合理的统 计分析，从而提高返回结果的质量。对于搜索引擎技术来说，考虑用户的点击行 为并做相关性挖掘工作是一个很有意义的尝试和创新。最后，文章根据反馈式搜 索引擎框架的优缺点和有待改进的地方做出进一步总结和展望。 关键词： n u t c hf t p 搜索引擎 内容相关性挖掘反馈式点击行为 a b s t r a c t n o ww eh a v ee n t e r e da ni l 】f c i m a t i o nw o d di nw 1 1 i c ht l l ei 1 1 f o 衄a t i o ni sg r o w i n g i nah i g hs p e e d t h es e a r c he n g i n em a d eu ss e a r c ht h ei n f o 册a t i o ne a s i l y b u t ，t h ef a s t g r o w i n gi 1 1 f o n n a t i o nm a k e st h e o l ds e a r c he n g i i l eu 1 1 a b l et ow o r kw e l l t bs 0 1 v et h e p r o b l e mo fs e a r c l l i n gt h eh u g ew e bi n f o 衄a t i o l l ，p e o p l ep r o p o s e dt h ec o n c e p t i o no f t h en e ws e a r c he n g i l l et e c l u l o l o g y i nt 址sd i s s e z t a t i o n ，t h ef e e d b a c ks e a r c he n g i n e ( f s e ) i so n eo ft h en e ws e a r h e n g i n e s w ew i us h o wt h ei d e ao ff s e 丘j a m e w o r l ( ，a sw e l la si t sw o r l d n gp m i p l e a 1 1 dc o r ea l g o r i t h l l l i nt h em e a n t i m e ，w ew i l li n 仃o d u c ea no p e ns o u r c es e a r c he n g i n e n u t c h ，a n dd e v e l o paf e e d b a c kf t ps e a r c he n g i n ec o n s u l t i n gi t ss 仃u c t i l r ea n ds o l u t i o n t h ef t ps e a r c he n g i n eu s e sc o n t 肌tr e l e v a n c em i n i n ga l g o r i t h ma sm ec o r e a l g o r i t mi nr e a l i z i n gi t sf e e d b a c k 如n c t i o n t 1 1 i sa l g o r i t h mt a k e sc a r eo fn o to n l ym e k e y w o r d ，b u ta l s ot 1 1 ec l i c k m go fu s e r sw h i l et h e ya r eu s i r 坞t h es e a r c he n g i n e ，i nt l l i s w a y ，i ta c l l i e v e st h ep u 印o s et ou p g r a d em eq u a l i 够o fr e t u m e dr e s u l t f o rm es e a r c h e n g i n e ，t h ei d e ao fc o n s i d e r i n gu s e r s c l i c l ( i n ga n dm i i l i n gi t sr e l e v a n c ei sa m e a i l i i l g m lt l ya n di 1 1 1 1 0 v a t i o n a tl a s t ，w ew i l lm a k ea 如r t h e rs a 秽a 1 1 dp r o s p e c t a b o u tm ea d v a n t a g e sa i l dd i s a d v a n t a g e sa l o n gw i t ht h e6 e l dn e e d e di m p r o v e m e mo f t b ef s e k e yw o i 之d s ：n u t c h ，f t ps e a r c he n g i n e ，c 0 n t e mr e l e v a l l c em i n i n f e e d b a c k ， c l i c k i i l g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：哆每域签字日期： 加c 纩 年6 月6 日 学位论文版权使用授权书 本学位论文作者完全了解苤鲞盘堂有关保留、使用学位论文的规定。 特授权苤鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：罗天戊 签字日期：伽口岁年6 月占日 导师签名： 强勉儿 签字日期：冽；年6 月6 日 第一章绪论 1 1 研究的背景和意义 第一章绪论 当今社会是一个快速发展的信息时代，信息的价值早已获得人们的认同，并 且在人们的生活中显得越来越重要。而随着信息量呈几何级数的猛烈增长，人们 要从如此大信息量的网络中获取对自己有价值的信息却显得越来越困难了。搜索 引擎技术的诞生使得人们脱离了原始的人工查找信息的方式，依赖搜索引擎的帮 助，信息搜集的速度和质量都有了很大的提高。 随着海量的信息量仍然在不断增长，传统搜索引擎的返回结果也显得越来越 难以驾驭。对于使用某一些关键词的搜索，经常会返回很多不同领域的结果，这 是由于不同领域的词语有所重叠造成的。而且随着各种领域知识的不断发展，网 络的不断发达，以及新的领域不断涌现，重叠的词语也会越来越多。这使得传统 的搜索引擎返回的结果包含来自众多领域的文档超链接，由用户人工处理、辨认 这些众多的返回结果从而找到自己需要的链接并不是一个好的办法。 举个例子来说，在w w w g o o g l e c n 中输入关键词“罗马”则会收到约两千八 百万条返回结果，仅仅第一页就包含民族，体育，城市，公司，影视，历史，论 坛及旅游等来自众多领域的链接。这种现象对于传统的搜索引擎是没有办法克服 的，而我们唯一能做到的就是在用户端输入关键词的时候增加限定词从而获得目 标领域的返回结果。比如我们可以输入“罗马帝国”这样的关键字组合以获得 历史相关的返回结果，而这么做是以牺牲不包含“帝国”却与历史有关的返回结 果为代价的，而且仍然会得到来自其他领域的链接。 而本文提到的反馈式搜索引擎却不必做出这种牺牲，这是由它的工作原理决 定的。由于它在平时工作时就考虑除关键词外的用户点击行为，因此它能将用户 的点击行为按照一定的方法进行存储，并且在用户做出点击行为以后反馈出它认 为相关的结果。这个就是基于内容相关性挖掘的反馈式搜索引擎的根本理念，在 以后的章节中将会有详细的介绍。 第一章绪论 1 2 搜索引擎的研究状况 搜索引擎伴随着信息技术的出现而出现，在信息大爆炸的今天则一跃成为了 互联网的主角之一，搜索引擎的发展史是一部互联网的繁荣史： 2 0 世纪9 0 年代初，当时万维网还没有出现，曾经有过几个工具用来查 询散布在各个主机中的文件，有觚m e ，g o p h e r 等。随着w e b 技术的普 及而不再适用。 1 9 9 4 年1 月既可搜索又可浏览的分类目录e i n e tg a l a x y ( t r a d e w a v e g a l a x y ) 上线，同年4 月m o o 目录诞生，并开始支持简单的数据库查 询。这时候仍然是简单的目录导航系统，并且其内容都需要人工的维护。 l y c o s 推出了基于r o b o t 的数据发现技术，并且使用了结果的相关性排序 和自动摘要技术，i n f o s e e k 也是同时期的重要代表。他们被认为是搜索 引擎史上的一个重要进步。 1 9 9 5 年1 2 月推出的m t a s t a 搜索引擎，支持自然语言搜索，具备了网 页内容分析，智能处理等能力，并且实现了高级搜索语法( a n d ，0 rn o t 等) 。被认为具有划时代的意义 1 9 9 8 年l o 月最流行的搜索引擎g o o g l e 诞生。 虽然目前传统的搜索引擎基本上可以满足大多数用户的需要，但是在可以预 见的未来，高速增长的信息将会使得传统搜索引擎的可使用性大大降低。而实际 上，对于某一些词汇，传统的搜索引擎给出的返回结果已经明显过多，并且使得 用户需要通过人工的鉴别才有可能找到自己需要的信息，这个过程大大增加了用 户时间上的消耗。基于以上事实，各大公司和研究机构都在紧锣密鼓的研发新式 的搜索引擎。 1 3 本文内容和结构 本文将提出一种基于内容相关性挖掘的反馈式搜索引擎，后面的章节将会给 出其概念，工作方式，工作原理，并且给出其内部结构和实现。同时也会介绍一 种开源搜索引擎n u t c h ，以及开源工具l u c e n e 。 文章的第二章将介绍搜索引擎的相关核心技术，第三章将给出这个f t p 搜索 引擎复用了的n u t c h 部分模块详细介绍和实现，包括l u c e i l e 的介绍。第四章将 给出本文提出的基于内容相关性挖掘的反馈式搜索引擎各个模块的设计与实现 以及内容相关性挖掘算法，第五章是总结与展望。 ， 第二章搜索引擎核心技术 第二章搜索引擎核心技术 搜索引擎( s e a r c he n g i n e ) 是一种在互联网上查找信息的工具，它通过网络机 器人等前端程序收集互联网信息，对其进行索引，形成共查询的数据库。用户在 搜索引擎的客户端程序中键入要查找的关键词，搜索引擎就会在所形成的数据库 中找出与该词匹配的u r l ，并将结果显示给用户，用户可根据输出的结果选择 并访问相关站点【2 j 。 搜索引擎是一个涉及到包括数据收集，数据存储，数据挖掘，分布式系统等 一系列技术的结合体。需要实现一个搜索引擎首先需要研究以及充分了解所有的 技术难点。 2 1 搜索引擎的基本技术 2 1 1 数据收集相关技术 首先，搜索引擎需要原始数据来进行搜索，数据从何而来? 因特网上的网页 不会自动跑到搜索引擎的系统中去，所以需要搜索引擎去主动收集数据。收集的 手段可以有不同的考虑，最常见的一种是所谓的“爬取”：将w 曲上的网页集合 看成是一个有向图，收集过程从给定起始u r l 集合s ( 或者说“种子”) 开始， 沿着网页中的链接，按照先深、先宽、或者某种别的策略遍历，不停的从s 中移 除u r l ，下载相应的网页，解析出网页中的超链接u i u ，看是否被访问过，将 未访问过的那些u i 也加入集合s 3 o 这个过程又被称为“爬行”( c r a w l ) ，而这 个程序被称为蜘蛛。 爬行器也有多种构造方法，比如有基于支持链接的爬行器，基于相似度的爬 行器等【4 1 。真正的搜索引擎中，为了提高爬行抓取的效率，不会只有一个爬行器 在工作，而通常会有多个爬行器并行工作，这就需要设计合适的体系结构以更好 地使这些爬行器相互协调合作，使得系统负载能够时刻维持在均衡的水平，而且 要求有一定的容错性。有经典的分布式体系结构h a r v e s t ，经典的集中式体系结 构g o o g l e 5 1 等。 第二章搜索引擎核心技术 2 1 2 数据处理相关技术 在爬行器抓取过数据之后，还不能直接将原始的未处理的数据存入数据库 中，而需要对数据进行进一步的数据处理。数据处理的目的是将网页中的数据进 行理解并提取出有用的部分，并且对它进行适当的处理。这个过程包括大概四个 方面：关键词提取，相同内容清除，网页分析和链接分析。 对于一个网页来说，除了它的内容外，还有大量的h t 池标记，以及与内容 无关的广告。关键词提取要求提取出网页的内容并且将内容中的词语提取出来， 并省略像“的”、“是”这样的没有检索意义，多次出现的词语。这里对于中文网 页来说需要用到中文分词技术，有基于词的分割法，基于字的分割法 6 。两种方 法各有优缺点，基于字的分割法实现简单，但是不能有效的起到分词作用，体现 不出中文的特点。基于词的分割法则克服了前者的缺点，但却有自己的不足，比 如实现起来较困难，词典的构建是一个大的工程，另外有时候会出现多种结果( 歧 义) 【7 1 。对于常用的中文搜索引擎来说，做好中文分词是很关键的一步。 在互联网上经常出现转载和镜像的现象，前者是在别的网页中转载某个网页 的内容，后者则是指某个网站为了防止数据丢失而提供了镜像服务器，这样原网 页与镜像网页的内容就会出现完全相同的现象。重复的内容对于搜索引擎来说不 论对硬盘还是内存都是一个很重的负担，严重的占用了处理器的资源，所以消重 技术被多家搜索引擎所采用。因此，发现重叠文档的技术被广泛研究，美国亚利 桑那大学的研究人员采用了计算文档重叠度的方法来发现大型文件系统中的相 似文件 8 1 。斯坦福大学的研究人员开发了s c a m ( s t a n f o r dc o p ya n a l y s i s m e c h a l l i s m ) 用于发觉相似文档【9 j 并在后来被用于g o o g l e 搜索引擎。文献 1o 采用了全文分段签名的算法，他把一个文档分成n 段，对每一段进行指纹计算， 对每一个文档用n 个指纹表示，通过计算n 个指纹的相似程度来判断网页的相 似度。 网页分析是通过网页中的h t 池标记来判断内容的重要性，进行链接的提 取，网页识别等操作。当抓取器抓取网页的时候如果网页暂时无法访问或者被重 定向到其他地址的话，搜索引擎必须做出正确的识别并进行适当的操作，对于无 法访问的网页进行有限次的重试，对于被重定向的网页则通过新的网址进行抓 取。 链接分析是搜索引擎中一个很重要的技术，一个好的算法可以成为一个搜索 引擎的标志，可以让它从众多同等的产品中脱颖而出。这里最著名的要数g o o g l e 的p a g e r a l l k 算法，该算法认为网页间的超链接能体现网页的重要性j 。与 p a g e r a n k 类似的k l e i i l b e 唱的h i t s 算法，此外还有基于连接的排序算法 4 第二章搜索引擎核心技术 ( c o 肌e c t i v i t ) ，- b a s e dr a l 】k i n g ) ，它又包括查询无关( q u e r y i n d 印e n d e n t ) 和查询 相关( q u e r y d 印e n d e l l t ) 两种【1 2 】。除了对网页排序，链接分析算法还可以用来 决定哪些网页可以加入某个网页集合，比如爬行某一组网页的时候，往往优先爬 行权值高的网页。c h oe ta 1 就提出按照p a g e r a n k 的顺序访问网页的爬行算法【4 】， 文献 1 3 提出了一种针对某一主题的搜索引擎的集中式爬行方法。链接分析算法 还被用于一种叫做按示例搜寻的搜索策略一给出一个网页而查找它的相关网页。 k l e i n b e 玛提出使用h i t s 算法解决此问题 1 4 】，而d e a n 和h e n z i n g e r 则证明了h i t s 算法和一个简单的基于互引用的算法都能很好的工作，基于互引用的算法思想是 频繁的互引用是相关性强的标志【1 5 】。r a f i e i 和m e n d e l z o n 扩展了h i t s 和p a g e r a n k 算法用来计算网页的受欢迎程度【1 6 1 ，s a m k k a i 则用来在个性化互联网应用中做预 测工作【1 7 】。 2 1 3 数据查询相关工作 数据的查询工作首先要求做好倒排索引的生成工作，查询工作要做的就是通 过关键字查询倒排索引、或者其所出现过的文章编号。查询过程还涉及到查询和 匹配技术，结果排序技术，以及文档摘要的动态生成技术。 倒排索引是一个索引数据结构体，它存储从内容( 比如词语或者数字) 到文 档在数据库文件中位置的映射，这使得全文检索十分方便。另外还有一个用于全 文检索的文件结构叫做签名文件。文献 1 8 比较了倒排索引和签名文件的优劣， 得出的结论是倒排索引在所有指数上都压过签名文件，因此倒排索引成为了搜索 引擎索引结构的唯一选择。文献 1 9 详细阐述了倒排索引的各种方面的细节。 在准备好了倒排索引结构后，接下来的工作将是查询该结构，并且做出适当 的匹配，返回必要的结果。查询过程一般分为两个步骤，第一步是分词，即将一 个查询短语分割成一个个词语，如果是中文短语的话需要用与关键词提取中提到 的同一个中文分词程序对短语进行分词。第二步是匹配，将第一步的结果集( 词 语集) 与倒排索引的关键词进行匹配，找出含有这些结果集的文档编号。在完成 第二步后将会得到一个符合查询条件的文档集合。 对结果进行排序是查询工作中的重要一步，它体现了搜索引擎返回结果的质 量以及搜索引擎的商业策略。结果排序这一阶段的算法依照搜索引擎的不同而不 同，著名的中文搜索弓f 擎百度采用的是竞价排名的排序策略 2 ，这个与它们的商 业目的有着密切的关系。g o 0 9 1 e 则是使用计算搜索短语与文档相似度与 p a g e r a n k 算法决定的网页重要性相结合的方法计算出一个综合的指标，通过这 个指标对返回结果进行排序【2 1 1 。 对于摘要方法，一般来说，有两种摘要方法，一种称为静态摘要，一种称为 第二章搜索引擎核心技术 动态摘要。前者一般固定截取文档的一段句子生成文档的摘要，但是往往生成的 摘要与查询短语无关，后者则需要根据查询词在文档中的位置，提取出周围的文 字作为摘要显示出来，并且往往高亮查询词。这种动态摘要技术被大多数搜索引 擎采用。该技术由搜索引擎l y c o s 于1 9 9 4 年引入【2 2 1 。文献 2 3 给出了一个全文 索引系统中的动态摘要生成算法。 2 2 搜索引擎优化技术 2 2 1 与性能相关的技术 这类技术中第一个想到的就应该是分布式软件系统的设计，分布式软件系统 是指支持分布式处理的软件系统，是在由通信网络互联的多处理机体系结构上执 行任务的系统。它包括分布式操作系统、分布式程序设计语言及其编译( 解释) 系 统、分布式文件系统和分布式数据库系统等。m a p r e d u c e 是一个用于辅助实现并 行计算的分布式软件框架，m a p r e d u c e 的用户是广大程序员，他们只需要实现两 个函数( m a p 函数和r e d u c e 函数) 就可以在不用考虑分布式实现细节的情况下 使用分布式系统 2 4 】。m a p r e d u c e 框架有多个语言版本的实现，包括c + + ，j a v a 等，并且该架构被著名搜索引擎g o o g l e 所采用。 在大型集群式设备中，需要考虑的不仅仅包括分布式系统的设计，还应当考 虑数据的分配方案，以及并行文件系统中的负载平衡问题。文献 2 5 对并行系统 下的数据分布和负载平衡问题有深入的实验和探索，并且提出了一个智能的可自 维护的文件系统。文献 2 6 提出了一种竞争性的算法来用来进行分布式数据系统 的管理。 对于一个从互联网上搜集数据的搜索引擎来说，控制在某一时刻对同一w - e b 站点的连接数是十分有必要的。因为提供w 曲服务的服务器，其能够处理的t c p 链接数量是有上限的，当出于等待队列中的t c p 链接占满了整个队列时，任何 t c p 连接请求都会被忽略。所以同一时刻连接同一服务器过多的话会影响服务器 的正常运行，实际上会起到拒绝服务的攻击效果。因此，对于并行运行的爬行器 来说，需要使用合适的方案来限制对某一站点过多的频繁连接。最简单也十分有 效的方法是硬性规定连接同一个站点的连接数上限。 2 2 2 与质量相关的技术 如何判断搜索引擎的好坏，为此，信息检索领域的研究人员推动并且建立了 一套评估搜索引擎系统质量的方法。根据评估对象的不同，可以分为6 个级别： 6 第二章搜索引擎桉。技术 工程级，输入级，处理级，输出级，应用级和社会级田 。其中，前三个级别的评 估咀系统为中心，后三个级别的评估以应用为中心。目前检索领域最重要的评估 往往由1 1 咂c ( t e x tr e 研v a ic o n k r 目l c e ) 组织，t r e c 是一个关注各种信息检索 研究领域的研讨会组织，它由n i s t ( n a t i 彻a l i l l s n 们t eo f s t a n d a m sa r i d t e c h n o l o g y ) 和美国国防部共同主办。在t r e c 的推动下，评估方法的研究取得 了很大的发展。 1 r e c 主要在处理级进行检索效果评估，把相关性作为评估准则。相关性是 一种复杂的感知和社会现象，它不是简单二元的是否判别，它和环境、上下文有 密切联系。相关性判别通过专门的评估人员人工判断，在大规模数据集上进行检 索系统评估时，这种人工的工作成为晟大的开销，并且使得对整个数据集进行完 全的相关性判别成为不可能。为了让评估实验可重复，t r e c 建立了大规模的评 估数据集，包括数据集，查询集和相关结果集。其中相关结果集通过一种称为 p o o l m g 的方法构造，对每个评估用的查询，从所有参加评估的结果序列中挑选 出前一部分，人工判断其相关性，其它文档作不相关处理p 。 2 2 3 前台优化技术 搜索引擎的前台主要指的是用户接口的阿页，对于搜索引擎这种包含如此多 复杂技术的应用来说，前台也许是最没有技术含量并且最不需要研究的领域。但 事实并非如此，前台作为用户直接看到的东西，对整个搜索引擎起着非常重要的 作用。前台做的好，给用户的直观感觉就要比前台一般的系统更能吸引用户的眼 球。目前前台大致有两种风格，一种是将搜索栏至于其他复杂繁多的内容之间， 其代表就是y a b o oo 搜索引擎( 图2 一1 ) ，还有一种则只显示一个简洁的搜索界面， 其他内容都小心的放在网页的四周，其代表是g o o g l e 搜索引擎( 图2 - 2 ) 。 。| 勰j 一 螺：= 、盈h o o r 一 茹句n v 。 o ”r r 日“一m 一“ = 。j 掣” ， ! ；备酋 一目国 誓 _ i “ j | 二 恐纛 置三墓= e日s1日ft自b60 第二章搜索引擎核心技术 y h b 塑2 9 箜! ! i 匹i ! 璺竖叁j ! e 2 塑日! ! ! 壁! ! ! 堡 图2 1y a h o o ! 首页 g q 喀董e “ e 坐鲤生业立! i 业 匝蔓圄匿薹耍幽i 盏羞型； 苎监里型卫旦婴! i 卫! 璺堡型筮型! ! 堕塑- 些2 也垒2 塑疃曼2 塑鱼壁! l 坦堕塑 90 0 口1 图2 2g o o g l e 界面 两种风格的界面各具特色，第一种有效的利用了网页的空间，使得网站在作 为门户网站的同时提供搜索引擎服务，第二种对于第一种来说则是一个创意上的 大革命，当年g o o g l e 的高速成长与它给人留下深刻印象的简洁界面功不可没。 如今像g 0 0 9 l e 一样的简洁风格在搜索引擎领域也是大行其道，包括百度，“v e s e a r c h ( 微软) 。 2 3 反馈式功能相关的研究 f t p 搜索引擎的反馈式功能的实现主要在于基于内容相关性挖掘的反馈式搜 索引擎框架( f s e ) ，该框架的核心是一个网页相关性矩阵，该矩阵实际上是由 用户点击过的网页组成的方阵，方阵的内容是通过f s e 的核心算法得来的网页 相关性。反馈式搜索引擎充分利用了用户的c l i c l ( t l 啪u 曲数据，正是通过这些数 据得到了这个网页相关性矩阵。目前也存在一些技术利用c l i c l ( t h r o u 曲数据来改 进搜索引擎系统的质量，这些技术大致可以分为两类，第一类是通过c l i c k t h r o u g h 数据来优化搜索引擎中的r a l l l ( i n g 函数，比如 2 8 】提出的以用户的c l i c l ( 廿啪u g h 数 据和r a n k i n gs m 学习有效的r a l l k i n g 函数；第二类是通过分析c l i c l ( t h r o u g h 数据 来抽取用户的偏好信息， 2 9 提出利用朴素贝叶斯方法学习基于特定用户偏好的 r a 出n g 函数。但是，无论所希望学习的r a i 此n g 函数是否基于特定用户偏好， r a u 幽n g 都系统是q u e d ，d 印e n d e n t 的，有必要考虑二元砌【1 1 ( i n g 函数r ( q i ，d i ) ，这里 q i 是第i 个查询，d i 是第j 个文本。由于可能查询潜在的无限性，使得r 难以在实 际搜索引擎的大规模开放环境中被有效学习。 通常搜索引擎的用户不会随机的点击搜索结果列表上的链接，而是作出某种 有目的性的判断和选择。文献 3 0 】 3 1 都证实点击数据是一种包含丰富信息的隐 性反馈，文献 3 0 也指出用户更加趋向于点击那些与他们的需求相吻合的链接。 第二章搜索引擎核心技术 所以，如果搜索引擎可以提供动态的查询结果，使查询结果既与查询词相关又与 特定用户点击的目标网页( 目标网页体现了该用户的需求) 相关，则可提高搜索 结果对用户的可用性。因此，使用用户的点击行为作为反馈式搜索引擎的数据基 础是有理论根据的。文献【3 2 给出了反馈式搜索引擎的网页相关性矩阵的算法， 与 3 3 和 2 8 】中的方法不同，这个算法避免了学习q u e r y s e n s i t i v e 的础【1 h n g 函数 的复杂性，具有与通用搜索引擎相适应的时空效率，它用到的算法包括直接随机 映像算法 3 4 】和基于最大可靠路模型的概率可达性算法【3 5 】【3 6 】等。 文献 3 7 提出了一种基于个性化搜索【3 8 】和隐式反馈 3 9 的反馈式搜索引擎，另 外还有一种基于用户显式表明文档相关性的显式反馈式搜索引擎，它们的区别在 于前者是系统估算出用户的兴趣所在，后者是用户显式表明自己的兴趣所在j 。 于这两种搜索引擎的不同之处在于本文实现的f t p 搜索引擎是基于网页相关性 矩阵的反馈式搜索引擎，而前两者是基于类似于查询该扩展的反馈式搜索引擎， 可以说与两者的最大的相似之处在于名字的相似。 第三章n u t c h 系统模块的复用和实现 第三章n u t c h 系统模块的复用和实现 这个反馈式f t p 搜索引擎是一个基于n u t c h 系统的实现，在搜索引擎的设计 和实现过程中复用了很多有用的n u t c h 模块，其中包括很重要的文件系统模块 等。本章首先介绍a p a c h e 项目组下的n u t c h 和l u c e i l e 项目，然后介绍f t p 搜 索引擎复用到的文件系统模块和插件管理模块的设计和实现，最后会介绍该搜索 引擎系统对l u c e n e 的使用。 3 1 开源搜索引擎n u t c h 介绍 3 1 1l u c e n e 项目组介绍 在介绍开源搜索引擎n u t c h 之前，有必要先介绍开源项目组a p a c h e 软件基 金会及其旗下项目组l u c e n e 。 a p a c h e 软件基金会( h 即：价哪w 印a c h e o ) 是一个支持a p a c h e 软件项目的 非营利性组织，他们发布的软件产品都因为遵守a p a c h e “c e n s e 而成为开源软件 或者免费软件。a p a c h e 旗下的每个项目组都由热衷于对项目做出贡献的技术专 家管理。 l u c e l l e ( h 印：1 u c e n e 。a p a c h e 。o 玛) 作为a p a c h e 旗下的一个项目组，主要提供 与搜索引擎相关的开源软件。l u c e n e 项目组的旗舰产品l u c e n e 在文档检索和搜 索方面是同类开源产品的领头羊。以下是在完成这篇论文时l u c e n e 项目组下的 子项目列表及其介绍： l u c e i l ej a v a ，l u c e i l e 项目组的旗舰产品，提供基于j a v a 的检索和搜索技 术。 n u t c h ，一个基于l u c e n ej a v a 的提供w e b 搜索的搜索引擎。 l u c y ，l u c e n ej a v a 粗略的c 语言版本，包含p e r l 和r u b y 的调用接口 s o l r ，一个使用l u c e n ej a v a 的高性能搜索服务器，包括诳。h t t p 以 及j s o n p y t h o l l r u b y 的a p i ，提供高亮关键字，支持高级检索语言，页 面缓存，镜像，以及w 曲管理接口等服务。 l u c e n e n e t ，一个构造中的l u c e n ej a v a 对c 群及n e t 平台的精确转移版本。 t i k a ，发现并抽取各种结构化文档的元数据的的工具包，它使用已有的 解析库，目前该项目正在构造中。 第三章n m c h 系统模块的复用和实现 m a h o u t ，新的l u c e i l e 子项目，目标在于创建一系列机器学习套件。 h a d o o p ，严格来说已经不算是l u c e n e 的子项目，它已经上升为与l u c e n e 项目组同级别的h a d o o p 项目组。它之前属于l u c e i l e 项目组，是 m a p r e d u c e 框架的j a v a 版本的实现。 l u c e i l e 最重要的两个项目无疑是l u c e n e 和n u t c h ，正是这两个项目使得普通 站点也能够自己建立自己的搜索引擎。并且推动了搜索引擎的研究和发展。 3 1 2l u c e n e 及n u t c h 介绍 l u c e n e 严格说来并不是完整的搜索引擎，而只是提供对已有文档的检索及搜 索功能的工具，n u t c h 则是真正意义上完整的搜索引擎。 二者的区别在于：n u t c h 是建立与l u c e n e 之上的搜索引擎，使用了l u c e i l e 提供的文档检索及搜索的a p i 。n u t c h 主要部分在于提供了w e b 爬行功能，这个 部分是专门为了这个项目而从零开始构建的。 n u t c h 有着高度模块化的架构允许开发者为以下功能创建插件：媒体类型解 析器，数据检索，查询和集群等功能。它完全用j a v a 语言构建，而其数据则是 以语言无关的形式保存。为了保证其处理大数据量的高效率，该项目同时实现了 m a p r e d u c e 框架和一个分布式文件系统，如今这一部分已经成为了一个独立的 h a d o o p 项目组。可以说，n u t c h 项目对搜索引擎的各方面技术都有着很大的贡献。 它使得普通的程序员有机会接触搜索引擎的源代码，其强大的模块化架构使得修 改及阅读源代码工作变得更加简单，这都有助于推进搜索引擎研究的进展。目前 n u t c h 的最高版本0 9 已经完全移植到h a d o o p 平台之上，其运行速度因此有了很 大的提高。 l u c e l l e 对于实验性的n u t c h 来说已经是一个很成熟的产品，它被应用到大大 小小的网站和工程之中，其中著名的开源开发工具e c l i p s e 的内部搜索功能就是 使用了l u c e l l e 的a p i 。目前l u c e n e 的最高版本已经到了2 3 术版，作为成熟的开 源工具，l u c e n e 成为了开源社区文档检索工具的第一选择。 3 2 文件系统模块的设计和实现 文件系统模块是搜索引擎系统中最基础也是最重要的模块，它设计了整个系 统的文件结构，为这个系统提供了高效的文件读写和修改接口，从而保证了搜索 引擎系统的高速度和高效率。几乎在搜索引擎的所有模块中，都需要用到文件系 统，因此，了解文件系统模块的设计和实现是了解其他模块的基础。 第三章n u t c h 系统模块的复用和实现 3 2 1 文件系统模块的设计概览 文件系统模块分成几个层次：最底层称为i o 层，位于其上的有d b 层和f s 层。 其中i o 层为上层的模块定义了基本的数据结构和文件结构，f s 层则完成了了两 种文件系统的实现一分布式文件系统和本地文件系统，d b 层则是搜索引擎文件 系统的最高级的实现，它定义了搜索引擎需要的数据结构，以及对数据库的读写 接口和接口的两种版本的实现( 分布式和本地) 。从子模块的划分角度上看，i o 层包括两个模块：数据结构模块和文件结构模块，f s 层有一个输入输出模块，d b 层包括高级数据结构模块和数据库模块。图3 1 是文件系统模块的设计图。 ：丌1 ： jo 事 、 输入输出模块p 血 | 。 图3 1 文件系统设计图 对于任何系统来说，设计一个好的、合适的文件系统是整个工程成功的基础。 作为一个搜索引擎系统来说，情况就更是如此，对于一个要求高效率读取大量数 据的搜索引擎系统，使用i a v a 自带的文件系统远远不能满足其要求，使用数据 库管理系统的话则不能很好的满足全文检索的需要。因此，搜索引擎往往都需要 设计自己的文件系统。 本f t p 搜索引擎采用的是开源项目n u t c h ( 0 7 2 ) 提供的文件系统，由于都 是用j a v a 实现的，基于l u c e n e 的搜索引擎，n u t c h 的文件系统可以很好的满足 f t p 搜索引擎的需要。如图3 1 所示，这个文件系统分作三个层次：i o 层，f s 层，d b 层。这三层由三个包实现：o r g 印a c h e n u t c h i o 包，o r g a p a c h e n u t c h f s 包 和o r g 印a c h e n u t c h d b 包。本节将分别详细介绍这三个包的内容。 眦止 眦o 一 ； 第三章n u t c h 系统模块的复用和实现 3 2 21 0 层的实现 这一层分别定义了搜索引擎的数据结构和文件结构，另外对于所有数据结构 都实现了可写可比较的接口，使得所有数据结构均可以直接写入电脑的硬盘中， 也使得大多数数据结构对象可以与同类型的数据结构对象作比较。下面将介绍 i o 层的四个部分：数据结构，文件结构，可写可比较接口，其他工具和输入输 出类。 在这一层实现了十一种数据结构，包括：胁a y w n t a b l e ( 可写的数组) ， b o o l e a n w n t a b l e ( 可写可比较的布尔数值) ，b y t e s w r i t a b l e ( 可写可比较的b y t e 数值) ，f l o a t w r i t a b l e ( 可写可比较的n o a t 数值) ，i i l t w d t a b l e ( 可写可比较的n 数值) ，l o n g w 五t a b l e ( 可写可比较的1 0 n g 数值) ，m d 5 h a s h ( 可写可比较的m d 5 值) ，n u l l t a b l e ( 可写的n u l l 值) ，u t f 8 ( 可写可比较的字符串) ， v e r s i o n e d w r i t a b l e ( 可写的版本值) ，t w o d a l l r a v w r i t a b l e ( 可写的二维数组) 。这 些数据结构均实现了可写接口( w r i t a b l e ) ，并且尽可能的实现了可比较接口 ( c o m p a r a b l e ) 。关于这两个接口将在后面介绍。这里要介绍的是两个很常用到 的并且含有特别方法的类：m d 5 h a s h 和u t f 8 类。 m d 5 h a s h 类从某种意义上讲是一个长度为1 6 的b y t e 型数组的包装类，它采 用的摘要算法是j a v a 系统提供的5 摘要算法，内部维护一个 j a v a s e c 谢吼m e s s a g e d i g e s t 类型的静态常量对象d i g e s t e r 作为摘要器。它提供 针对包括b y t e 数组，字符串和u t f 8 对象这三种数据结构做摘要的静态摘要方法 m d 5 h a s hd i g e s t ( ) 。它的h a l f d i g e s t ( ) 方法返回一个由它内部的b y t e 数组的前8 位 组成的1 0 n g 型数据。 u t f 8 类代表一个字符串的u t f 8 表示，它的内部维护一个任意长度的b y t e 数组。它对外提供了几个很有用的方法：b ”e 口g e t b ”e s ( s t 血gs 缸证g ) ，这个方法 返回一个字符串的u t f 8 格式编码，s t r i n gr e a d s t 血g ( d a t a i n p u ti n ) ，这个方法从 一个u t f 8 格式编码的输入流中读取字符串：s l ( i p ( d a t a i n p u ti n ) ，这个方法使u t f 8 格式的输入流i 1 1 跳过一段u t f 8 字符串；w r i t e s t r i n g ( d a t a o u t p u to u t ，s t 血gs ) ，这 个方法向输出流o u t 写出字符串s 的u t f 8 版本的字节数和其u t f 8 版本的内容。 这一层实现的文件结构有四种：a 1 1 r a y f i l e ，m 印f i l e ，s e q u e n c e f i l e ，s e t f i l e 。 在这四种文件结构中，最基础的文件结构是s e q u e n c e f i l e ，其次是m 印f i l e ，而 a 1 1 r a y f i l e 和s e t f i l e 可以看作是m 印f i l e 的特例。 s e q u e n c e f i l e 代表一个键值对文件，该类的内部有三个子类： s e q u e l l c e f i l e 、r i t e r ，s e q u e n c e f i l e r e a d e r ，s e q u e n c e f i l e s o r t e r 。分别提供对这种 文件的写，读和排序操作。该文件的格式如下： 第三章n u t c h 系统模块的复用和实现 三垫业三：三曼卫业荃s y l l c n 个咖 其中版本是长度为4 的b y t e 口数组，表示该文件的版本号；键类名和值类名 分别是两个类的名字的u t f 8 版本；s y n c 是长度为4 + 1 6 的b ”e 数组，其中4 部分是一个值为1 的i n t 类型，1 6 部分是一个随机的m d 5 h a s h 值；n 的值是 s y n ci n t e r v a i ，的值( 为常数1 0 ) ；一个e n n y 是指一个键值对，它的格式是： 。每隔s y n ci n t e r _ 也个键值对 就放置一个s y n c 。 m a p f i l e 实际上代表的是包括两个s e q u e n c e f i l e 文件的文件夹，两个子文件 的名字分别是i n d e x 和d a t a ，其中d a t a 是包含全部( 键值) 的s e q u e n c e f i l e ，i n d e x 是只包含部分( 键位置值) 的s e q u e n c e f i l e 。其中部分的间隔由m 印f i l e 、斩r t e r i n d e x i n t e r v a l 的值决定。m a p f i l e 有两个子类：w h t e r 和r e a d e r ，这两个子类提供 读写方法。与s e q u e n c e f i l e 不同，m 印f i l e 必须始终是有序的，因此m 印f i l e w h t e r 的a p p e n d ( ) 方法必须保证添加的键值对的键大于d a t a 文件中最后一个键，否则会 抛出异常。a