Department of Computer Science, P.O Box 26 (Teollisuuskatu 23)
FIN-00014 University of Helsinki, Finland.
Abstract. Suffix array is a data structure that can be
used to index a large text file so that queries of its content can be answered
quickly. Basically a suffix array is an array of all suffixes of the text
in the lexicographic order. Whether or not a word occurs in the text can
be answered in logarithmic time by binary search over the suffix array.
In this work we present a method to compress a suffix array such that the
search time remains logarithmic. Our experiments show that in some cases
a suffix array can be compressed by our method such that the total space
requirement is about half of the original.