给定一个有穷字符集∑，假设S是由∑中的n个字符组成的文本串，P则是由∑中的m个字符组成的模式串。模式匹配就是查找模式串P在文本串S中符合特定条件的所有出现。在巨大数据集的模式匹配问题中，采用索引机制可以有效地提高匹配速度。在建立索引的过程中，要考虑查找速度和空间开销的平衡，既要保证较高的查找速度又要有合理的空间开销。 后缀数组作为一种常用的文本索引机制，因其简单的结构和较好的空间效率，已成为模式匹配算法的基础数据结构。但是，它也有着文本索引机制共有的缺陷：实现快速查询的算法仍使用了较多的空问。为了解决这一问题，Grossi和Vitter对后缀数组进行压缩，在实现O(m／log∣∑∣n+log∣∑∣εn)的查找时间的同时，最多只需要(ε-1+O(1))nlog∣∑∣位的存储空间。其中ε为任意常数，且0<ε≤1。 本文提出了一种新的构造压缩后缀数组的方法：对原文本串s每logn位一组进行划分，每组只保存一个绝对地址，把后缀数组的存储空间降为O(n)位。同时，结合BWT变换的性质，把BWT(S)数组每logn个字符分为一组，各分组内每个不同字符只保存一个绝对位置，将每个字符平均所占空间降为O(1)位，从而有效解决空间瓶颈问题。