Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space

DOI10.1016/j.tcs.2007.05.030zbMath1125.68041OpenAlexW2015577249MaRDI QIDQ2456365

Joong Chae Na, Kun Soo Park

Publication date: 18 October 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.05.030

zbMATH Keywords

Burrows-Wheeler transformFM-indexCompressed suffix arrayindex data structure

Mathematics Subject Classification ID

Data structures (68P05)

Related Items (3)

Lightweight data indexing and compression in external memory ⋮ Space-efficient construction of Lempel-Ziv compressed text indexes ⋮ Computing the Burrows-Wheeler transform in place and in small space

Cites Work

• Unnamed Item
• A space and time efficient algorithm for constructing compressed suffix arrays
• Constructing suffix arrays in linear time
• Space efficient linear time construction of suffix arrays
• Suffix Arrays: A New Method for On-Line String Searches
• Linear work suffix array construction
• Indexing compressed text
• New text indexing functionalities of the compressed suffix arrays
• Algorithms and Computation
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• On the sorting-complexity of suffix tree construction

This page was built for publication: Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space