Linear-time string indexing and analysis in small space

DOI10.1145/3381417MaRDI QIDQ4987434zbMATH OpenOpenAlexFDO

Authors Djamal Belazzougui, Fabio Cunial, Juha Kärkkäinen, Veli Mäkinen

Publication date 3 May 2021

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.06378, http://hdl.handle.net/10138/325331

zbMATH Keywords

bidirectional BWT indexBurrows-Wheeler transformcompact data structurescompressed indexescompressed suffix arraycompressed suffix treematching statisticsmaximal exact matchmaximal repeatmaximal unique matchminimal absent wordmonotone minimal perfect hash functionpartial rank querystring kernelsuffix arraysuffix treesuffix-link tree

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Abstract: The field of succinct data structures has flourished over the last 16 years. Starting from the compressed suffix array (CSA) by Grossi and Vitter (STOC 2000) and the FM-index by Ferragina and Manzini (FOCS 2000), a number of generalizations and applications of string indexes based on the Burrows-Wheeler transform (BWT) have been developed, all taking an amount of space that is close to the input size in bits. In many large-scale applications, the construction of the index and its usage need to be considered as one unit of computation. Efficient string indexing and analysis in small space lies also at the core of a number of primitives in the data-intensive field of high-throughput DNA sequencing. We report the following advances in string indexing and analysis. We show that the BWT of a string $Tin{1,ldots,sigma}^n$ can be built in deterministic $O(n)$ time using just $O(nlogsigma)$ bits of space, where $sigmaleqn$. Within the same time and space budget, we can build an index based on the BWT that allows one to enumerate all the internal nodes of the suffix tree of $T$. Many fundamental string analysis problems can be mapped to such enumeration, and can thus be solved in deterministic $O(n)$ time and in $O(nlogsigma)$ bits of space from the input string. We also show how to build many of the existing indexes based on the BWT, such as the CSA, the compressed suffix tree (CST), and the bidirectional BWT index, in randomized $O(n)$ time and in $O(nlogsigma)$ bits of space. The previously fastest construction algorithms for BWT, CSA and CST, which used $O(nlogsigma)$ bits of space, took $O(nloglogsigma)$ time for the first two structures, and $O(nlo{g}^{epsilon}n)$ time for the third, where $epsilon$ is any positive constant. Contrary to the state of the art, our bidirectional BWT index supports every operation in constant time per element in its output.

Recommendations

• Space-efficient construction of compressed suffix trees
• Versatile succinct representations of the bidirectional Burrows-Wheeler transform
• Fast BWT in small space by blockwise suffix sorting
• Smaller Fully-Functional Bidirectional BWT Indexes
• Fully functional suffix trees and optimal text searching in BWT-runs bounded space

Cited in

(23)

• Discovering subword associations in strings in time linear in the output size
• Two-dimensional substring indexing.
• Fast compressed self-indexes with deterministic linear-time construction
• Range majorities and minorities in arrays
• Space-efficient construction of compressed suffix trees
• Parallel computation of the Burrows Wheeler transform in compact space
• Versatile succinct representations of the bidirectional Burrows-Wheeler transform
• scientific article; zbMATH DE number 7559178 (Why is no real title available?)
• Linking BWT and XBW via Aho-Corasick automaton: applications to run-length encoding
• Prefix-free parsing for building big BWTs
• String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure
• scientific article; zbMATH DE number 7651193 (Why is no real title available?)
• Algorithms and complexity on indexing founder graphs
• Elastic founder graphs improved and enhanced
• Smaller Fully-Functional Bidirectional BWT Indexes
• Linear time construction of indexable founder block graphs
• Chaining of maximal exact matches in graphs
• On approximate colored path counting
• Sorting circular suffixes in linear time
• Simplified tight bounds for monotone minimal perfect hashing
• Tight bounds for monotone minimal perfect hashing
• Faster path queries in colored trees via sparse matrix multiplication and min-plus product
• Improved circular dictionary matching

This page was built for publication: Linear-time string indexing and analysis in small space

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