A Compressed Suffix Tree Based Implementation With Low Peak Memory Usage

Suffix trees (STs) and suffix arrays are well known indices which demand too much space for large inputs. Recently, several works explore a data structure called compressed suffix tree (CST), which offers the same functionality than suffix trees and is based on compressed suffix arrays, compressed longest common prefix information and navigational operations. In this paper, the implementation of a CST based on range-minimum-queries and nearest smaller value queries, which requires roughly more than the space needed to represent the index during the construction, is presented. Experiments show that this index is useful for many applications since, on the one side, one can execute complex traversals such as suffix links and longest common ancestor queries that are essential to deal with several questions about the combinatorial structure of sequences; and, on the other side, the structure results of practical interest for applications using computational environments in which the amount of available memory is restricted, because it fits in main memory of ordinary computers.