我和kexzcle，在这里讨论了一些问题。
其中他有个pdf怎么也搜不出来，就发给我了。

我跟踪了一下，用pdfbox从中取出String没问题。

也索引进去了， _0.cfs文件113K，UE打开，也能看到东西

但就是查询不出来。

后来我换了CJKAnalyzer，就OK了。

又经过试验，发现，不是IKAnalyzer的问题，而是你吐血推荐的IKQueryParser
换成Lucene自己的MultiFieldQueryParser就OK了。

附件怎么发呀？

附件不会发，以下是PDF中弄出来的文本：

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software, Vol.20, No.7, July 2009, pp.1768?1784 http://www.jos.org.c
doi: 10.3724/SP.J.1001.2009.03500 Tel/Fax: +86-10-62562563
circlecopyrt by Institute of Software, the Chinese Academy of Sciences. All rights reserved.

全文索引技术时空效率分析 ?
刘小珠 1,2,  彭智勇 3+
1( 武汉大学  软件工程国家重点实验室 , 湖北  武汉   430072)
2( 武汉理工大学  自动化学院 , 湖北  武汉   430070)
3( 武汉大学  计算机学院 , 湖北  武汉   430072)
Time and Space Efficiencies Analysis of Full-Text Index Techniques
LIU Xiao-Zhu1,2,  PENG Zhi-Yong3+
1(State Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072, China)
2(School of Automation, Wuhan University of Technology, Wuhan 430070, China)
3(School of Computer, Wuhan University, Wuhan 430072, China)
+ Corresponding author: E-mail: peng@whu.edu.cn
Liu XZ, Peng ZY. Time and space efficiencies analysis of full-text index techniques. Journal of Software,
2009,20(7):1768?1784. http://www.jos.org.cn/1000-9825/3500.htm
Abstract:  As one of the efficient methods of improving time and space efficiencies, the full-text index technique
has been well studied in recent years. According to the implementation ways, it can be classified into three
categories: Index technique, hybrid technique of index and compression, self-index technique. This paper reviews
the recent researches on this topic, which include the main techniques such as inverted files, signature files, suffix
trees, suffix arrays, compressed indices based on the indices mentioned above, self-index based on inverted files,
and self-index based on suffix arrays. This paper also introduces the basic theories, problems, progress as well as
space and time efficiencies of these techniques. Through a detailed efficiency analysis and comparison, the pros and
cons of the techniques are given. Finally, the important features of these techniques are summarized, and the future
research strategies and trends directions are pointed out as well.
Key words:  inverted file; signature file; suffix tree; suffix array; self-index; compression; time and space
efficiency
摘   要 : 全文索引技术 (full-text index technique)作为提高全文检索时空效率的有效方式之一 , 近年来得到了广
泛而深入的研究 . 根据全文索引实现技术的不同 , 将其分为三大类 : 索引技术、压缩与索引混合技术以及自索引
技术 (self-index technique). 从上述分类角度综述了全文索引时空效率方法中具有代表性的一些方法和技术 : 倒
排文件、签名文件、后缀树与后缀数组、基于这 3 种索引的压缩技术、基于倒排文件的自索引与基于后缀数
                                                            
? Supported by the National Natural Science Foundation of China under Grant Nos.60573095, 90718027 (国家自然科学基金 ); the
National High-Tech Research and Development Plan of China under Grant No.2006AA12Z210 (国家高技术研究发展计划 (863)); the
National Research Foundation for the Doctoral Program of Higher Education of China under Grant No.20050486024 (国家教育部博士学
科点专项科研基金 )
Received 2008-03-21; Accepted 2008-10-07



刘小珠  等 : 全文索引技术时空效率分析  1769
组的自索引的基本原理、所面临的问题及进展 , 并对这些技术的时空性能进行了详细的分析和比较 , 分析了各种
技术的适应环境及优劣 . 最后总结了上述技术的特点 , 指出了存在的问题以及未来的研究方向 .
关键词 : 倒排文件 ; 签名文件 ; 后缀树 ; 后缀数组 ; 自索引 ; 压缩 ; 时空效率 
中图法分类号 : TP311   文献标识码 : A
据统计 , 在联机存储的信息中 ,80%以上的信息是以文本的形式存在的 [1]. 如何快捷、 有效地管理和检索文本
这种非结构化的数据成为一项紧迫的研究任务 , 全文本信息检索 (full-text information retrieval, 简称全文检索 )[2]
技术由此应运而生 . 全文检索 [2]是指以文本为检索对象 , 允许用户以自然语言的方式根据资料内容 ( 例如文献中
的任何一个词语 ) 而不仅是外在特征 ( 诸如标题、作者、摘要、附录等 ) 来实现信息检索的手段 , 以支持多角度、
多侧面地综合利用信息资源 . 全文检索技术的出现 , 导致了信息检索领域的一场革命 . 它不仅可以实现情报检索
的绝大部分功能 , 而且还能直接根据数据资料的内容进行检索 .
全文检索的研究可追溯至 20 世纪 60 年代 [3]. 最初的全文检索是通过在文本中逐个字符扫描匹配完成的 ,
不需要其他辅助数据 . 随着文本集越来越大 , 人们对全文检索的需求越来越多样 , 这种顺序比较方法效率低下的
弊端就凸现出来 . 同时 , 由于早期受到计算机等技术的限制 , 既无法实现大量文本的存储 , 又不能实现快速的信
息检索 . 因此 , 全文检索的时间与空间效率一直是人们衡量文本检索系统的关键指标之一 . 如何既能实现大量文
本的有效存储 , 又能实现快速、准确的信息检索成为人们追求的目标 . 全文索引技术 (full-text index technique) 作
为提高时空效率的有效方式之一 , 得到了广泛而深入的研究 . 经过近几十年的发展 , 人们在全文索引的时空效率
研究中取得了很多实质性的成果 , 并得到了广泛的应用 . 根据实现技术的不同 , 本文将全文索引的时空效率研究
方法分为如图 1 所示的 3 类 .
Time and space efficiencies
of full-text index technique
Index technique Hybrid of index and compression technique Self-Index technique
Inverted files[4,5]
Signature
files[6-8]
Suffix trees[9] Gamma and
delta[25,26]
Golomb[27,28]
Bayesian[32]
D-Gap[34]
Belluni[13,29-31,33]
Dictionary[35,36]
Compressed
inverted files
Compressed
suffix arrays
CAS[47]
Succinct index[48]
Inverted file-
based
Suffix array-
based
D-Gap-Based[46]
Location
function-based
Lempel-
Ziv-Based
Suffix arrays[10,11]
FMI[44]
WTI[55]
RMI[54,56]
AFI[58,59]
CSA[60,61]
GCSA[51,62]
FM[65]
Compressed
signature files
Huffman-Based
compression[42,43]
Subsequence array
model[24]
Hybrid index
Adjacency matrix
based[23]

Fig.1  Classification of research methods on time and space efficiencies of full-text indexes
图 1  全文索引的时空效率研究方法分类 
一是索引技术 . 人们受到书目索引的启发提出了全文索引的思想 , 通过存储辅助的索引数据 , 在适当地牺牲
空间效率的前提下 , 显著地提高了全文检索的时间效率 . 并且提出了倒排文件 [4,5] 、签名文件 [6?8] 、后缀树 [9]与后
缀数组 [10,11]等具有代表性、应用广泛的全文索引模型 .
二是压缩与索引混合技术 . 一方面 , 通过将各种索引技术的优点相结合实现混合索引技术以提高全文检索
的性能 . 另一方面 , 随着计算机技术的发展 , 人们将各种数据压缩技术引入全文检索系统中 , 在适当地牺牲时间
效率的前提下 , 不仅有效地实现了海量文本信息的存储 , 而且实现了高效的全文检索 .



1770 Journal of Software 软件学报  Vol.20, No.7, July 2009  

三是自索引 (self-index)技术 . 通过充分地发展压缩索引技术 , 提出了使时空效率同时提高成为可能、完全不
依赖于原文本的新一代索引技术——自索引 . 自索引技术从一定程度上改变了传统索引技术与压缩技术在时
间效率与空间效率上相对立的矛盾 .
本文着眼于全文索引技术时空效率的研究 , 从上述分类角度综述了全文索引时空效率方法中具有代表性
的一些方法和技术 , 并对相关技术的性能进行比较 . 重点讨论了索引技术、压缩与索引混合技术以及自索引技
术的基本原理及进展 , 从相关问题、现状和趋势等方面进行归纳和评论 . 第 1 节介绍 3 种具有代表性的索引技
术并对 3 种技术的时空性能进行对比分析 . 第 2 节讨论混合索引技术、压缩与索引混合技术并对 3 种压缩索引
技术的性能进行比较分析 . 第 3 节介绍两种自索引技术 , 并对这两种自索引的性能进行比较分析 . 最后对当前工
作存在的问题进行分析与总结 , 并展望相关技术的未来发展 .
1   索引技术 
索引 (index) 最早出现在文献系统中 , 从这个意义上讲 , 索引是指文献集合中包含的事项或从文献集合中引
出概念的一种系统指南 , 这些事项或引出的概念是按已知的或已说明的可检索顺序排列的条目表达出来的 . 如
第 1 个专门为圣经编制的索引、带索引的书籍、医学文献索引目录等 . 以上索引的提出 , 为现代索引技术的发
展奠定了基础 , 具有深远的影响 . 随着计算机的出现 , 索引技术得到了迅猛的发展 , 尤其是数据库系统中索引技
术的研究 , 长期以来都得到高度重视 , 并提出了很多应用广泛的索引 . 但是传统数据库擅长于结构化数据的管
理 , 其索引是关键字索引 ; 而文本是典型的非结构化数据 , 文本检索要求针对全文建立索引 , 并且还要求具有相
关度排序、高亮显示等附加功能 . 这些差异使得全文检索系统的实现方式以及全文索引的结构与传统数据库截
然不同 , 因此无法通过对传统数据库技术的移植、借用和变换等简单方法来实现全文检索 , 必须寻求全新的理
论和方法 .
全文检索的关键技术是索引的建立与维护 , 本文重点讨论索引的建立机制 , 对于索引的维护与更新机制将
在后续论文中加以论述 . 目前具有代表性的索引技术有倒排文件、签名文件以及后缀树与后缀数组等 .
1.1   倒排文件
倒排文件 (inverted file)[4,5] 是从书目索引中受到启发而派生出来的 , 它是目前应用最广泛的全文索引模型 .
倒排文件机制是一种面向单词的索引机制 , 利用它可以提高检索速度 . 倒排文件主要分为以下两种 .
(1) 文档级倒排文件 (document-level inverted file)
在文档级倒排文件中 , 索引由两部分组成 : 第 1 部分是词表 . 包含两部分信息 : 一是包含词 t 的文档数量 ft, 二
是指向文档倒排列表的指针 . 第 2 部分是倒排列表 Lb. 包含两部分信息 : 一是包含词 t 的文档的标识 (identifier,ID)
号 d, 二是文档 d 中词 t 出现的次数 fd,t. 倒排列表由文档的 ID 号 d 与文档 d 中词 t 出现的次数 fd,t 组成的 ?d,fd,t?
序列对构成 .
(2) 单词级倒排文件 (word-level inverted file)
由于文档级倒排文件不包含词在文档中出现位置的具体信息 , 导致搜索效率不高 . 为了提高搜索效率 , 单词
级倒排文件对索引中的第 2 部分倒排列表 Lb 进行了改进 : 在 Lb 中加入了词在文档中出现的位置信息 pi, 即 
,,12
, , , ,...,
dtdt f
df pp p , 可以实现精确的定位 , 避免在原始文本中搜索的时间开销 .
在倒排文件中 , 对于有 n 个字符的文本 , 词表对空间的需求相对较小 , 其增长率为 O(nβ)[12], 其中 β 为 [0,1] 的
常量 , 在实际系统中 , 其值一般为 0.4~0.6 之间 . 对于 1GB 的文本信息 , 词表的大小约为 5MB. 索引中倒排列表的
存储空间为 O(n),索引的创建可以在 O(n) 的时间内完成 . 在实际应用中 , 由于存放倒排列表时还必须存放一些描
述信息 , 因此 , 倒排列表的存储空间变化较大 , 可能会达到原文件大小的 300%[12].
1.2   签名文件
签名文件 (signature file) 作为一种文本检索技术也被称为散列函数法 [6?8]. 在签名文件中 , 每个文档都通过
Hash 函数及重叠编码 (superimposed coding)产生一个称为目标签名 (target signature)的位串 . 具体做法是 : 将文档



刘小珠  等 : 全文索引技术时空效率分析  1771
中的每个词作为散列函数的参数产生二进制词签名 (w 位的向量 ),当把文档中每个词的词签名叠加时 , 就得到了
合并文档的目标签名 . 文档的目标签名结果顺序存入一个单独的文件 ( 签名文件 ) 中 . 由于签名文件采用的是二
进制的叠加 , 比原文件小得多 , 因此可以提供快速的检索 . 当数据对象较大时 , 为了提高效率 , 可将其分成若干个
逻辑块 , 每个逻辑块产生相应的目标签名 .
由于签名文件方式的产生采用了类似于二进制的编码方式 , 因此签名文件占用的空间很小 , 一般为原文本
集大小的 30%~50%[13]. 由于签名的产生方式决定了签名文件的大小及查询匹配的效率与正确性 , 为了提高签名
文件的时空效率 , 很多研究工作都集中在签名文件的设计方式上 , 并提出了很多应用广泛的签名文件 [14?17] 用以
进一步提高检索性能 .
1.3   后缀树与后缀数组
后缀树 (suffix tree) 是一种特殊的  Patricia 树 [9], 其最大的特点是将一个文本看成一组半无限串的叠加 , 而
这组半无限串的排序结果被表示成树的形式 .
对于有 n 个字符的文本 T1,n, 后缀树的空间效率为 O(n),创建时间为 O(n)[9,18,19]. 其存储空间为 O(nlog2 n) 比
特 , 后缀树的存储消耗巨大 , 在实际应用中至少是原文本大小的 10 倍 [20].
后缀数组 (suffix array) 由  Gonnet,Manber 和  Myers[10,11] 在改进后缀树模型的过程中提出 . 他们将后缀树的
叶节点串行化就得到了后缀数组 . 后缀数组是文本 T1,n 所有的后缀按照字母大小顺序排序后的简单排列 . 对 
于文本 T1,n, 其后缀数组为包含范围为 [1,n] 的排列的一个数组 A[1,n],该数组对于所有的 i∈[1,n] 有 [], [ 1],Ai n Ai nTT+< .
其中 “<”为按照字母顺序的大小关系 ,A[i]表示后缀数组中第 i 个元素对应到原始文本中后缀开始的位置 .
对于有 n 个字符的文本 T1,n, 后缀数组的存储空间消耗为 22log lognnnσ+ 比特 [10], 当搜索文本为 S1,m 时 , 搜
索时间消耗为 O(mlog2 n),文本定位时间消耗为 O(1), 显示 l 个字符的时间消耗为 O(l).这里 ,σ 为文本中字符所在
字符集的所有字符的个数 .
当用更多的空间存储连续的后缀数组之间的最长相同前缀信息时 [10,21], 对于有 n 个字符的文本 T1,n, 后缀数
组的存储空间消耗为 222log lognnnσ+ 比特 , 当搜索文本为 S1,m 时 , 搜索时间消耗为 O(m+log2 n),文本定位时间
消耗为 O(1),显示 l 个字符的时间消耗为 O(l).
1.4   3种索引的性能分析与比较
3 种索引的性能比较见表 1.
Table 1   Performance comparison of three kinds of indexes
表 1  3 种索引的性能比较 
Item Inverted file Signature file Suffix array
Space cost 50%~300% 30%~50% >>100%, nlog2 n+nlog2 σ
Index construction Slowly,O(n)  Slowly Slowly
Updating cost Medium,<O(n)  High High
Retrieval cost Medium, O(log2 n) +Merging time Medium Low, O(mlog2 n) 
Ranking Yes No No
Scalability Sublinear Linear Linear
Extensibility Yes No No
倒排文件有很多优点 , 如实现相对简单、查询速度快、很容易支持同义词查询以及排序查询等扩展功能 .
但是倒排文件也存在很明显的缺点 [22]: 由于倒排列表是以排序的方式进行存储的 , 因此在查询估计过程中对倒
排列表进行排序的开销巨大 ; 倒排列表的存储空间变化较大 , 导致倒排文件的大小范围可以从原文本大小的
50% 增加到 300%[12]; 索引创建开销较大 , 动态环境下索引文件更新和重新组织的开销与索引合并的开销要大 ;
对于有 N 个文档的文本集 , 倒排列表的磁盘访问次数为 logN, 因此磁盘访问开销大 .
如表 1 所示 , 签名文件的最大优点是空间效率高 , 由于其二进制特性 , 签名文件形成的索引存储结构紧凑 , 其
大小一般为原文本集大小的 30%~50%[13]. 但是存在误匹配是签名文件的一个主要缺点 . 尽管可以通过加大签名
宽度 w 来降低误匹配率 , 但这将增加索引空间的大小 . 并且在查询过程中 , 由于签名文件的特性与数据集的多样



1772 Journal of Software 软件学报  Vol.20, No.7, July 2009  

性导致误匹配不可避免 , 这在一定程度上增加了查询的开销 . 另外 , 签名文件不支持排序查询 , 同时 , 由于其二进
制特性难以实现功能的扩展 .
后缀数组的最大优点是极大地加快了检索速度 , 尤其是对某些特殊的检索 , 如前缀检索、范围检索等检索
效率更高 . 它的最大缺点是索引生成复杂、 空间开销大 , 而且创建过程中的空间开销更大 , 创建效率也很低 . 此外 ,
无论是创建过程还是检索过程都严重依赖原文本 . 后缀树和后缀数组在创建和合并的过程中均需要大量移动
数据 , 因此 , 两者的动态性能都不理想 . 另外 , 后缀数组与签名文件一样 , 不支持排序查询 , 扩展性较差 .
从空间开销上看 , 由于签名文件的二进制特性使其最具优势 , 而后缀数组由于重复存储了文本中的所有字
符 , 使其空间开销最大 , 达到 22log lognnnσ+ 比特 , 其大小一般是原文本的 10 倍 ; 由于索引所占的空间大、存储
结构紧凑 , 使得索引文件更新和重建的开销增加 , 这样不仅增加了磁盘的访问量 , 也增加了对内存空间的需求 .
因此 ,3 种索引的创建开销都较大 ; 在索引更新开销上 , 倒排文件由于支持部分更新 , 其性能略有优势 , ...