全文检索技术研究与应用论文

   全文检索是现代信息检索技术的一个非常重要的分支，它是处理非结构化数据的强大工具，也是搜索引擎的核心技术之一。本文对中文全文检索的有关技术进行了较为深入的研究。在基于字表的全文索引方面，本文提出了一种改进的倒排索引结构，同传统索引结构相比，更便于索引的构建、维护、更新。本文的重点放在了全文检索技术的应用上，对如何利用新技术、改善检索系统的结构、提高检索系统的性能和效率、加快检速度、不断适应网络信息发展等方面做了重点研究。

    全文检索是一种IO密集型的应用，以往的全文检索系统的开发多在关系数据库的基础上进行。本文针对全文数据库的特点，深入讨论此法弊端与不足，并提出了在文件系统上构建的解决方案。由于目前全文检索系统的开发平台并不多见，本文介绍了一种全文检索引擎工具包一Lucene，它功能强大，小巧精悍，便于嵌入各种应用。近年在世界各地被广泛使用，诸如IBM等公司都使用其核心代码。作为一个开源软件，它为我们学习搜索引擎的核心技术提供了绝佳的机会，对其剖析研究、进行二次开发，是一件很有意义的事情。

   在应用方面，本文主要工作是本校学位论文全文数据库的设计与实现。

关键字：全文检索  倒排文件  Lucene  全文数据库  自动分词

THE RESEARCH AND IMPLEMENTATION

OF FULL-TEXT RETRIEVALSYSTEM

（ABSTRACT）

Full-text retrieval is an important information retrieval technology. It is a powerful tool fordealing with nonstructural data, and is one of the key technologies of the search engine. This paper deeply research on Chinese full-text retrieval technology. In the filed of full-text index based on word inverted table, a improved word-based Chinese inverted index structure is proposed which has a better performance than traditional approaches, and convenient for constructing, maintaining and updating index. According. to its characteristic, we design its corresponding optimized search method. Analysis shows that better dynamic performance and high indexing speed is possible using this structure. This paper pays more attention in application of full-text retrieval technologies. How to use new technique, optimize the structure of retrieval system, improve performance and efficiency, quicken search speed and adapt the development of current web is also discussed in this paper.

Full-text retrieval is an I/O intensive application.. Its previous developments are carried on the basis of relation database. This paper deeply discusses the abuse and deficiency of this mode according to its characteristic. Because the development platform of full-text retrieval is absent currently, Lucene, a full-text search engine toolkit, is introduced into the paper. It has powerful performance. and its body is cabinet, capable and vigorous. this convenient for it embedded applications. At present, Lucene is employed world abroad, so that many professional companies such as IBM also use its core code. As an open source code soft, Lucene offer a superexcellent chance to study search engine key technology. It is worthful to take a parse. research and carry second development to it.

In the application aspect, this paper work mostly in the design and implement of the degree dissertation full-text database in university. 

KEY WORDS: Full-text，Inverted File， Lucene，Full-text Database

                Divided Syncopation

一、全文检索技术简介

1.1 论文研究背景

信息时代产生了大量数字信息, 而这些信息大致可分为两类：结构化数据和非结构化数据，结构化数据指的是诸如企业财务帐目和生产数据、学生的分数数据等等，非结构化数据的则是一些文本数据、图象声音等多媒体数据等等。据统计，非结构化数据占有整个信息量的80%以上。

对于结构化数据，用RDBMS（关系数据库管理系统）技术来管理是目前最好的一种方式。但是由于RDBMS自身底层结构的缘故使得它管理大量非结构化数据显得有些先天不足，特别是查询这些海量非结构化数据的速度较慢。而通过全文检索技术就能高效地管理这些非结构化数据。

国内外对全文检索的研究方兴未艾，己有一些较成熟的商用产品相继问世。中文全文检索与英文检索相比，由于自然语言体系不同，索引机制也不完全相同。英文以词为单位建索引，与字母无关，而中文以字为最小单位。再者，英文的分词以空格和标点为分界符，而汉字的分词往往依赖于词库。因而中文全文检索与英文实现相比困难些。不得不承认目前国内的研究水平与国际上还有较大差距，坐等国外成果，然后加以移植改造的老路是行不通的，因此在国内进行全文检索的研究非常必要。

1.2什么是全文检索

全文检索是指计算机索引程序通过扫描文章中的每一个词，对每一个词建立一个索引，指明该词在文章中出现的次数和位置，当用户查询时，检索程序就根据事先建立的索引进行查找，并将查找的结果反馈给用户的检索方式。这个过程类似于通过字典中的检索字表查字的过程。

全文检索是指以文本为检索对象，允许用户以自然语言根据资料内容而不仅是外在特征来实现信息检索的手段。全面、准确和快速是衡量全文检索系统的关键指标。全文检索不仅可以实现对数据资料的外部特征的检索，诸如标题、作者、摘要、附录等，而且还能直接根据数据资料的内容进行检索，实现了支持多角度、多侧面地综台利用信息资源。

总之，全文检索技术是现代信息检索的一项重要技术。

1.3 全文检索与关系数据库

   全文检索提出基于文件系统的全文数据库，使用文件系统存储文档建立全文库时，文本的添加，删除，更新可以通过全文数据库管理系统来实现，因此可以说是实现了一个微型的专门为全文检索设计的数据库系统。所谓微型的，是因为它只实现数据的增、删、改、查找、获取，而不涉及复杂的事务处理等。

使用文件系统构建全文数据库的根据如下:

   (1)无论关系数据库还是全文数据库最终数据都是以文件的形式存在的。数据库实现的基础是文件，对数据库的任何操作最终要转换为对文件的操作。当前占主流的关系数据库是文件系统的发展。文件系统中每个文件存储同质实体的数据，各文件是孤立的，没有体现实体之间的联系，关系数据库中，数据的物理组织必须体现实体之间的联系，支持数据库的逻辑结构，因此数据库要存储四方面的数据:数据描述(即数据外模式，模式，内模式)、数据本身、数据之间的联系和存取路径，这四个方面的数据都要采用一定的文件组织方式组织存储起来[1]。

   而全文数据库可以说是介于文件系统和关系数据库之间的体系结构，它一般包含的实体少，实体间的关联也少，结构相对简单，对事务性和并发性要求不高。所以一般情况下，基本的检索过程应采用文件系统来实现，这样使得查询直接、快速，有效提高执行速度。

   (2)全文数据库不需要事务支持

   考虑到全文数据库系统的操作主要是读数据，写操作主要是插入新数据，删除和修改几乎没有。插入数据往往是间隔一段日期，待积累了一定的新文献数后才进行。而且即使有数据插入，也不需要锁住读操作，因为用户只是查询文献，暂时看不到新加入的文章，以往的数据照样可以使用。所以，数据库根本不需要事务支持，而对事务的管理恰恰是很费时间的，这样在效率上就能得到很大提高。

   实际上，当前各大搜索引擎，其后台存储的主流设计都是基于自设计的文件系统。

1.4 全文检索需要解决的问题

     一套完整的全文检索一般包括：

     1 对不同文本的统一处理；

     2 索引的建立，考虑索引压缩率，是否支持动态索引更新等问题；

     3 对汉语词语进行正确的切分；

     4 检索问题，考虑检索效率，查全率，查准率等问题；

     5 排序问题。

本文就围绕以上5个问题进行分析与研究。

二、建立索引库

2.1索引文件分类

2.1.1、顺排档结构

    顺排档文档是以DocID为主序的，每一文档下存放各自出现的词的ID及各词所出现的次数和具体位置信息，各数据项的存储长度固定[2]。

2.1.2、倒排档结构

1）、一级索引：一级索引文件属于记录式文件，每一记录大小固定，共有三个数据项构成，WordID、文档数、第一个文档开始位置。其中WordID是词典中词条的ID，文档数是指这个词总共在多少个文档中出现，文档开始位置是一个文件指针指向二级索引中出现当前词的文档集中的第一个文档存储位置，这个指针是一个长整形值相当于指明了是二级索引文件中的第几条记录，因为各记录长度也是固定大小。通过这个指向可以直接定位到二级索引文件读取位置，然后读取nDocs个记录即可，因为它们是存放在连续的地址空间上。

2）、二级索引：二级索引也是一种记录式文件，每一记录有三个数据项组成，DocID、出现次数、第一个Hit位置。其中DocID是文档的ID，出现次数指的是当前文档中某一个词出现的次数，第一个Hit位置也是一个指针，指向Hits文件中的某一位置。通过这个指针就可以直接定位到Hits位置中的读取位置，这样连续读取nHits个记录就可以将所有当前词在当前文档中的出现的位置信息都读入。这些文件将属于同一WordID下的所有文档记录按其词在整个文档的权值从大到小排列。

3）、Hits位置信息文件：这些文件每一记录只有一个数据项，即Hit位置信息，只记录了各词在文档中出现的位置。将同一词在同一文档中的出现位置按出现的先后排列。这样在读取文档并提取摘要时只需对字符串从头到尾扫描一边即可，不需要来回扫描。

2.2倒排索引压缩

2.2.1倒排索引压缩初步实现

一个倒排索引通常由字典表文件（dictionary file）和记录文件（postings file）两部分组成。字典文件记录了文本集中出现的每个单词及其倒排列表在记录文件中的位置和大小等信息。一个单词对应的倒排列表可以表示为：

>,…,>,…,>>

n表示单词在n个文档中出现，di为文档ID，fi为单词在文档di中出现的词频，是单词出现在某个文档中的位置列表。事实上，一个倒排列表可拆分为三部分。

1.一个文档ID序列（1≤i≤n）。

2.n个位置序列。

3.一个词频序列。其中，第1和第2两个序列都是递增的整数序列。鉴于这种递增的特性，可以用间隔di+1-di和pik+1-pik来代替序列中的值，那么上边三个整数序列就转化为如下形式。

1.一个文档ID间隔序列。   ？

2.n个位置间隔序列。

3.一个词频序列。转化成间隔后，没有损失任何信息，因为初始倒排列表总是可以通过计算间隔的和还原，此外，还给序列的取值带来了两个影响：样本空间缩小、概率分布不均衡性扩大，因此预示着存在基于概率分布的高效压缩方法。目前己经提出了一些模型描述整数值的概率分布，适用于对以上任一序列的压缩。这些模型可以分成两类。

1.全局模型，所有序列使用相同的压缩参数。

2.局部模型，对于不同序列，其压缩参数是不同的，这个参数通常是单词的出现频率。局部模型的压缩效率一般高于全局模型，且在解码速度方面也很有优势，但实现更复杂。

2.2.2动态文本集的倒排索引压缩方案

我们考虑文本集动态性时，将文本内部的动态调整用两次文本层次的调整代替，即对一个文本作文字改动视为删除旧文本和增加新文本，因此一般只考虑文本层次的索引动态同步调整。上文3.1节提到一个倒排列表可拆分成三部分序列，事实上这三部分的动态特性并不相同，根据这一特点，我们可以采用混合编码的方案，对三部分序列实施不同的压缩方法，力求在满足动态性的前提下，尽可能地实现高压缩率。

位置序列记录的是某单词在一个文本内部的位置，由于只考虑文本层次的增加、删除，所以该序列内部的值不会发生任何的改动，它是静态的，可以采用压缩率较高的任何压缩方法。与文档ID序列和词频序列相比，位置序列占用的索引空间往往多于二者，故而位置序列的压缩对整个倒排索引的压缩率起决定性作用。到目前为止，压缩率最高的首推二进制内插编码，虽然它的压缩与解压比较耗时，但与由压缩减少的I/O时间相比，可以忽略，因此我们可以对位置序列采用二进制内插编码。

与位置序列不同，文档ID序列和词频序列会随文档的增加、删除而增删序列的元素，所以必须采用支持动态性的压缩方法。二进制内插编码虽然有较高的压缩率，但它不支持序列的动态更新，所以不能采用。能够支持动态序列的压缩方法主要有：可变字节编码、γ编码、和δ编码。三者中压缩率最高的是δ编码，所以对两个序列都采用δ编码。

需要指出的是，由于文档ID序列是递增序列，所以多将其先转化成间隔序列后再进行压缩，这就给后续的增加元素操作带来了困难。例如，文档ID序列<3,8,9,11,12,13,17>，它对应的间隔序列为<3,5,1,2,1,1,4>，对该序列进行压缩，如果今后增加一个文档19，则需要知道文档ID序列最后一个文档ID的值17才能求两者的间隔值2=19-17，而由间隔序列得出17必须从头到尾解压整个序列，然后求总和才能得到，这就需要额外的I/O时间和解压时间，尤其是对于较长的序列来说更是一笔可观的开销。为避免这一问题，我们可以把文档ID当前的最大值存放到单词表里该倒排列表对应单词信息中。

词频序列不是递增序列，不用转化为间隔形式，因此不存在类似文档ID序列的问题。

从文档ID间隔序列中删除一个元素则比较简单，只需修改其后的一个元素值为两者的和即可。如上例中的文档ID序列，如果删除文档9，则间隔序列修改为<3,5,3,1,1,4>。（第三个3=1+2）

2.2.3 Lucene压缩技术

为了减小索引文件的大小，Lucene对索引也使用了压缩技术。首先，对词典文件中的关键词进行了压缩，关键词压缩为<前缀长度，后缀>，例如：当前词为“阿拉伯语”，上一个词为“阿拉伯”，那么“阿拉伯语”压缩为<3，语>。其次大量用到的是对数字的压缩，数字只保存与上一个值的差值（这样可以减小数字的长度，进而减少保存该数字需要的字节数）。例如当前文章号是163（不压缩要用3个字节保存），上一文章号是16382，压缩后保存7（只用一个字节）。 注意是“上一个词”。由于词典是按顺序排列的，这种压缩方法的效果会非常显著。

2.3索引增量更新

2.3.1利用B树实现倒排索引的更新

文献[3]提出在倒排索引的字典表上建一个B树索引，以支持字典表的扩充。B树的索引项就是单词，一个单词对应的倒排列表放在一个B树块中，如果一个块装不下，则在堆文件（heap file）中分配一片连续的空间，再从B树叶子节点链一条指针到堆文件中。此后，若倒排列表还要膨胀，超出了已有空间，则重新在堆文件（heap file）中分配一片空间，把原倒排列表迁移到新空间中，再将新增倒排列表合并到后面，然后将旧空间标记为空闲。对这个堆文件的管理可以采用动态存储空间分配的算法，如伙伴系统。

使用堆文件来处理溢出，会增加查询时的I/O的时间。由于使用伙伴系统管理堆文件可能导致频繁地申请和释放空间以及频繁地迁移索引数据。

在字典表上建一个B树，显然需要额外的硬盘空间存放B树索引块，而且每次查找倒排列表都需要从B树的树根遍历到叶子节点，因此增加了查找的时间。

2.3.2 Dual-Structure索引结构

文献[3]提出了一种Dual-Structure索引结构，它动态地区分长、短倒排列表，并对长、短列表采用两种不同的存储结构及配套的检索、更新策略。

其一是针对短倒排列表的，某词通过静态散列函数映射到桶里，一个桶可以装多个倒排列表，桶数是固定的，且每个桶都只有一个存储块。每个词的倒排列表初始都是短倒排列表，当某个桶溢出时，将桶中最长的倒排列表晋升为长倒排列表，在字典表中做上标记后，将它迁移到长倒排列表使用的存储结构中。这样就动态地实现了长、短倒排列表的区分。另一种是将长倒排列表放在变长的连续块中，且末尾预留一部分空闲空间，这些块不让其他词的倒排列表共享。对于给定的词，可以通过查单词表来判定它是否对应一长倒排列表。

该方法有以下不足。

1.它只考虑了文档的插入操作，而忽略了删除操作。

2.采用静态散列函数，不管文档的多少，桶的大小及桶数都不能改变，且不同桶之间不能共享存储块。这样，当文档量很少时，桶空间大量闲置，造成空间的浪费。而当文档量很大时，即使是非高频词的倒排列表也会变得较大，桶数远远满足不了它们的需要。所以，需要一种动态散列表的支持，使得桶的数量可变。

3.动态地区分长、短倒排列表的策略虽然简单，但也不尽合理。只要发生桶溢出便把最长的倒排列表转移到长倒排列表的存储区，会误把相当数量的短倒排列表排挤到长倒排列表中。

4.对长倒排列表的管理采用的是绕开操作系统直接管理硬盘的方式，这样做不适合多任务操作系统，因为当还有其他程序要读写磁盘时，很难保证不发生错误。

2.3.3 Lucene索引过程优化

大部分的搜索（数据库）引擎都是用B树结构来维护索引，索引的更新会导致大量的IO操作，Lucene在实现中，索引一般分2种情况，一种是小批量的索引扩展，一种是大批量的索引重建。在索引过程中，并不是每次新的DOC加入进去索引都重新进行一次索引文件的写入操作（文件I/O是一件非常消耗资源的事情）。Lucene先在内存中进行索引操作，并根据一定的批量进行文件的写入。这个批次的间隔越大，文件的写入次数越少，但占用内存会很多。反之占用内存少，但文件IO操作频繁，索引速度会很慢。在IndexWriter中有一个MERGE_FACTOR参数可以帮助你在构造索引器后根据应用环境的情况充分利用内存减少文件的操作。根据我的使用经验：缺省Indexer是每20条记录索引后写入一次，每将MERGE_FACTOR增加50倍，索引速度可以提高1倍左右。

三、 中文分词研究

目前在中文搜索引擎领域，国内的搜索引擎已经和国外的搜索引擎效果上相差不远。之所以能形成这样的局面，有一个重要的原因就在于中文和英文两种语言自身的书写方式不同，这其中对于计算机涉及的技术就是中文分词。

3.1 什么是中文分词

众所周知，英文是以词为单位的，词和词之间是靠空格隔开，而中文是以字为单位，句子中所有的字连起来才能描述一个意思。例如，英文句子I am a student，用中文则为：“我是一个学生”。计算机可以很简单通过空格知道student是一个单词，但是不能很容易明白“学”、“生”两个字合起来才表示一个词。把中文的汉字序列切分成有意义的词，就是中文分词，有些人也称为切词。我是一个学生，分词的结果是：我 是 一个 学生。

3.2 为什么需要中文分词

目前的搜索引擎，大多是基于一种称为倒排索引的结构[4]。以什么做为索引的Key值，直接影响到整个搜索引擎的准确度、召回率、速度。我们先看看不使用中文分词的情况。

如果不使用中文分词，可以采用单个汉字索引方式。例如，雅虎，先索引"雅"字，然后再索引"虎"字。同样，对于一篇文章，先把所有的汉字都单独索引一次，并记录他们的位置。搜索过程中，也是先找"雅"字的所有文档，再找"虎"字的所有文档，然后做交叉"与"运算，即包含这两个字，而且位置连续的文档才会做为符合要求的结果。这种方式是最基本的索引方式，现在有些小引擎中还在使用。但这里存在一个很有挑战性的问题：总共的常用汉字是3000多个，我们每次查询过程中，进行"与"操作的计算量会相当大，对于大数据量搜索引擎来说(超过10亿的文档)，每天上亿次查询，这样的索引结构，无疑是对硬件和算法的极大挑战。

考虑到速度问题，如果不使用分词，还有另外一种选择：n元组合索引方式，2元/3元等。拿2元来说，中国人，先索引"中国", 再索引"国人"。同样，对于一篇文章，以2为单位，把所有相邻的汉字都索引起来，并记录他们的位置。搜索过程中，也是先找包含"中国"的所有文档，再找" 国人"的所有文档，然后做交叉"与"运算，即包含这两个单元，而且位置连续的文档才会做为符合要求的结果。这样以两个字做为索引单元，可以大大减少在搜索过程中的计算量。

以上两种方式，都可以不需要分词，也能实现搜索引擎的索引和搜索。但是这里存在一个不可忽视的问题：准确度。一个很常见的例子：和服，如果按照上面两种方式，都会查到包含"主板 和服 务器"的文档； 北大 也会得到"东 北大学"。对于大数据量的搜索引擎来说，每个搜索次都会有成千上万个结果，用户已经很挑选他真正想要的文章，如果这里还要增加许多错误，估计用户体验会极差。这时候，我们需要中文分词。

词，是中文语言中最小的语意单位。以词为单位做为搜索引擎的索引的Key值，会大大提高搜索引擎结果的准确性，同时保证了搜索过程中计算量小。其实还有一个优点，以词为单位的索引，索引库会比上两种方式小很多。很明显：如果以 中国人做为一个词，那么搜索的时候，不需要任何"与"运算，索引的时候记录也会减少。

3.3 中文分词技术

中文分词技术属于自然语言处理技术范畴，对于一句话，人可以通过自己的知识来明白哪些是词，哪些不是词，但如何让计算机也能理解？其处理过程就是分词算法。

现有的分词算法可分为三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法[5]。

3.3.1、基于字符串匹配的分词方法

这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短）匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下：

◆ 最小匹配算法

在所有的分词算法中，最早研究的是最小匹配算法(Minimum Matching)，该算法从待比较字符串左边开始比较，先取前两个字符组成的字段与词典中的词进行比较，如果词典中有该词，则分出此词，继续从第三个字符开始取两个字符组成的字段进行比较，如果没有匹配到，则取前3个字符串组成的字段进行比较，依次类推，直到取的字符串的长度等于预先设定的阈值，如果还没有匹配成功，则从待处理字串的第二个字符开始比较，如此循环。

例如，"如果还没有匹配成功"，取出左边两个字组成的字段与词典进行比较，分出"如果"；再从"还"开始，取"还没"，字典中没有此词，继续取"还没有"，依次取到字段"还没有匹配"(假设阈值为5)，然后从"没"开始，取"没有"，如此循环直到字符串末尾为止。这种方法的优点是速度快，但是准确率却不是很高，比如待处理字符串为"中华人民共和国"，此匹配算法分出的结果为：中华、人民、共和国，因此该方法基本上已经不被采用 。

◆ 最大匹配算法

基于字符串的最大匹配，这种方法现在仍比较常用。最大匹配(Maximum Matching)分为正向和逆向两种最大匹配，正向匹配的基本思想是：假设词典中最大词条所含的汉字个数为n个，取待处理字符串的前n个字作为匹配字段，查找分词词典。若词典中含有该词，则匹配成功，分出该词，然后从被比较字符串的n+1处开始再取n个字组成的字段重新在词典中匹配；如果没有匹配成功，则将这n个字组成的字段的最后一位剔除，用剩下的n一1个字组成的字段在词典中进行匹配，如此进行下去，直到切分成功为止。

例如，待处理字符串为"汉字多为表意文字"，取字符串"汉语多为表"(假设比较的步长为5，本文步长step都取5)与词典进行比较，没有与之对应的词，去除"表"字，用字段"汉语多为"进行匹配，直至匹配到"汉语"为至，再取字符串"多为表意"，循环到切分出"文字"一词。目前，正向最大匹配方法作为一种基本的方法已被肯定下来，但是由于错误比较大，一般不单独使用。如字符串"处理机器发生的故障"，在正向最大匹配方法中会出现歧义切分，该字符串被分为：处理机、发生、故障，但是使用逆向匹配就能得到有效的切分。

逆向最大匹配RMM(Reverse Directional Maximum Matching Method)的分词原理和过程与正向最大匹配相似，区别在于前者从文章或者句子(字串)的末尾开始切分，若不成功则减去最前面的一个字。比如对于字符串"处理机器发生的故障"，第一步，从字串的右边取长度以步长为单位的字段"发生的故障"在词典中进行匹配，匹配不成功，再取字段"生的故障"进行匹配，依次匹配，直到分出"故障"一词，最终使用RMM方法切分的结果为：故障、发生、机器、处理。该方法要求配备逆序词典。

一般来说根据汉语词汇构成的特点，从理论上说明了逆向匹配的精确度高于正向匹配，汉语语句的特点一般中心语偏后。有研究数据,单纯使用正向最大匹配的错误率为1/ 169 ,单纯使用逆向最大匹配的错误率为1/245。实际应用中可以从下面几方面改进，同时采取几种分词算法，来提高正确率;改进扫描方式，称为特征扫描或标志切分,优先在待分析字符串中识别和切分出一些带有明显特征的词,以这些词作为断点,可将原字符串分为较小的串再来进机械分词，从而减少匹配的错误率等。

◆ 逐字匹配算法

逐字匹配算法，基于TRIE索引树的逐字匹配算法,是建立在树型词典机制上，匹配的过程是从索引树的根结点依次同步匹配待查词中的每个字，可以看成是对树某一分枝的遍历。因此，采用该算法的分词速度较快，但树的构造和维护比较复杂。一种改进的算法是和最大匹配算法相结合，吸取最大匹配算法词典结构简单、 TRIE索引树算法查询速度快的优点。因此词典结构和最大匹配词典构造机制相似，区别在于词典正文前增加了多级索引。匹配过程类似TRIE索引树进行逐字匹配，在性能上和TRIE索引树相近。

还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245。但这种精度还远远不能满足实际的需要。实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过利用各种其它的语言信息来进一步提高切分的准确率。

一种方法是改进扫描方式，称为特征扫描或标志切分，优先在待分析字符串中识别和切分出一些带有明显特征的词，以这些词作为断点，可将原字符串分为较小的串再来进机械分词，从而减少匹配的错误率。另一种方法是将分词和词类标注结合起来，利用丰富的词类信息对分词决策提供帮助，并且在标注过程中又反过来对分词结果进行检验、调整，从而极大地提高切分的准确率。

3.3.2基于理解的分词方法

这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试验阶段。

3.3.3基于统计的分词方法

从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。定义两个字的互现信息，计算两个汉字X、Y的相邻共现概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常用字组，例如“这一”、“之一 ”、“有的”、“我的”、“许多的”等，并且对常用词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分词词典（常用词词典）进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。

到底哪种分词算法的准确度更高，目前并无定论。对于任何一个成熟的分词系统来说，不可能单独依靠某一种算法来实现，都需要综合不同的算法。据了解，海量科技的分词算法就采用“复方分词法”，所谓复方，相当于用中药中的复方概念，即用不同的药才综合起来去医治疾病，同样，对于中文词的识别，需要多种算法来处理不同的问题。

3.4分词中的难题

有了成熟的分词算法，是否就能容易的解决中文分词的问题呢？事实远非如此。中文是一种十分复杂的语言，让计算机理解中文语言更是困难。在中文分词过程中，有两大难题一直没有完全突破。

3.4.1歧义识别

歧义是指同样的一句话，可能有两种或者更多的切分方法。例如：表面的，因为“表面”和“面的”都是词，那么这个短语就可以分成“表面 的”和“表面的”。这种称为交叉歧义。像这种交叉歧义十分常见，前面举的“和服”的例子，其实就是因为交叉歧义引起的错误。“化妆和服装”可以分成“化妆 和服装”或者“化妆 和服 装”。由于没有人的知识去理解，计算机很难知道到底哪个方案正确[6]。

交叉歧义相对组合歧义来说是还算比较容易处理，组合歧义就必需根据整个句子来判断了。例如，在句子“这个门把手坏了”中，“把手”是个词，但在句子“请把手拿开”中，“把手”就不是一个词；在句子“将军任命了一名中将”中，“中将”是个词，但在句子“产量三年中将增长两倍”中，“中将”就不再是词。这些词计算机又如何去识别?

如果交叉歧义和组合歧义计算机都能解决的话，在歧义中还有一个难题，是真歧义。真歧义意思是给出一句话，由人去判断也不知道哪个应该是词，哪个应该不是词。例如：“乒乓球拍卖完了”，可以切分成“乒乓 球拍 卖 完 了”、也可切分成“乒乓球 拍卖 完了”，如果没有上下文其他的句子，恐怕谁也不知道“拍卖”在这里算不算一个词。

3.4.2新词识别

新词，专业术语称为未登录词。也就是那些在字典中都没有收录过，但又确实能称为词的那些词。最典型的是人名，人可以很容易理解句子“王军虎去广州了” 中，“王军虎”是个词，因为是一个人的名字，但要是让计算机去识别就困难了。如果把“王军虎”做为一个词收录到字典中去，全世界有那么多名字，而且每时每刻都有新增的人名，收录这些人名本身就是一项巨大的工程。即使这项工作可以完成，还是会存在问题，例如：在句子“王军虎头虎脑的”中，“王军虎”还能不能算词？

新词中除了人名以外，还有机构名、地名、产品名、商标名、简称、省略语等都是很难处理的问题，而且这些又正好是人们经常使用的词，因此对于搜索引擎来说，分词系统中的新词识别十分重要。目前新词识别准确率已经成为评价一个分词系统好坏的重要标志之一。

四、索引数据库的搜索

4.1词库查找方法

词库的查找过程其实是一个典型的字典问题（dictionary problem），可以使用三类方法。1.一类是基于单词比较(comparison based)的方法，如：顺序查找、折半查找、二叉排序树、平衡二叉树等。其查找的效率依赖于查找过程中比较的次数，且这类方法一般都有一个前提就是单词必须事先排好序。2.第二类是基于表示法(representation based)的方法，如：串树（trie）。其查找不是建立在单词的比较上，而是利用组成单词的字母字符序列或数字序列的逐个比较，尤其适合于英文单词和数值的查找。3.第三类则是无需经过任何比较，一次存取便能得到所查单词位置的散列法。通过对单词K作某种算术运算f(K)，计算的结果就是K及其相关数据的存储位置[45]。若对于不同的单词得到同一散列值，便产生了冲突。冲突会降低查询效率，因此应尽量避免。

4.2 lucene搜索算法 

1 把.tii文件调入内存[7]。

2 在内存中用二分查找找到相应的Block。

3 把.tis文件中相应的Block调入内存。

4 在Block中顺序找到相应的Term。

5 Term在索引里是有序排列的。

6采用二分查找机制来定位索引里的Term。

7在Index包TermInfosReader类中的实现代码。

 private final int getIndexOffset(Term term) throws IOException {

  int lo = 0;        // binary search indexTerms[]

  int hi = indexTerms.length - 1;

while (hi >= lo) {

int mid = (lo + hi) >> 1;

  int delta = term.compareTo(indexTerms[mid]);

if (delta < 0)hi = mid - 1;

else if (delta > 0) lo = mid + 1;

  else return mid;

}

  return hi;

}

4.3搜索过程优化

lucene支持内存索引：这样的搜索比基于文件的I/O有数量级的速度提升[8]。

而尽可能减少IndexSearcher的创建和对搜索结果的前台的缓存也是必要的。

Lucene面向全文检索的优化在于首次索引检索后，并不把所有的记录（Document）具体内容读取出来，而起只将所有结果中匹配度最高的头100条结果（TopDocs）的ID放到结果集缓存中并返回，这里可以比较一下数据库检索：如果是一个10,000条的数据库检索结果集，数据库是一定要把所有记录内容都取得以后再开始返回给应用结果集的。所以即使检索匹配总数很多，Lucene的结果集占用的内存空间也不会很多。对于一般的模糊检索应用是用不到这么多的结果的，头100条已经可以满足90%以上的检索需求。

如果首批缓存结果数用完后还要读取更后面的结果时Searcher会再次检索并生成一个上次的搜索缓存数大1倍的缓存，并再重新向后抓取。所以如果构造一个Searcher去查1－120条结果，Searcher其实是进行了2次搜索过程：头100条取完后，缓存结果用完，Searcher重新检索再构造一个200条的结果缓存，依此类推，400条缓存，800条缓存。由于每次Searcher对象消失后，这些缓存也访问那不到了，你有可能想将结果记录缓存下来，缓存数尽量保证在100以下以充分利用首次的结果缓存，不让Lucene浪费多次检索，而且可以分级进行结果缓存。

Lucene的另外一个特点是在收集结果的过程中将匹配度低的结果自动过滤掉了。这也是和数据库应用需要将搜索的结果全部返回不同之处。

参考文献

[1] 罗晓沛等.数据库技术(高级).北京:清华大学出版社，1999:102-103.

[2] Google搜索引擎技术实现探究  化柏林  中国科学技术信息研究所

[3] D.Cutting,J.Pedersen.Optimization for Dynamic Inverted Index Maintenance.in:Proceedings of the 13thAnnual International ACM SIGIR Conference on Researchand Development in Information Retrieval.Brussels,Belgium.1990.New York:ACM Press,1990.405~411

[4] A.Tomasic,H.Garcia-Molina,K.A.Shoens.Incremental Updates of Inverted Listsfor Text Document Retrieval.in:Proceedings of 1994 ACM SIGMOD InternationalConference on Management of Data.Minneapolis.1994.New York:ACM Press,1994.23(2):2~300

[5] 中文搜索引擎技术揭密：中文分词      作者Winter

[6] 汉语分词在中文软件中的广泛应用  李东 张湘辉  微软中国研究开发中心http://www.stlchina.org/twiki/bin/view.pl/Main/SESegment

[7] Lucene 算法介绍  作者：胡晓光

[8] Lucene：基于Java的全文检索引擎简介  作者：车东

致  谢

在设计系统的同时,我撰写了这篇论文,对系统的功能、 全文数据库的查询与访问等关键技术作了阐述。我们能在短短的两个月之内完成此次的毕业设计，当然也离不开教员对我们的指导。开始有许多不成熟的地方，但由于我们经常与教员取得联系，并请他对我们制作出的成果进行调试，而教员不厌其烦，总是及时地把他的宝贵意见提出来，这样我们在不断改进中又对所学的知识有了进一步的认识。

通过这次课题的研究，我对搜素引擎技术方面有很大的提高，使我的动手能力也有了一定的进展。所以在这里我要衷心感谢在这次毕业设计过程中再一次感谢我的指导老师周扬教员，她在我的整个课题设计过程中给予了细致的指导，提出了宝贵的意见。这些意见有的开阔了我的思路，使设计工作少走了不少弯路；有的指出了不足，使我得以迅速改进，对我的课题设计都有重要意义。

最后我还要感谢小组的其它同学。在课题设计当中，我们密切配合，互相帮助，互通有无，在很大程度上加快了课题设计的进度，如果没有他们的合作，这样一个课题不可能顺利的完成。