在互联网和移动应用中,搜索引擎是人们检索信息的基础工具,并始终面临着性能问题的严峻挑战。搜索引擎的性能优化围绕着存储和计算两个关键命题,两者彼此制约且相互影响。倒排索引作为搜索引擎的核心数据结构,其压缩问题不仅涉及海量数据如何存储,同时会对召回计算效率产生直接影响。国内外的研究人员已经在倒排索引的压缩问题上积累了大量的研究成果。目前压缩倒排索引主要采用整数序列编码方案,通过精心设计的紧凑格式,降低数据元素的存储位宽。由人类语言书写的文档集合中,文档之间存在着天然的相似性。因此已经有研究者另辟蹊径,提出基于归约冗余的索引压缩方案。这种方案简化索引中重复内容的表述形式,降低索引文件的存储开销。尽管国内外的研究者对这种方案进行了诸多探索,但这些探索主要针对高重复度的特殊文档集,还缺少针对普通网页文档集的研究工作。更重要的是,很多工作没有考虑搜索引擎对召回计算效率的需求,缺少将归约冗余的压缩方案与召回计算有机地结合。除此之外,学术界的研究人员提出了多种基于Bitmap形式的索引结构。特别是近些年来,工业界已经实践了完全采用Bitmap形式实现的签名文件作为核心数据结构的文档召回模型,从而显著提升搜索引擎的文档召回效率。不过签名文件存在着严重浪费存储空间的突出问题,并且对可能采用的压缩方案提出了苛刻的设计需求。为了解决上述的这些难题,本文提出了基于上下文无关文法的压缩方案。针对倒排索引和签名文件分别设计了相应的压缩算法和文档召回算法,从而为搜索引擎优化问题中关于存储和计算的关键命题提出统一的解决方案。本文的具体工作包括如下三个方面:第一,提出基于上下文无关文法的倒排索引压缩算法和文档召回算法。本文首先分析网页文档集的倒排索引中普遍存在的数据冗余现象。针对这些冗余,提出了基于上下文无关文法的压缩算法搜索原始索引中的重复序列,并通过归约替换消除重复序列的存储开销。采用新编号替换重复序列,能够在降低索引存储开销的同时,为加速召回计算提供可行的优化方向。为了进一步提升压缩效果,本文提出了结合整数序列编码的文法压缩方案,并提出了完整的基于文法压缩和整数序列编码的分级索引结构。在Gov2索引和ClueWeb09索引中,编码文法方案比OptPFD编码方案分别减少至多17%和12%的文档编号存储位宽,同时会降低至多20%和8.4%的求交平均响应时间;它比Elias编码方案减少至多8.7%和6.4%的文档编号存储位宽,但会比后者增加至多15%和9.9%的求交平均响应时间。第二,提出优化文法索引时空性能的具体策略。首先针对网页文档集中文档相似度较低的问题,提出了一种自顶向下的文档重排算法,优化倒排列表中重复序列的分布情况。然后针对搜索引擎关于索引存储开销和召回计算效率的性能需求,提出了两种字典精简方案。两种方案分别基于归约序列对压缩效果和召回计算效率的实际贡献,有针对性地裁剪文法字典内容,提升索引的时空性能。最后通过分析文法压缩加速召回计算的具体原因,提出了适于文法压缩的选择性压缩方案。相比基于分段结构的PackedBinary编码方案,采用相同编码结构的选择性文法压缩方案在Gov2索引和ClueWeb09索引中分别减少至多11%和9.4%的文档编号存储位宽,并降低至多8.1%和14%的求交平均响应时间。第三,提出有损的基于上下文无关文法的签名文件压缩方案。首先通过具体分析和统计数据,阐述签名文件压缩问题的特殊性,提出解决相关难题的关键命题。然后针对关键命题,提出并验证了采用文法压缩方案的合理性与局限性。针对无损文法压缩方案的缺陷,提出了针对签名文件的有损文法压缩算法和序列求交算法。随后重点阐述有损压缩带来的压缩损失问题,提出并分析采用局部压缩的合理性与可行性。针对不同的局部选择策略,分别提出了选择性归约的文法压缩方案,以及基于文法压缩的混合索引方案。由Gov2文档集构建的签名文件中,选择性归约方案能够在召回错误率增幅不超过6.7%的条件下,降低原始签名矩阵约19%的存储位宽。在取得最优时空权衡结果的条件下,由Gov2文档集构建的混合索引会比归约签名文件降低约62%的存储位宽,但同时会增加约14%的求交平均响应时间。基于上下文无关文法的压缩方法为搜索引擎核心数据结构的存储和计算问题提供了完整的解决方案,同时也为提升索引结构在时空性能上的表现开拓了不同的优化思路。尽管本文是以搜索引擎的性能优化作为研究工作的应用背景,但所提方案在涉及大规模文档召回的相关场景中也是具有参考价值的。