Lightweight BWT and LCP Merging via the Gap Algorithm

DOI10.1007/978-3-319-67428-5_15zbMath1454.68202OpenAlexW2753495445MaRDI QIDQ5150930

Giovanni Manzini, Lavinia Egidi

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 compressionstring indexingdocument collections

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)

Related Items (7)

Space-efficient construction of compressed suffix trees ⋮ Computing the multi-string BWT and LCP array in external memory ⋮ Unnamed Item ⋮ 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 ⋮ Space efficient merging of de Bruijn graphs and Wheeler graphs

Cites Work

• Unnamed Item
• On the number of elements to reorder when updating a suffix array
• Inducing enhanced suffix arrays for string collections
• Multiway in-place merging
• Divide and conquer computation of the multi-string BWT and LCP array
• An extension of the Burrows-Wheeler transform
• Lightweight LCP construction for very large collections of strings
• Compressed representations of sequences and full-text indexes
• Fast Lightweight Suffix Array Construction and Checking
• Lightweight Data Indexing and Compression in External Memory
• Permuted Longest-Common-Prefix Array
• External Memory Generalized Suffix and LCP Arrays Construction
• Compressed suffix trees
• Linear time construction of compressed text indices in compact space
• LCP Array Construction in External Memory
• Algorithm Theory - SWAT 2004

This page was built for publication: Lightweight BWT and LCP Merging via the Gap Algorithm