A space and time efficient algorithm for constructing compressed suffix arrays

DOI10.1007/s00453-006-1228-8zbMath1123.68137OpenAlexW2017808314WikidataQ58062917 ScholiaQ58062917MaRDI QIDQ996703

Wing-Kin Sung, Wing-Kai Hon, Tak-Wah Lam, Kunihiko Sadakane, Siu-Ming Yiu

Publication date: 19 July 2007

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-006-1228-8

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Protein sequences, DNA sequences (92D20) Data structures (68P05)

Related Items

Extended suffix array construction using Lyndon factors ⋮ Lightweight algorithms for constructing and inverting the BWT of string collections ⋮ Suffix array and Lyndon factorization of a text ⋮ Stronger Lempel-Ziv based compressed text indexing ⋮ Lightweight data indexing and compression in external memory ⋮ Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space ⋮ Full-Text Indexes for High-Throughput Sequencing ⋮ On the string matching with \(k\) mismatches ⋮ Lightweight BWT Construction for Very Large String Collections ⋮ Space-efficient construction of Lempel-Ziv compressed text indexes ⋮ Rank/select on dynamic compressed sequences and applications ⋮ Parallel computation of the Burrows Wheeler transform in compact space ⋮ Haplotype-aware graph indexes ⋮ Computing the Burrows-Wheeler transform in place and in small space ⋮ Linked dynamic tries with applications to LZ-compression in sublinear time and space