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 l...

Full description

Saved in:
Bibliographic Details
Published in:Electronic notes in theoretical computer science 2014-02, Vol.302, p.73-94
Main Authors: Nogueira Nunes, Daniel Saad, Ayala-Rincón, Mauricio
Format: Article
Language:English
Subjects:
Compressed suffix trees
Longest common prefix
String Processing
Suffix arrays
Suffix trees
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1571-0661
1571-0661
DOI:10.1016/j.entcs.2014.01.021