Burrows-Wheeler transform and LCP array construction in constant space
From MaRDI portal
Publication:511147
DOI10.1016/J.JDA.2016.11.003zbMath1359.68340arXiv1611.08198OpenAlexW3105423208MaRDI QIDQ511147
Travis Gagie, Felipe A. Louza, Guilherme P. Telles
Publication date: 14 February 2017
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1611.08198
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Algorithms on strings (68W32)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimal suffix sorting and LCP array construction for constant alphabets
- Lightweight algorithms for constructing and inverting the BWT of string collections
- On the number of elements to reorder when updating a suffix array
- Combined data structure for previous- and next-smaller-values
- Replacing suffix trees with enhanced suffix arrays
- Wee LCP
- Practical compressed suffix trees
- Low space external memory construction of the succinct permuted longest common prefix array
- LCP array construction using \(O(\operatorname{sort}(n))\) (or less) I/Os
- Computing the Burrows-Wheeler transform in place and in small space
- Computing the longest common prefix array based on the Burrows-Wheeler transform
- Lightweight data indexing and compression in external memory
- Compressed suffix trees with full functionality
- Lightweight LCP construction for very large collections of strings
- Computing the BWT and the LCP Array in Constant Space
- Average Linear Time and Compressed Space Construction of the Burrows-Wheeler Transform
- Suffix Arrays: A New Method for On-Line String Searches
- Permuted Longest-Common-Prefix Array
- Universal codeword sets and representations of the integers
- Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time
- Faster External Memory LCP Array Construction
- Lightweight LCP Construction for Next-Generation Sequencing Datasets
- Optimal Dynamic Sequence Representations
- Compressed suffix trees
- Inducing the LCP-Array
- Fast and Lightweight LCP-Array Construction Algorithms
- Linear time construction of compressed text indices in compact space
- Inducing Suffix and LCP Arrays in External Memory
- LCP Array Construction in External Memory
- Algorithm Theory - SWAT 2004
- In-Place Suffix Sorting
This page was built for publication: Burrows-Wheeler transform and LCP array construction in constant space
