Lightweight merging of compressed indices based on BWT variants

DOI10.1016/J.TCS.2019.11.001MaRDI QIDQ2297864zbMATH OpenOpenAlexWikidataFDO

Authors Lavinia Egidi, Giovanni Manzini

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

circular patternscompressed permuterm indexlongest common prefix arraymulti-string BWTtrie compressionXBWT

Mathematics Subject Classification ID

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

Abstract: In this paper we propose a flexible and lightweight technique for merging compressed indices based on variants of Burrows-Wheeler transform (BWT), thus addressing the need for algorithms that compute compressed indices over large collections using a limited amount of working memory. Merge procedures make it possible to use an incremental strategy for building large indices based on merging indices for progressively larger subcollections. Starting with a known lightweight algorithm for merging BWTs [Holt and McMillan, Bionformatics 2014], we show how to modify it in order to merge, or compute from scratch, also the Longest Common Prefix (LCP) array. We then expand our technique for merging compressed tries and circular/permuterm compressed indices, two compressed data structures for which there were hitherto no known merging algorithms.

Recommendations

• Lightweight BWT and LCP merging via the gap algorithm
• Lightweight data indexing and compression in external memory
• Lightweight data indexing and compression in external memory
• Space-efficient construction of compressed suffix trees
• Lightweight BWT construction for very large string collections

Cites work

• 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
• Compressing and indexing labeled trees, with applications
• Efficient algorithm for circular Burrows-Wheeler transform
• External memory BWT and LCP computation for sequence collections with applications
• External memory generalized suffix and LCP arrays construction
• FM-index of alignment with gaps
• FM-index of alignment: a compressed index for similar strings
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• Indexing compressed text
• Indexing variation graphs
• LCP array construction in external memory
• 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
• On the number of elements to reorder when updating a suffix array
• Permuted Longest-Common-Prefix Array
• Sorting conjugates and suffixes of words in a multiset
• Space-efficient construction of compressed indexes in deterministic linear time
• Succinct de Bruijn graphs
• Succinct indexes for circular patterns
• The compressed permuterm index
• Trickier XBWT tricks
• Uniqueness Theorems for Periodic Functions
• Wheeler graphs: a framework for BWT-based data structures
• XBWT tricks

Cited in

(4)

• Space efficient merging of de Bruijn graphs and Wheeler graphs
• scientific article; zbMATH DE number 2087041 (Why is no real title available?)
• Lightweight BWT and LCP merging via the gap algorithm
• A new class of string transformations for compressed text indexing

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

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