Space-efficient construction of compressed suffix trees

DOI10.1016/J.TCS.2020.11.024MaRDI QIDQ2220837zbMATH OpenOpenAlexFDO

Authors Nicola Prezza, Giovanna Rosone

Publication date 25 January 2021

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

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

zbMATH Keywords

Burrows-Wheeler transformcompressed suffix treeLCPPLCP

Mathematics Subject Classification ID

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

Abstract: We show how to build several data structures of central importance to string processing, taking as input the Burrows-Wheeler transform (BWT) and using small extra working space. Let $n$ be the text length and $sigma$ be the alphabet size. We first provide two algorithms that enumerate all LCP values and suffix tree intervals in $O(nlogsigma)$ time using just $o(nlogsigma)$ bits of working space on top of the input BWT. Using these algorithms as building blocks, for any parameter $0<epsilonleq1$ we show how to build the PLCP bitvector and the balanced parentheses representation of the suffix tree topology in $Oleft(n(logsigma+epsilo{n}^{-1}cdotloglogn)ight)$ time using at most $nlogsigmacdot(epsilon+o(1))$ bits of working space on top of the input BWT and the output. In particular, this implies that we can build a compressed suffix tree from the BWT using just succinct working space (i.e. $o(nlogsigma)$ bits) and any time in $Theta(nlogsigma)+omega(nloglogn)$. This improves the previous most space-efficient algorithms, which worked in $O(n)$ bits and $O(nlogn)$ time. We also consider the problem of merging BWTs of string collections, and provide a solution running in $O(nlogsigma)$ time and using just $o(nlogsigma)$ bits of working space. An efficient implementation of our LCP construction and BWT merge algorithms use (in RAM) as few as $n$ bits on top of a packed representation of the input/output and process data as fast as $2.92$ megabases per second.

Recommendations

• Engineering a compressed suffix tree implementation
• Fast BWT in small space by blockwise suffix sorting
• Linear-time string indexing and analysis in small space
• scientific article; zbMATH DE number 1421005
• Average linear time and compressed space construction of the Burrows-Wheeler transform

Cites work

• Algorithm Theory - SWAT 2004
• Alphabet-independent compressed text indexing
• An extension of the Burrows-Wheeler transform
• An improved algorithm for the all-pairs suffix-prefix problem
• Average linear time and compressed space construction of the Burrows-Wheeler transform
• Breaking a time-and-space barrier in constructing full-text indices
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Compressed suffix trees with full functionality
• Computing the longest common prefix array based on the Burrows-Wheeler transform
• Detecting mutations by eBWT
• Divide and conquer computation of the multi-string BWT and LCP array
• Engineering a compressed suffix tree implementation
• Fast BWT in small space by blockwise suffix sorting
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• scientific article; zbMATH DE number 2119665 (Why is no real title available?)
• 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
• Lightweight metagenomic classification via eBWT
• Linear time construction of compressed text indices in compact space
• Permuted Longest-Common-Prefix Array
• Representing trees of higher degree
• Space-efficient construction of compressed indexes in deterministic linear time
• Space-Time Tradeoffs for Longest-Common-Prefix Array Computation
• String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure
• Suffix Arrays: A New Method for On-Line String Searches
• Wavelet trees for all

Cited in

(23)

• XBWT tricks
• Space efficient merging of de Bruijn graphs and Wheeler graphs
• Lightweight merging of compressed indices based on BWT variants
• Space-efficient representation of truncated suffix trees, with applications to Markov order estimation
• Fast BWT in small space by blockwise suffix sorting
• Versatile succinct representations of the bidirectional Burrows-Wheeler transform
• Compressed Cache-Oblivious String B-tree
• scientific article; zbMATH DE number 871936 (Why is no real title available?)
• Space-efficient construction algorithm for the circular suffix tree
• scientific article; zbMATH DE number 1421005 (Why is no real title available?)
• Linear-time string indexing and analysis in small space
• Space-efficient computation of the LCP array from the Burrows-Wheeler transform
• Prefix-free parsing for building big BWTs
• Burrows-Wheeler transform and LCP array construction in constant space
• Lightweight BWT and LCP merging via the gap algorithm
• String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure
• Optimal construction of compressed indexes for highly repetitive texts
• Engineering a compressed suffix tree implementation
• Trickier XBWT tricks
• Comparative genomics with succinct colored de Bruijn graphs
• The Burrows-Wheeler transform of an elastic-degenerate string and its application to pattern matching
• Computing the LCP array of a labeled graph
• A space and time efficient algorithm for constructing compressed suffix arrays

This page was built for publication: Space-efficient construction of compressed suffix trees

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