Lightweight BWT and LCP merging via the gap algorithm

DOI10.1007/978-3-319-67428-5_15MaRDI QIDQ5150930zbMATH OpenOpenAlexFDO

Authors Lavinia Egidi, Giovanni Manzini

Publication date 16 February 2021

Published in String Processing and Information Retrieval (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-67428-5_15

zbMATH Keywords

data compressiondocument collectionsstring indexing

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Recommendations

• Lightweight merging of compressed indices based on BWT variants
• Space-efficient construction of compressed suffix trees
• Algorithm Theory - SWAT 2004
• Burrows-Wheeler transform and LCP array construction in constant space
• Lightweight LCP construction for very large collections of strings

Cites work

• Algorithm Theory - SWAT 2004
• An extension of the Burrows-Wheeler transform
• Compressed representations of sequences and full-text indexes
• Compressed suffix trees, efficient computation and storage of LCP-values
• Divide and conquer computation of the multi-string BWT and LCP array
• External memory generalized suffix and LCP arrays construction
• Fast lightweight suffix array construction and checking
• scientific article; zbMATH DE number 1947433 (Why is no real title available?)
• Inducing enhanced suffix arrays for string collections
• LCP array construction in external memory
• Lightweight data indexing and compression in external memory
• Lightweight LCP construction for very large collections of strings
• Linear time construction of compressed text indices in compact space
• Multiway in-place merging
• On the number of elements to reorder when updating a suffix array
• Permuted Longest-Common-Prefix Array

Cited in

(8)

• Computing the multi-string BWT and LCP array in external memory
• Space efficient merging of de Bruijn graphs and Wheeler graphs
• Space-efficient construction of compressed suffix trees
• Lightweight merging of compressed indices based on BWT variants
• Space-efficient computation of the LCP array from the Burrows-Wheeler transform
• Detecting mutations by eBWT
• External memory BWT and LCP computation for sequence collections with applications
• Space-efficient merging of succinct de Bruijn graphs

This page was built for publication: Lightweight BWT and LCP merging via the gap algorithm

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