Lightweight LCP construction for very large collections of strings

DOI10.1016/j.jda.2016.03.003zbMath1362.68303arXiv1605.04098OpenAlexW3103359476MaRDI QIDQ2628803

Fabio Garofalo, Anthony J. Cox, Giovanna Rosone, Marinella Sciortino

Publication date: 15 July 2016

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

longest common prefix arrayextended Burrows-Wheeler transformgeneralized suffix array

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items

A survey of string orderings and their application to the Burrows-Wheeler transform ⋮ Space-efficient construction of compressed suffix trees ⋮ Lightweight BWT and LCP Merging via the Gap Algorithm ⋮ Burrows-Wheeler transform and LCP array construction in constant space ⋮ Inducing enhanced suffix arrays for string collections ⋮ Computing the multi-string BWT and LCP array in external memory ⋮ Unnamed Item ⋮ Lightweight merging of compressed indices based on BWT variants ⋮ The alternating BWT: an algorithmic perspective ⋮ Space-efficient computation of the LCP array from the Burrows-Wheeler transform ⋮ Detecting Mutations by eBWT ⋮ Faster online computation of the succinct longest previous factor array

Cites Work

• Unnamed Item
• Unnamed Item
• Lightweight algorithms for constructing and inverting the BWT of string collections
• Replacing suffix trees with enhanced suffix arrays
• Computing the longest common prefix array based on the Burrows-Wheeler transform
• Compressed suffix trees with full functionality
• An extension of the Burrows-Wheeler transform
• A new combinatorial approach to sequence comparison
• Algorithms and Data Structures for External Memory
• Lightweight BWT Construction for Very Large String Collections
• Suffix Arrays: A New Method for On-Line String Searches
• Linear work suffix array construction
• Space-Time Tradeoffs for Longest-Common-Prefix Array Computation
• Permuted Longest-Common-Prefix Array
• Lightweight LCP Construction for Next-Generation Sequencing Datasets
• External Memory Generalized Suffix and LCP Arrays Construction
• Inducing Suffix and LCP Arrays in External Memory
• Fast and Lightweight LCP-Array Construction Algorithms