Space-efficient construction of compressed suffix trees
From MaRDI portal
Publication:2220837
DOI10.1016/j.tcs.2020.11.024zbMath1477.68556arXiv1908.04686OpenAlexW3102885865MaRDI QIDQ2220837
Nicola Prezza, Giovanna Rosone
Publication date: 25 January 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1908.04686
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Algorithms on strings (68W32)
Cites Work
- Unnamed Item
- Unnamed Item
- Lightweight algorithms for constructing and inverting the BWT of string collections
- Representing trees of higher degree
- Divide and conquer computation of the multi-string BWT and LCP array
- Lightweight metagenomic classification via eBWT
- Computing the longest common prefix array based on the Burrows-Wheeler transform
- Wavelet trees for all
- Compressed suffix trees with full functionality
- Fast BWT in small space by blockwise suffix sorting
- An extension of the Burrows-Wheeler transform
- Lightweight LCP construction for very large collections of strings
- An improved algorithm for the all-pairs suffix-prefix problem
- Average Linear Time and Compressed Space Construction of the Burrows-Wheeler Transform
- Suffix Arrays: A New Method for On-Line String Searches
- Space-Time Tradeoffs for Longest-Common-Prefix Array Computation
- Permuted Longest-Common-Prefix Array
- Breaking a Time-and-Space Barrier in Constructing Full-Text Indices
- Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time
- Alphabet-Independent Compressed Text Indexing
- Detecting Mutations by eBWT
- Lightweight BWT and LCP Merging via the Gap Algorithm
- Optimal Dynamic Sequence Representations
- String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure
- Linear time construction of compressed text indices in compact space
- Algorithm Theory - SWAT 2004
- Engineering a compressed suffix tree implementation
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
This page was built for publication: Space-efficient construction of compressed suffix trees