Space-efficient computation of the LCP array from the Burrows-Wheeler transform

DOI10.4230/LIPICS.CPM.2019.7MaRDI QIDQ5088894zbMATH OpenOpenAlexFDO

Authors Nicola Prezza, Giovanna Rosone

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/1901.05226

zbMATH Keywords

Burrows-Wheeler transformDNA readsLCP array

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Algorithm Theory - SWAT 2004
• Computing the BWT and the LCP array in constant space
• Burrows-Wheeler transform and LCP array construction in constant space
• Space-efficient construction of compressed suffix trees
• Computing the longest common prefix array based on the Burrows-Wheeler transform

Cites work

• Alphabet-independent compressed text indexing
• An extension of the Burrows-Wheeler transform
• Computing the longest common prefix array based on the Burrows-Wheeler transform
• Detecting mutations by eBWT
• Divide and conquer computation of the multi-string BWT and LCP array
• Lightweight algorithms for constructing and inverting the BWT of string collections
• Lightweight BWT and LCP merging via the gap algorithm
• Lightweight LCP construction for very large collections of strings
• Linear time construction of compressed text indices in compact space
• Space-efficient construction of compressed indexes in deterministic linear time
• Wavelet trees for all

Cited in

(5)

• Computing the Burrows-Wheeler transform in place and in small space
• Fast and Lightweight LCP-Array Construction Algorithms
• Longest common prefix arrays for succinct \(k\)-spectra
• Space-time trade-offs for the LCP array of Wheeler DFAs
• LZ77 computation based on the run-length encoded BWT

This page was built for publication: Space-efficient computation of the LCP array from the Burrows-Wheeler transform

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5088894)