Lightweight merging of compressed indices based on BWT variants

DOI10.1016/j.tcs.2019.11.001zbMath1435.68085arXiv1903.01465OpenAlexW2983503608WikidataQ126816132 ScholiaQ126816132MaRDI QIDQ2297864

Giovanni Manzini, Lavinia Egidi

Publication date: 20 February 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

longest common prefix arraycircular patternscompressed permuterm indexmulti-string BWTtrie compressionXBWT

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)

Related Items (2)

A new class of string transformations for compressed text indexing ⋮ Space efficient merging of de Bruijn graphs and Wheeler graphs

Cites Work

• Unnamed Item
• Unnamed Item
• FM-index of alignment: a compressed index for similar strings
• Lightweight algorithms for constructing and inverting the BWT of string collections
• On the number of elements to reorder when updating a suffix array
• Wheeler graphs: a framework for BWT-based data structures
• FM-index of alignment with gaps
• XBWT tricks
• An extension of the Burrows-Wheeler transform
• Lightweight LCP construction for very large collections of strings
• Efficient Algorithm for Circular Burrows-Wheeler Transform
• Compressed representations of sequences and full-text indexes
• Succinct Indexes for Circular Patterns
• The compressed permuterm index
• Compressing and indexing labeled trees, with applications
• Indexing compressed text
• Permuted Longest-Common-Prefix Array
• Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time
• Succinct de Bruijn Graphs
• External Memory Generalized Suffix and LCP Arrays Construction
• Lightweight BWT and LCP Merging via the Gap Algorithm
• Compressed suffix trees
• Indexing Variation Graphs
• SORTING CONJUGATES AND SUFFIXES OF WORDS IN A MULTISET
• Linear time construction of compressed text indices in compact space
• LCP Array Construction in External Memory
• Uniqueness Theorems for Periodic Functions
• Trickier XBWT tricks

This page was built for publication: Lightweight merging of compressed indices based on BWT variants