Burrows-Wheeler transform and LCP array construction in constant space
From MaRDI portal
Publication:511147
DOI10.1016/J.JDA.2016.11.003zbMATH Open1359.68340arXiv1611.08198OpenAlexW3105423208MaRDI QIDQ511147FDOQ511147
Authors: Felipe A. Louza, Travis Gagie, Guilherme P. Telles 
Publication date: 14 February 2017
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Abstract: In this article we extend the elegant in-place Burrows-Wheeler transform (BWT) algorithm proposed by Crochemore et al. (Crochemore et al., 2015). Our extension is twofold: we first show how to compute simultaneously the longest common prefix (LCP) array as well as the BWT, using constant additional space; we then show how to build the LCP array directly in compressed representation using Elias coding, still using constant additional space and with no asymptotic slowdown. Furthermore, we provide a time/space tradeoff for our algorithm when additional memory is allowed. Our algorithm runs in quadratic time, as does Crochemore et al.'s, and is supported by interesting properties of the BWT and of the LCP array, contributing to our understanding of the time/space tradeoff curve for building indexing structures.
Full work available at URL: https://arxiv.org/abs/1611.08198
Recommendations
Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Compressed suffix trees with full functionality
- Suffix Arrays: A New Method for On-Line String Searches
- Universal codeword sets and representations of the integers
- Optimal suffix sorting and LCP array construction for constant alphabets
- Permuted Longest-Common-Prefix Array
- Inducing the LCP-array
- Fast and Lightweight LCP-Array Construction Algorithms
- Combined data structure for previous- and next-smaller-values
- Bioinformatics algorithms. Sequence analysis, genome rearrangements, and phylogenetic reconstruction
- Lightweight algorithms for constructing and inverting the BWT of string collections
- Replacing suffix trees with enhanced suffix arrays
- Lightweight data indexing and compression in external memory
- On the number of elements to reorder when updating a suffix array
- Algorithm Theory - SWAT 2004
- Analysis of the average depth in a suffix tree under a Markov model
- Wee LCP
- Space-efficient construction of compressed indexes in deterministic linear time
- 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 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
- Faster External Memory LCP Array Construction
- Title not available (Why is that?)
- Lightweight LCP Construction for Next-Generation Sequencing Datasets
- Compressed suffix trees, efficient computation and storage of LCP-values
- Linear time construction of compressed text indices in compact space
- Inducing suffix and LCP arrays in external memory
- LCP array construction in external memory
- In-Place Suffix Sorting
Cited In (12)
- Lightweight BWT and LCP merging via the gap algorithm
- When a dollar makes a BWT
- Computing the BWT and the LCP array in constant space
- Algorithm Theory - SWAT 2004
- Computing the longest common prefix array based on the Burrows-Wheeler transform
- Lyndon array construction during Burrows-Wheeler inversion
- A constant-space comparison-based algorithm for computing the Burrows-Wheeler transform
- Fast BWT in small space by blockwise suffix sorting
- String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure
- Tighter bounds for the sum of irreducible LCP values
- Tighter bounds for the sum of irreducible LCP values
- Space-time trade-offs for the LCP array of Wheeler DFAs
This page was built for publication: Burrows-Wheeler transform and LCP array construction in constant space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q511147)
