个性化搜索引擎及相关技术研究 基于Lucene索引机制的研究与实现---毕业论文

本 科 毕 业 论 文 个性化搜索引擎及相关技术研究:基于Lucene索引机制的研究与实现Personalized search engine and related technology research: The research and implementation of Lucene indexing mechanism姓 名： 学 号：学院：软件学院系：软件工程专 业：软件工程年 级：指导教师： 年 月摘要随着互联网的快速发展和网络信息的爆炸性膨胀，基于Internet的各种信息搜索服务应运而生并迅速发展。但现有搜索引擎基本上采用“一个搜索适用所有用户”的模型，体现不出特定用户的真正需求所在。因此，搜索引擎的个性化成为当今Internet信息检索的一个重要课题。本研究小组基于此，研究相关搜索及个性化技术，并开发实现了个性化搜索引擎系统。本文首先简要介绍了搜索引擎技术及索引技术的相关理论，并通过对全文检索中的正排表、倒排表，以及倒排表的字表法、词表法的研究与实践，深入了解了全文检索索引的构建使用。并通过对Apache全文检索技术Lucene源码的剖析和实践，理解Lucene的系统组织结构、基本数据类型、索引内存结构及索引库文件结构，深刻理解了其索引过程以及索引方式，掌握了索引维护和索引优化的方法。在此基础上，利用Lucene API函数，设计了个性化搜索引擎的索引器。使其可以实现批量索引、增量索引、索引删除、索引更新等方法，并成功为个性化搜索引擎系统生成了所需索引库，供查询检索模块使用。在设计开发过程中，严格按照软件工程代码重用的要求重用了Lucene的源码，并在此基础上根据系统实际情况进行了改进和扩充。基于Lucene的索引器可以对不同格式文档进行预处理和过滤，并可结合中文分词器迅速为文档建立全文索引库，具有良好扩展性，不仅适用于搜索引擎系统，还适用于目前运用广泛的全文检索系统。关键词：索引器；个性化搜索引擎；LuceneABSTRACTWith the rapid development of Internet and the information explosive expansion, many kinds of search services emerged and developed fast. However, most of the existing search engines use the “a search for all users” model, which cannot reflects the real needs of the specific user. Therefore, the personalized search engine has become an important topic in the Internet information field. For this reason, the research team studies the relevant technology in search engines and personalized search. The team also developed a real personalized search engine system.This article briefly introduced the theories of search engine and index technology. Through the study and practice of the ranked list, inverted list, single word table and vocabulary table in full-text search, deeply understand the using of indexing. And through the research in the source of Apache Lucene, understand the structure of Lucene system, the basic data types, the memory structure of index and the indexing file. Also understand the indexing process and the method of maintaining and optimization of indexing database. Basic on this, designed the indexer for personalized search engine system using Lucene API. The indexer can implement indexing, incremental indexing, index deletion, index update and so on. It built the index file successfully for the system and the query module. In the process of design and development, reuse the Lucene source code strictly according the code reuse requirements in software engineering. Improved and expanded it basic on the actual situation.The indexer based on Lucene can handle different format files and filter them. Combine with the Chinese tokenizer, the indexer can build the full-text index rapidly for the documents. It has the good scalability, not only applicable to the search engine system, also applies to the full-text retrieval system which is used widely. Key words: Indexer; Personalized search engine; Lucene目录第一章引言11.1研究背景11.2本文主要工作1第二章搜索引擎及索引模块概述32.1搜索引擎的概念32.2搜索引擎的关键技术52.2.1搜索引擎的搜索技术52.2.2搜索引擎的索引技术62.2.3搜索引擎的查询技术72.2.4搜索引擎的接口技术72.3索引原理82.3.1索引概述82.3.2索引基本结构82.4全文检索中的索引组织102.4.1全文检索概述102.4.2索引模块在搜索中的重要性112.4.3索引的组织方式112.4.4倒排表的组织字表和词表13第三章全文检索系统Lucene的技术分析153.1Lucene系统概述153.2Lucene结构分析163.2.1系统结构组织163.2.2数据流183.3Lucene索引器193.3.1Lucene索引器概述193.3.2Lucene索引结构203.3.3Lucene索引文件结构22第四章系统设计与实现254.1系统概述254.1.1系统结构254.1.2系统平台及开发环境264.2索引模块设计与实现264.2.1索引模块的组成概述264.2.2索引模块的数据流图284.2.3索引构建部分的数据流图294.3索引过程的分析与实践304.3.1原始语料的预处理过程304.3.2索引建立过程334.3.3索引参数优化394.3.4使用RAMDirectory提高效率404.3.5索引优化414.4索引库的实现424.4.1批量索引424.4.2增量索引44第五章运行结果与性能分析455.1索引建立455.2查询测试47第六章结论50致 谢51参考文献52ContentsChapter1 Introduction11.1Background11.2Content1Chapter2 Search engine and Indexing module32.1Concept of Search Engine32.2The key technology of Search Engine52.2.1Searching Technology52.2.2Indexing Technology62.2.3Querying Technology72.2.4Interface Technology72.3Indexing principle82.3.1Summary of Indexing82.3.2Basic framework of Indexing82.4Indexing structure in Full-text Retrieval102.4.1Summary of Full-text Retrieval102.4.2The importance of Indexing module112.4.3The organisation of Indexing112.4.4The organisation of inverse table13Chapter3 The analysis of Lucene Technology153.1Summary of Lucene153.2Structure of Lucene163.2.1Structure of System163.2.2Data stream183.3Indexer in Lucene193.3.1Summary193.3.2Indexing structure203.3.3Indexing file structure22Chapter4 Design and Implementation of System254.1Summary254.1.1Framework254.1.2Development Platform264.2Design and implementation of Indeing module264.2.1Summary of Indexing module264.2.2Data stream of Indexing module284.2.3Data stream of building index294.3Analysis and Practice of indexing process304.3.1Pretreatment for original document304.3.2Process of Indexing334.3.3Parameter Optimazation394.3.4Using of RAMDirectory404.3.5Indexing Optimazation414.4Implement of Indexing424.4.1Batch Indexing424.4.2Increment Indexing44Chapter5 Test Result and Analyses455.1Building Index455.2Search Test47Chapter6 Conclusions50Acknowledgements51References52个性化搜索引擎及相关技术研究基于Lucene索引机制的研究与实现第一章 引言1.1 研究背景Internet的出现改变了全球通讯和信息资源的共享方式，它将各种各样的资源整合联系在一起，构成了一个巨大的网络。而互联网的快速发展带来的是网上信息爆炸性的增长。2008年，Google宣称其目前索引的网页数量已经达到一万亿，这些信息都具有无固定结构、分布无规律性和动态性极强的特点。虽然Internet上的信息量每天成指数级增长，但对于用户只有少数是相关或有用的。如何将这些信息有效的组织利用，让人们可以比较容易的找到自己所需的资源，这已经成为了现代互联网研究的关键课题。搜索引擎正是在这种情况下应运而生，它以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供检索服务，从而起到信息导航的目的。但是，随着信息多元化的增长，千篇一律的给所有用户提供同样的搜索结果已经不能满足特定用户更深入查询的需求。通常，不同领域背景、不同知识结构的用户对文档相关性的判断及检索结果的要求是不同的。因此，未来的搜索引擎，必将体现这种“个性化”的信息检索，减少垃圾信息，提高查准率，并能够根据用户背景、兴趣爱好、行为、检索目的等信息，检索出适量的、高质量的查询结果。针对上述问题，本项目组主要研究搜索引擎的相关技术，及如何充分挖掘用户浏览网页过程中的各种信息，来构造用户兴趣模型，对检索结果进行过滤、排序，选择更有针对性的信息，提高用户对检索的满意度。并尝试搭建个性化搜索引擎平台，将理论研究转化为实际产品。1.2 本文主要工作“个性化搜索引擎”项目组的课题内容是研究并建立一个基于用户行为模式的个性化搜索服务平台，主要包括系统建构的搭建、索引器模块、检索器模块、用户行为分析模块的开发。本文主要是研究索引器模块，设计个性化搜索引擎中的全文检索索引器，生成高效率、高性能的索引库。文中通过对现有搜索引擎技术及索引技术、全文检索中正排表、倒排表，以及倒排表的字表法、词表法的研究与实践，深入了解了全文检索搜索引擎的构建和使用。并通过对Apache全文检索系统Lucene源码的剖析，理解Lucene的系统组织结构、基本数据类型、索引内存结构以及索引库的文件结构。深刻掌握了Lucene的索引过程及索引方式，并了解了其对索引优化的方法。在此基础上，利用Lucene API函数，设计了索引器批量索引、增量索引、索引删除、索引更新等功能模块，成功生成了可供系统检索模块使用的高效索引库，实现了个性化搜索引擎中的索引器模块。第二章 搜索引擎及索引模块概述22.1 搜索引擎的概念搜索引擎,指的是一种在Web上应用的软件系统，它以一定的策略在Web上搜集和发现信息，在对信息进行处理和组织后，为用户提供Web信息查询服务。1从使用者的角度看，这种软件系统提供一个网页界面，让他通过浏览器提交一个词语或者短语，然后很快返回一个可能和用户输入内容相关的信息列表（通常会是很长一个列表，如包含1万个条目）。通过浏览列表，用户对相应的网页是否真正包含他所需的信息进行判断。比较肯定的话则可点击对应URL，从而得到该网页的全文。但搜索引擎提供信息查询服务的时候，它面对的只是查询词。而有不同背景的人可能提交相同的查询词，关心的却是和这个查询词不同方面的信息，但搜索引擎通常是不知道用户背景的，因此搜索引擎既要争取不漏掉任何相关的信息，还要争取将那些“最可能被关心”的信息排在列表的前面。1搜索引擎还有两个重要方面与传统信息检索系统区别。第一，当用户提交查询的时候，搜索引擎并不是即刻在Web上“搜索”一通，发现那些相关的网页，形成列表呈现给用户；而是事先已“搜集”了一批网页，以某种方式存放在系统中，此时的搜索只是在系统内部进行而已。第二，当用户感到返回结果列表中的某一项很可能是他需要的，从而点击URL，获得网页全文的时候，他此刻访问的则是网页的原始出处，于是，从理论上讲搜索引擎并不保证用户在返回结果列表上看到的标题和摘要内容与他点击URL所看到的内容一致，甚至不保证那个网页还存在。为了弥补这个差别，现代搜索引擎都保存网页搜集过程中得到的网页全文，并在返回结果列表中提供“网页快照”或“历史网页”链接，保证用户能看到和摘要信息一致的内容。 2按照信息搜集方式和服务提供方式的不同，现代搜索引擎系统可以分为五大类：41） 基于目录的搜索引擎基于目录的搜索引擎将收集到的信息分到某一个类中, 典型的基于目录的搜索引擎有Yahoo 和Magellan。目录式搜索引擎提供由网页作者呈送的Internet资源的链接集合, 同时对这些资源做出评价并组织成主题目录。它使用一定的选择标准用于挑选所录用的链接资源, 不同的目录式搜索引擎使用不同的选择标准。它有两种基本类型: 一种是由主题专家日常建立和维护的学术性专业目录以满足科研人员的需要; 另一方面是为普通大众和商业服务的商业目录。因此, 一定要使用确切满足自己真正需求的那种类型的目录式搜索引擎。当检索一个范围较广的题目, 并希望浏览一下与该题目相关的所推荐的网站时, 目录式搜索引擎会是非常有用的。2） 基于机器人的搜索引擎基于机器人的搜索引擎从一组已知的文档出发, 通过这些文档的超文本链接确定新的检索点, 然后用索引机器人周游这些新的检索点, 标引这些检索点上的新文档, 将这些新文档加入到索引数据库。以后搜索引擎可以用这个索引数据库去回答用户的提问。机器人搜索引擎不是靠人工发现和甄别信息, 而是由一个被称作“蜘蛛”的计算机程序在网中爬行, 依据一定的网络协议在因特网中发现、加工、整理信息, 并为用户提供检索服务。3） 基于客户的搜索引擎基于客户的搜索引擎用Web 客户器中的周游软件, 它们从一组已知的文档出发, 检索WWW上的文档并传送这些文档, 然后用文档中的超文本链接找到更多的文档, 直到满足要求。基于客户的搜索引擎不需要第三方检索接口, 因此可改善用户界面, 因为基于客户的搜索是实时的, 它可以搜索到最新的资料, 但搜索速度慢, 网络负载和服务器负载都太大。4） 元搜索引擎元搜索引擎将用户查找要求传递交给其它搜索引擎。它的注意力放在改进用户界面及不同的方法过滤从其它搜索引擎接收到的相关文档，包括消除重复信息。元搜索引擎设计简单，但网络的负载太大。典型的元搜索引擎有METACRAWLER等。5） 分布式搜索引擎。分布式搜索引擎按区域、主题或其它标准创建分布式索引服务器，索引服务器之间相互可以交换中间信息，且查询可以被重新定向。如果一个检索服务器没有满足查询请求的信息，它可以将查询请求发送到具有相应信息的检索服务器。由于分布式搜索引擎将所有数据库划分到几个分布的数据库中，每个数据库变得小一些，但所有搜索引擎覆盖的范围变大，且很少有信息重复，并且具有可扩充的特点。然而分布式搜索引擎需要多个索引数据库协同工作，实现较困难。目前尚未有真正的、实用的分布式搜索引擎。3 2.2 搜索引擎的关键技术2.2.1 搜索引擎的搜索技术搜索技术是指在互联网中漫游、发现和搜集信息的技术，如Robot、Spider等。它常常是一个计算机程序，可以自动的在网络中穿梭，该程序最重要的功能是使用索引策略，也就是查找网站和网页的次序。可以用题目、URL、关键词进行索引，也可以是以上几项的某种组织。如果把整个Internet看作是一个图或一棵树的话，可以发现Robot技术的基本工作原理和人工智能中的搜索树一样，这在计算机中可以方便地使用递归方法实现。这类搜索软件日夜不停地运作。它要尽可能多、快的搜集各种类型的新信息，同时因为互联网上的信息更新很快，所以还要定期更新已经搜集过的旧信息，以避免死链接和无效链接。4目前有三种搜集信息的策略：1）最常见的一种是所谓“爬取”：将Web上的网页集合看成是一个有向图，搜集过程从给定起始URL集合S开始，沿着网页中的链接，按照先深，先广，或某种别的遍历策略，不停的从S中移除URL，下载相应的网页，解析出网页中的超链接URL，看是否已经被访问过，将未访问过的那些URL加入集合S。真正的系统实际上是很多个“蜘蛛”同时在爬。2）另一种可能的方式是在第一次全面网页搜集后，系统维护相应的URL集合S，往后的搜集直接基于这个集合。每搜到一个网页，如果它发生变化并含有新的URL，则将它们对应的网页也抓回来，并将这些新URL也放到集合S中；如果S中某个URL对应的网页不存在了，则将它从S中删除。3）还有一种方法是让网站拥有者主动向搜索引擎提交它们的网址（为了宣传自己，他们通常会有这种积极性），系统在一定时间内定向向那些网站派出“蜘蛛程序”，扫描该网站的所有网页并将有关信息存入数据库中。大型商业搜索引擎一般都提供这种功能。52.2.2 搜索引擎的索引技术索引技术的目的是理解Robot所搜索的信息，从中抽取索引项，用于表示文档已经生成文档库的索引表。索引项有客观索引项和内容索引项两种：客观索引项与文档的语意内容无关，如作者名、URL、更新时间、编码、长度、链接流行度等等；内容索引项是用来反映文档内容的，如关键词及其权重、短语、单字等等。内容索引项可以分为单索引项和短语索引项两种。单索引项对于英文来说是英文单词，比较容易提取，因为单词之间有天然的分隔符（空格）；对于中文等连续书写的语言，必须进行词语的划分。6信息索引就是创建文档信息的特征记录，以使用户能够快速地检索到所需信息。建立索引主要涉及到以下几个问题：1） 信息语词切分和语词词法分析语词是信息表达的最小单位，由于语词切分中存在切分歧义，切分需要利用各种上下文知识。语词词法分析是指识别出各个语词的词干，以便根据词干建立信息索引。2） 进行词性标注及相关的自然语言处理词性标注是指利用机遇规则和统计（马尔科夫链）的数学方法对语词进行标注。基于马尔科夫链随机过程的n元语法统计分析在词性标注中能达到较高的精度。7 可利用多种语法规则识别出重要的短语结构。自然语言处理是指自然语言识别在信息检索中应用，可以提高信息检索的精度和相关性。3） 建立检索项索引使用倒排文件的方式建立检索项索引，一般包括“检索项”，“检索项所在文件位置信息”以及“检索项权重”。 4） 检索结果预处理技术搜索引擎的检索结果通常包含大量的文件，用户不可能一一浏览。搜索引擎一般应按与查询的相关度对检索结果进行排列，搜索引擎确定相关性的方法有概率方法、位置方法、摘要方法、分类或聚类方法等。概率方法根据关键词在文中出现的频率来判断文件的相关性。这种方法对关键词出现的次数进行统计，关键词出现的次数越多，该文件与查询的相关度越高。位置方法根据关键词在文中出现的位置判定文件的相关性。关键词在文中出现的越早，文件的相关程度越高。摘要方法是指搜索引擎自动的为每个文件生成一份摘要，让用户自己判断结果的相关性，以便用户进行选择。分类或聚类方法是指搜索引擎采用分类或聚类技术，自动把查询结果归入到不同的类别中。72.2.3 搜索引擎的查询技术查询技术主要是根据用户的查询，检索系统对用户的关键词进行语言分析，分解成多个词或者词组，在索引库中依据关键词的相关性进行匹配，根据与关键词相关程度来逐渐逼近文档，然后再对相关度的高低进行依次排序，关键词出现的越多，排序就越在前面。在此过程中查询技术可实现某种用户相关性反馈机制。查询技术常用的信息检索模型有集合理论模型、代数模型、概率模型和混合模型4种。2.2.4 搜索引擎的接口技术接口技术的作用是输入用户查询、显示查询结果、提供用户相关性反馈机制。主要的目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中得到有效、及时的信息。接口技术的设计和实现使用人机交互的理论和方法，以充分适应人类的思维习惯。输入接口可以分为简单接口和高级接口2种。简单接口只提供用户输入查询串的文本框；高级接口可以让用户对查询进行限制，如逻辑运算（与、或、非）、相近关系（相邻、NEAR）、域名范围（如：edu、com）、出现位置（如标题、内容）、信息时间、长度等等。61232.3 索引原理2.3.1 索引概述索引是一种数据存储和组织结构。索引主要用于从大量文件中快速找到某个单词或短语。完成信息索引建立、维护和管理功能的软件叫索引器。索引器实际上是一个文本信息处理系统。通常采用倒排文件索引构造索引库，将 Robot采集到的网页信息全部存于其中。经过索引后的数据按照优化格式存放，便于快速加载和检索。索引库的规模直接影响了系统查询的查全率。有些记录了网页的全部内容，对整个HTML文件的所有单词都建立索引，有的只记录网页的地址、标题、关键词、摘要等信息，还有的能处理HTML文件中的META标记或其他不可见的特殊标记。8文本索引的实现方法很多，当前主流的索引技术是倒排索引、后缀数组和签名文件三种。后缀数组技术比较适合于短语查询，签名文档技术目前使用也比较少。倒排索引是一种高效率的索引组织方式，能够很好的支持多种检索模型，提供高性能的检索。倒排索引技术采用字或词作为索引项，非常适合关键词搜索。索引结构的选择和设计过程中需要考虑如何提高性能。对于搜索引擎的海量信息处理环境，还需要考虑如何减少资源的占用。92.3.2 索引基本结构 搜索引擎中用来建立索引的软件系统称为索引器，主要功能是处理和分析非结构化文档。索引器从原始文档中抽取索引项，用于表示文档，并生成文档集合的索引表。搜索引擎索引的文档内容通常包括文档的附属信息、文档的内容信息。不同的索引内容在后续检索中会采用不同的使用方法。9文档在索引之前通常会利用预处理程序和分词程序转化为中间文档格式。这种中间文档格式大多时候以纯文本形式存放，采用空格或者其他方式标示不同的词汇。搜索引擎的索引器处理文本解析器生成的纯文本或统一格式信息，生成索引字典和文本索引库。索引生成器工作的上下文环境如图2-1所示。图2-1：索引器基本流程环境图搜索引擎索引器在工作中需要与相关的文档库以及其他程序发生联系。索引器运行环境涉及的内容主要是文本预处理和检索数据库。其中：l 原始文本库：是网络蜘蛛从网上获取的网页、本地存储的各种格式文本的原始备份。原始文本库保留了文本的完整原始格式，主要为后续解析器提供数据源。在后续文本的更新中，可以用来比较文本内容是否已经更新，减少不必要的下载和更新。l 文本解析器：用来分析网页和文档的内容，统一为无格式文档或者中间格式文档。文档解析器往往是一系列不同文档格式的分析和处理程序。通常还包括中文分词、垃圾信息过滤、为索引器提供统一的可分析数据。l 文本中间格式库：是经过文本解析器处理后得到的纯文本或者统一中间格式的数据库。已经去除了噪音和其他垃圾信息，并且根据需要完成了分词等处理过程。可以为索引器提供输入数据。l 索引器：对分析器处理的结果信息进行处理。依次读取分析索引项，利用预设的索引项字典建立按索引项排列的链表，并动态更改索引字典。最终完成按照索引项组织的索引列表、索引字典和文档索引，用于表示文档以及生成文档库的索引表。l 文本索引库：是以索引形式组织存放的数据文件。在搜索引擎系统中通常采用倒排索引形式。l 索引字典：是词和编码的二元组结构数据库。对每个词汇都有一个唯一的编码与它对应。在建立索引过程中，完成索引项的转换，以减少磁盘内存的使用量。文档解析器和索引器协同工作，统一完成了索引的建立和维护管理工作。文本索引库统一保存对应的文档索引。92.4 全文检索中的索引组织2.4.1 全文检索概述全文检索（Full-text Retrieval）技术是一种面向全文、提供全文的新型检索技术。它是基于文献内容进行数字化文档的查询处理，为全文集合建立一个能精确定位每个字词的索引，克服了传统顺序索引在多文献集合和复杂查询条件下检索效率低的不足。一些系统还能够将检索结果根据引文数量等因素进行相关性排序。10全文检索技术分为两种：一种是根据检索表达式直接在源文档中匹配查找，这种方式适合于对小型文档库的检索；另一种是对文档预先建立索引，查询时对索引进行检索，这种方式适合于对大容量文档库的检索，如Internet网络上的文档检索。全文检索技术包含两方面的核心问题：一个是如何建立和维护索引库；另一个是如何提供快速有效的检索机制。面向网络的全文检索系统所处理的对象是大规模的海量数据，要实现对它们快速有效的全文检索，主要需要考虑以下三方面：1）检索的快速响应；2）索引库的建立与维护；3）索引数据的压缩。7 全文检索系统的结构图如图2-2：图2-2：全文检索系统结构图2.4.2 索引模块在搜索中的重要性索引模块将Spider收集的文档进行处理，以便于有效查找的数据结构进行组织，其中就包括了全文检索索引的建立；查询服务模块从用户处获得查询请求，进行查找后将结果页面返回给用户。其中，查询模块的效率取决于索引的组织情况，也直接决定了整个搜索引擎能否实现快速响应。因此，必须对索引进行高效组织，以实现整个搜索引擎的高效率。112.4.3 索引的组织方式全文检索中索引的常见组织方法有两种：正排表和倒排表。1）正排表正排表是以文档的为关键字，表中各项记录文档中每个字的位置信息，查找扫描表中每个文档中字的信息直到找出所有包含查询关键字的文档。正排表结构如图2-3（a）所示。这种组织方法在建立索引的时候结构比较简单，建立比较方便且便于维护；但是在查询的时候需对所有的文档进行扫描以确保没有遗漏，这样就使得检索时间大大延长，检索效率低下。2）倒排表人们受到图书馆的书目索引的启发提出了全文检索的思想，从书目索引延伸处理的方法就是现在应用广泛的倒排索引模型，如图2-3（b）所示。倒排表以字或词尾关键字进行索引，表中关键字对应的记录项记录出现这个字或词的所有文档，一个表项就是一个字表段，记录该文档的ID和字符在该文档中出现的位置情况。由于每个字或词对应的文档数量在动态变化，所以倒排表的建立和维护都较为复杂，但是在查询的时候由于可以一次得到查询关键字所对应的所有文档，所以效率高于正排表。在全文检索中，检索的快速响应是一个最为关键的性能，而索引建立由于在后台进行，效率相对低一些，不会影响整个搜索引擎的效率。7创建倒排索引一般分为两个步骤，先建立正向索引，然后经过倒排，生成反向索引。分析完语料后，得到以文档编号为主键的正向索引表，如图2-3（a）所示。当反向索引建立完成后，得到图2-3（b）。图2-3：由正向索引建立反向索引这是一个表的重组过程，为了加快速度，全过程一般在内存中完成。在小数据量时，有足够的内存保证创建过程可以一次完成。数据规模增大后，可以采用先分组索引，再归并索引的策略。该策略是，建立索引的模块根据当时运行系统所在的计算机内存大小，将索引分为k组，使得每组运算所需内存都小于系统能够提供的最大使用内存的大小。按照倒排索引的生成算法，生成k组倒排索引。然后将这k组索引归并，即将相同索引词对应的数据合并到一起，就得到了以索引词为主键的最终倒排文件索引，即反向索引。2.4.4 倒排表的组织字表和词表全文检索的核心技术是将文档中出现的所有基本元素的出现信息记录到索引库中。中文全文检索技术在原理上同西文全文检索是一致的，但汉字本身的特点使中文系统的实现比西文系统的实现更为复杂。在英文系统中，基本的处理单元很自然的就是词（Word），因为词是最小的语义单位，英文词之间有空格隔开，词的识别处理非常方便。而中文系统中，字是独立的书写单位，基本元素可以是单个汉字字符，也可以是词。另一方面，由于一个句子中的词之间没有任何分隔标志，加上中文词法灵活，使得中文词的切分处理非常困难。这样，根据倒排文件包含索引词形式的不同，又可将倒排索引构建分为字表法和词表法。1） 字表法字表法是把源文档中每一个字出现的位置信息记录到索引库中，索引库对每个不同的字符都保存一个字表，记录同一个字在文档中的所有出现位置。建库时只要扫描所有的文档，将读到的每个字符的位置信息加到对应的字表中即可。字表法通用性强，实现和维护相对容易，但检索时有可能断章取义，将完全不相关的文档也检索出来。72） 词表法词表法需要使用切分词典，因而其适用于特定领域中内容相对固定的文档的全文检索。其优点是对于大规模应用，索引库可以组织得比较小，检索的处理速度也比较快，而且还可能实现同义词、反义词的概念检索。词表法的总体性能较好，但这种方法在处理中文时实现起来却十分困难。中文文档最基础的结构是句子、短语、词汇、单个的汉字。中文环境的句子通常可以利用标点符号来分隔。其他基础结构单元都无法直接利用空格等分隔符进行划分，这是中文搜索和全文检索面临的巨大挑战。9 通常认为中文分词有3种形式的方法，包括基于字典匹配的分词方法、基于语义的分词方法、基于统计的分词方法。其中第一种是目前应用最广泛和最成熟的技术。基于字典匹配的分词方法按照一定的匹配策略将输入的字符串与机器字典词条进行匹配。如果在词典中找到当前字符串，则匹配成功输出识别的词汇。按照匹配操作的扫描方向和不同长度优先匹配情况，常有的几种词典分词方法如下：l 正向最大匹配法（由左到右的方向）l 逆向最大匹配法（由右到左的方向）l 最少切分（使每一句中切出的词数最小）实际应用中上述各种方法经常组合使用，以达到最好的效果。真正实用的分词系统，都是把词典分词作为基础手段，结合各种语言的其他特征信息来提高切分的效果和准确度。有的实用系统中将分词和词性标注结合起来，利用句法和语法分析对分词策略提供帮助，在词性标注过程中迭代处理，利用词性和语法信息对分词结果进行检验、调整。9第三章 全文检索系统Lucene的技术分析1233.1 Lucene系统概述Lucene是Doug Cutting开发的一套全文检索工具包，是一个开放源代码的系统。目前，它是Apache软件基金会Jakarta项目组的一个子项目，提供了一个全文检索引擎的架构。Lucene并不是一个完整的全文检索引擎，但设计目的是为软件开发人员提供一个开发工具包，以方便普通开发者在系统中实现全文检索的功能。由于Lucene的原作者是一位资深全文索引检索专家，整个系统性能和稳定性良好。9目前已经有很多Java项目都使用了Lucene作为其后台的全文索引引擎，比较著名的有：l Jive: WEB论坛系统；l Eyebrows：邮件列表Html归档、浏览、查询系统；l Cocoon：基于XML的Web发布框架，全文检索部分使用了Lucene；l Eclipse：基于Java的开放开发平台，帮助部分的全文索引使用了Lucene。12作为一个开放源代码项目，Lucene从问世之后，引发了开放源代码社群的巨大反响，程序员们不仅使用它构建具体的全文检索应用，而且将之集成到各种系统软件中去，以及构建Web应用，甚至某些商业软件也采用了Lucene作为其内部全文检索子系统的核心。apache软件基金会的网站使用了Lucene作为全文检索的引擎，IBM的开源软件eclipse的2.1版本中也采用了Lucene作为帮助子系统的全文索引引擎，相应的IBM商业软件Web Sphere中也采用了Lucene。13 Lucene以其开放源代码的特性、优异的索引结构、良好的系统架构获得了越来越多的应用。Lucene作为一个全文检索引擎，其具有如下突出的优点：（1）索引文件格式独立于应用平台。Lucene定义了一套以8位字节为基础的索引文件格式，使得兼容系统或者不同平台的应用能够共享其建立的索引文件。（2）在传统全文检索引擎的倒排索引的基础上，实现了分块索引，能够针对新的文件建立小文件索引，提升索引速度。然后通过与原有索引的合并，达到优化的目的。（3）优秀的面向对象的系统架构，使得对于Lucene扩展的学习难度降低，方便扩充新功能。（4）设计了独立于语言和文件格式的文本分析接口，索引器通过接受Token流完成索引文件的创立，用户扩展新的语言和文件格式，只需要实现文本分析的接口。（5）已经默认实现了一套强大的查询引擎，用户无需自己编写代码就可让系统获得强大的查询能力，Lucene的查询实现中默认实现了布尔操作、模糊查询（Fuzzy Search）、分组查询等等。3.2 Lucene结构分析3.2.1 系统结构组织Lucene是一个优秀的全文检索引擎，其系统结构具有强烈的面向对象特征。首先是定义了一个与平台无关的索引文件格式，其次是通过抽象，将系统的核心组成部分设计为抽象类，具体的平台设计部分为抽象类的实现，此外与具体平台相关的部分比如文件存储也封装为类，经过层层的面向对象式的处理，最终达成了一个低耦合高效率、容易二次开发的检索引擎系统。12Lucene的系统结构与源码组织如图3-1所示：图3-1：Lucene系统结构与源码组织图从图中我们清楚的看到，Lucene的系统由基础结构封装、索引核心、对外接口三大部分组成。其中直接操作索引文件的索引核心又是系统的重点。Lucene的将所有源码分为了7个模块（在java语言中以“包”即package来表示），各个模块所属的系统部分也如上图所示。需要说明的是org.apache.lucene.queryPaser是作为org.apache.lucene.search的语法解析器存在，不被系统之外实际调用，因此这里没有当作对外接口看待，而是将之独立出来。从面向对象的观点来考察，Lucene应用了最基本的一条程序设计准则：引入额外的抽象层以降低耦合性。首先，引入对索引文件的操作org.apache.lucene.store的封装，然后将索引部分的实现建立在（org.apache.lucene.index）其之上，完成对索引核心的抽象。在索引核心的基础上开始设计对外的接口org.apache.lucene.search与org.apache.lucene.analysis。在每一个局部细节上，比如某些常用的数据结构与算法上，Lucene也充分的应用了这一条准则。在高度的面向对象理论的支撑下，使得Lucene的实现容易理解，易于扩展。Lucene在系统结构上的另一个特点表现为其引入了传统的客户端服务器结构以外的的应用结构。Lucene可以作为一个运行库被包含进入应用本身中去，而不是作为一个单独的索引服务器存在。这自然和Lucene开放源代码的特征分不开，但是也体现了Lucene在编写上的本来意图：提供一个全文索引引擎的架构，而不是实现。93.2.2 数据流Lucene系统中的主要数据流以及它们之间的关系，如图3-2所示：图3-2：Lucene数据流图图中很好的表明了Lucene在内部的数据流组织情况，并沿着数据流的方向也可以对Lucene内部的执行时序有清楚地了解。现在将图中的涉及到的流的类型与各个逻辑对应系统的相关部分的关系说明一下。图中共存在4种数据流，分别是文本流、token流、字节流与查询语句对象流。文本流表示了对于索引目标和交互控制的抽象，即用文本流表示了将要索引的文件，用文本流向用户输出信息；在实际的实现中，Lucene中的文本流采用了UCS-2作为编码，以达到适应多种语言文字的处理的目的。Token流是Lucene内部所使用的概念，是对传统文字中的词的概念的抽象，简单的讲Token就是一个词和所在域值的组合。字节流则是对文件抽象直接操作的体现，通过固定长度的字节（Lucene定义为8比特位长）流的处理，将文件解脱出来，也做到了与平台文件系统的无关性。查询语句对象流则是仅仅在查询语句解析时用到的概念，它对查询语句抽象，通过类的继承结构反映查询语句的结构，将之传送到查找逻辑来进行查找的操作。143.3 Lucene索引器3.3.1 Lucene索引器概述文档索引是Lucene系统的核心功能。有专门的API用来实现索引建立和管理功能。Lucene可以处理多种格式的文档，包括磁盘文件、电子邮件地址、网页以及数据库的记录。Lucene的索引格式可以采用独立索引模式和复合索引模式。l 独立索引模式是指每个Document独立索引成一个文件，这种方法检索速度比较快，但是不适合大量文件的处理。l 复合索引模式是把等待索引的全部Document索引成一个文件，这个文件包含的文档内容各不相同，甚至包括域项目不同的异构型文档。Lucene的索引采用了一套非常高效的数据结构，通常以单个或者一系列索引文件形式存放在系统目录中。索引文件根据需要可以存放在硬盘和内存中。放在硬盘上的索引可以用FSDirectory管理，放在内存的索引用RAMDirectory管理。内存索引检索速度快，但是关机后会丢失。硬盘索引可以长期保存，但是检索时需要进行I/O操作，速度相对较慢。实际使用过程中，经常采用两者结合的方式，提高总体效率。从系统和使用方式来看，Lucene还具有以下特点：l 索引结构以文件形式存储，不必依赖于数据库或者某种特定平台。l 支持分块索引，对新加入的文件建立新的索引，缩短索引生效时间，然后通过索引合并建立整体索引。3.3.2 Lucene索引结构Lucene索引结构可以分为索引（Index）、索引段（Segment）、索引文档（Document）、索引域（Field）和索引项（Term）几个不同层次。Lucene每个索引的结构由一个或者多个段组成，每个段包含一个或多个文档，每个文档管理了一个或多个域，每个域由一个或多个索引项组成，每个索引项是一个索引数据。索引结构几个组成部分的层次关系如图3-3所示：图3-3：Lucene索引层次图1） 索引（Index）Lucene的索引结构最终体现到特定格式的磁盘文件来存储。索引在内存和磁盘中，都使用相同的逻辑结构。在磁盘上Lucene索引以格式化的文本形式存储。Lucene每个索引的结构