Engineering a lightweight suffix array construction algorithm

DOI10.1007/s00453-004-1094-1zbMath1082.68867OpenAlexW2109062349MaRDI QIDQ1882475

Paolo Ferragina, Giovanni Manzini

Publication date: 1 October 2004

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-004-1094-1

zbMATH Keywords

Suffix arraySuffix treeAlgorithmic engineeringFull-text indexSpace-economical algorithms

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Data structures (68P05)

Related Items

Suffix-sorting via Shannon-Fano-Elias codes ⋮ \(p\)-suffix sorting as arithmetic coding ⋮ The longest common extension problem revisited and applications to approximate string searching ⋮ On the number of elements to reorder when updating a suffix array ⋮ On-line suffix tree construction with reduced branching ⋮ Parallel suffix sorting for large string analytics ⋮ Fast, practical algorithms for computing all the repeats in a string ⋮ On the possible patterns of inputs for block sorting in the Burrows-Wheeler transformation ⋮ Algorithms for Indexing Highly Similar DNA Sequences ⋮ A simpler analysis of Burrows-Wheeler-based compression ⋮ Fast BWT in small space by blockwise suffix sorting ⋮ Faster suffix sorting ⋮ An elegant algorithm for the construction of suffix arrays ⋮ Space-efficient construction of Lempel-Ziv compressed text indexes ⋮ Space efficient algorithms for the Burrows-Wheeler backtransformation ⋮ Linearized suffix tree: An efficient index data structure with the capabilities of suffix trees and suffix arrays ⋮ The alternating BWT: an algorithmic perspective ⋮ Linear Time Suffix Array Construction Using D-Critical Substrings ⋮ IN-PLACE UPDATE OF SUFFIX ARRAY WHILE RECODING WORDS ⋮ RECONSTRUCTING A SUFFIX ARRAY ⋮ Inducing Suffix and LCP Arrays in External Memory